Mengaitkan Objek (Struktur Data Berantai-Java)

Hampir semua objek memiliki variabel instansi. Jika variabel instansi bertipe suatu kelas atau interface, maka variabel instansi itu bisa menyimpan referensi ke objek lain. Referensi disebut juga pointer, karena referensi menunjuk pada suatu objek. (Variabel yang berisi referensi ke suatu objek juga bisa berisi null alias tidak menunjuk ke mana-mana). Jika satu objek memiliki referensi ke objek lain, objek itu disebut terkait satu sama lain. Struktur data kompleks bisa dibuat dengan mengaitkan objek satu sama lain.

Jika suatu objek memiliki pointer ke objek lain dengan tipe yang sama, maka definisi kelasnya bersifat rekursif. Rekursi jenis ini banyak terjadi, misalnya kelas Pegawai yang melambangkan pegawai di suatu perusahaan. Semua orang kecuali bos tertinggi memiliki atasan, di mana atasannya ini adalah juga pegawai perusahaan tersebut. Tentunya kelas Pegawai memiliki variabel instansi dengan tipe Pegawai yang menunjuk pada atasan pegawai itu, sehingga :

class Pegawai {
    // Objek untuk menyimpan data tentang seorang pegawai
    String nama;          // Nama pegawai
 
    Pegawai atasan;  // Atasan pegawai ini
    .
    .  // (Metode dan variabel instansi lain.)
    .
} // akhir kelas Pegawai

Jika pgw adalah variabel bertipe Pegawai, maka pgw.atasan adalah variabel lain yang juga bertipe Pegawai. Jika pgw menunjuk pada bos tertinggi, maka pgw.atasan berisi null yang artinya ia tidak memiliki atasan. Kita bisa mencetak nama atasan seorang pegawai, misalnya dengan pernyataan Java berikut :

if ( pgw.atasan == null) {
    System.out.println( pgw.nama " adalah bos tertinggi." );
}
else {
    System.out.print( "Atasan dari " + pgw.nama + " ialah " );
    System.out.println( pgw.atasan.nama );
}

Sekarang, misalnya kita ingin tahu berapa tingkat di atas seorang pegawai hingga sampai pada bos tertinggi. Jika bisa melacak atasan dari atasannya, dan seterusnya, hingga sampai pada bos tertinggi, kemudian menghitung berapa langkah yang diperlukan hingga sampai ke bos tertinggi itu:

if ( pgw.atasan == null ) {
    System.out.println( pgw.nama " adalah bos tertinggi." );
}
else {
    Pegawai pointer;  // Untuk menunjuk pada urutan bos.
    pointer = pgw.supervisor;
    if ( pointer.atasan == null) {
        System.out.println( pgw.nama
                + " memiliki atasan langsung bos tertinggi." );
    }
    else {
        int level = 0;
        while ( pointer.atasan != null ) {
            level++;  // Level atasan
            pointer = pointer.atasan;
        }
        System.out.println( "Ada " + level
                + " atasan antara " + pgw.nama
                + " dan bos tertinggi." );
    }
}

Ketika perulangan while dieksekusi, pointer akan menunjuk pada atasan pgw, kemudian atasannya lagi, dan seterusnya. Variabel level dinaikkan 1 setiap kali pointer menunjuk pada atasan baru. Perulangan selesai ketika pointer.atasan berisinull yang artinya pointer telah sampai pada bos tertinggi. Pada saat itu, level telah mencatat berapa level yang dibutuhkan daripgw ke bos tertinggi.

Dalam contoh ini, variabel atasan terlihat natural dan berfungsi dengan baik. Sebenarnya, struktur data yang dibangun dengan mengaitkan objek satu sama lain sangat berguna, sehingga sering digunakan sebagai topik pembahasan dalam ilmu komputer. Kita akan melihat beberapa contohnya. Pada bagian ini dan berikutnya, kita akan melihat yang dinamakan list berantai (linked list).

List berantai merupakan rantai objek yang bertipe sama, yang terkait oleh pointer dari satu objek ke objek lain. Mirip dengan hirarki organisasi antara pgw hingga bos tertinggi pada contoh di atas. Kita bisa juga memiliki siatuasi yang lebih kompleks di mana satu objek berisi pointer ke beberapa objek. Kita akan lihat contohnya di bagian berikutnya.

Di bagian ini, list berantai akan dibuat dari objek yang bertipe Simpul yang didefinisikan sebagai berikut :

class Simpul {
    String item;
    Simpul berikut;
}

Istilah simpul sering digunakan untuk menyebut salah satu objek di dalam struktur data berantai. Objek dengan tipe Simpul bisa disambung seperti pada gambar di atas. Simpul terakhir dalam list tersebut bisa ditentukan apabila variabel instansi berikut berisinull.

Meskipun Simpul pada contoh ini terlihat sederhana, kita bisa menggunakannya untuk mengilustrasikan operasi umum pada list berantai. Operasi umumnya meliputi menghapus simpul dari list, menyisipkan simpul baru ke dalam list, dan mencari String padaitem di dalam list. Kita akan lihat beberapa subrutin yang melakukan operasi ini.

Agar list berantai bisa digunakan dalam program, program tersebut perlu variabel untuk menunjuk pada simpul pertama dari list. Variabel itu hanya perlu menunjuk pada simpul pertama, karena simpul lainnya bisa dicari dari simpul tertama kemudian mengurutkan melalui pointer ke simpul berikutnya.

Kita bisa membuat objek baru dengan misalnya bernama "ListString" yang memiliki variabel instansi bernama "kepala". Variabel ini bertipe Simpul dan menyimpan referensi ke simpul pertama dari list berantai. Jika listnya kosong, maka kepala berisinull.

public class ListString {
    Simpul kepala;
    .
    .
    . // metode dan variabel instansi lainnya
}

Misalnya kita ingin tahu apakah suatu string, itemDicari ada di salah satu simpul di dalam list. Kita bisa membandingkanitemDicari dengan isi setiap simpul di dalam list. Caranya, kita akan menggunakan variabel bertipe Simpul yang bernamapointer untuk digunakan sebagai penunjuk ke simpul-simpul yang akan kita lihat. Kita hanya bisa mengakses list melalui variabelkepala, jadi kita bisa mulai dengan mengisi pointer dengan isi kepala.

Simpul pointer = kepala;  // Mulai dari simpul pertama.

Kita harus membuat variabel baru ini karena kita akan mengganti isinya pada saat melakukan pencarian. Kita tidak bisa mengganti isi kepala, karena jika kita ganti, kita akan kehilangan jejak list yang kita buat. Untuk pindah dari satu simpul ke simpul berikutnya, kita cukup menggunakan perintah pointer = pointer.berikut;. Kita akan tahu bahwa kita telah sampai pada akhir list jika pointer bernilai null.

Semuanya bisa kita tuangkan dalam metode instansi cari() pada kelas ListString sebagai berikut :

public boolean cari(String itemDicari) {
    // Kembalikan true jika itemDicari ada di dalam list
    // false jika tidak ada dalam list.
 
    Simpul pointer;    // Pointer untuk menelusuri list
 
    pointer = kepala;
    // Mulai pencarian dari kepala list (kepala adalah variabel instansi)
 
    while ( pointer != null ) {
        // Lihat isi simpul satu per satu. Jika isinya sama dengan
        // yang kita cari, kembalikan true, jika tidak
        // teruskan pencarian di simpul berikutnya
        if ( pointer.item.equals(itemDicari) )
            return true;
        pointer = pointer.berikut;  // Pindah ke simpul berikutnya
    }
 
    // Di sini, kita telah sampai pada akhir list
    // akan tetapi tidak ada item yang kita cari.
    // Kembalikan false, yang artinya kita tidak menemukan item ini.
 
    return false;
 
} // akhir cari()

Pola di atas akan sering digunakan nanti: Jika kepala adalah variabel yang menunjuk pada suatu list berantai, maka untuk proses semua simpul dalam list, kita bisa lakukan dengan :

pointer = kepala;
while ( pointer != null ) {
    .
    .  // proses simpul yang ditunjuk oleh pointer
    .
    pointer = pointer.berikut;
}

Mungkin saja listnya kosong, yaitu apabila isi kepala adalah null. Dalam contoh kode di atas, jika kepala berisi null, maka badan perulangan while tidak akan dieksekusi sama sekali, karena kondisi perulangan hanya bisa dijalankan apabila pointerbernilai null.

Menyisipkan item baru ke dalam list sedikit lebih sulit. Dalam kelas ListString, item pada simpul dibuat dalam urutan menaik. Jika suatu item ditambahkan ke dalam list, item tersebut harus ditempatkan pada posisi yang tepat sesuai urutannya. Artinya, kita harus menyisipkan item baru ditengah-tengah list, di antara dua simpul yang sudah ada.

Supaya mudah, kita membutuhkan dua variabel dengan tipe Simpul, di mana masing-masing menunjuk pada 2 posisi di mana item baru akan disisipkan di antaranya. Pada ilustrasi berikut, variabel ini adalah sebelum dan pointer. Variabel lain, yaitusimpulBaru menyimpan referensi ke simpul baru yang akan disisipkan. Untuk melakukan penyisipan, hubungan antara sebelumdan pointer harus diputus, dan kait baru dari sebelum ke simpulBaru dan dari simpulBaru ke pointer harus dibuat.

Perintah "sebelum.berikut = simpulBaru;" digunakan untuk membuat sebelum.berikut menunjuk pada simpul baru. Dan perintah "simpulBaru.berikut = pointer" digunakan untuk membuat simpulBaru.berikut menunjuk pada pointer. Akan tetapi, sebelum kita menjalankan perintah ini, kita harus menempatkan posisi sebelum dan pointer pada tempat yang benar terlebih dahulu (seperti pada ilustrasi di atas).

Kita akan mulai dari awal list, kemudian pindah ke simpul berikutnya selama isinya lebih kecil dari item baru. Ketika kita memindahkan pointer dari satu tempat ke tempat berikutnya, hati-hati bahwa kita bisa sampai di akhir list tanpa kita sadari. Artinya kita tidak bisa meneruskan lagi apabila pointer sampai ke akhir list, yaitu ketika pointer.next bernilai null.

Jika sisipItem adalah item item yang akan disisipkan, maka kita asumsikan bahwa item ini harus berada di dalam list. Kode berikut akan menempatkan posisi sebelum dan pointer dengan tepat:

Simpul pointer, sebelum;
sebelum = kepala;     // Mulai di awal list
pointer = kepala.berikut;
while ( pointer != null && pointer.item.compareTo(sisipItem) < 0 ) {
    sebelum = pointer;  // bisa juga menggunakan "sebelum = sebelum.berikut"
    pointer = pointer.berikut;
}

(Kode di atas menggunakan compareTo() dari kelas String untuk menguji apakah item di dalam node bernilai kurang dari item yang akan disisipkan.)

Kode di atas boleh-boleh saja, akan tetapi asumsi kita untuk menyisipkan node baru di tengah-tengah list tidak selamanya benar. Mungkin saja sisipItem lebih kecil dari item pertama. Artinya, simpul baru harus disisipkan pada kepala list. Ini bisa dilakukan dengan instruksi berikut :

simpulBaru.berikut = kepala;   // Buat simpulBaru.next menunjuk kepala lama
kepala = simpulBaru;        // Buat simpulBaru sebagai kepala list yang baru

Atau bisa saja listnya kosong. Artinya, simpulBaru menjadi simpul pertama dan satu-satunya di dalam list. Ini bisa dilakukan dengan mengisi kepala = simpulBaru. Metode sisip() berikut ini merangkum semua kemungkinan di atas :

public void sisip(String sisipItem) {
    // Tambah sisipItem ke dalam list. Boleh menyisipkan
    // kopi yang sama
 
    Simpul simpulBaru;          // Simpul baru yang berisi item baru
    simpulBaru = new Simpul();
    simpulBaru.item = sisipItem;  // (N.B.  isi simpulBaru.berikut masih null)
 
    if ( kepala == null ) {
        // List masih kosong
        // Buat kepala menunjuk ke simpulBaru
        kepala = simpulBaru;
    }
    else if ( kepala.item.compareTo(sisipItem) >= 0 ) {
        // Item baru kurang dari item pertama list
        // Jadi item baru harus disisipkan sebelum kepala list
        simpulBaru.berikut = kepala;
        kepala = simpulBaru;
    }
    else {
        // Item baru akan disisipkan di tengah-tengah list setelah
        // item pertama. Cari posisi yang tepat dan sisipkan di sana
        Simpul pointer;     // Simpul untuk menelusuri list
        Simpul sebelum;   // Simpul yang menunjuk pada posisi sebelum pointer
        sebelum = kepala; // Set sebelum ke kepala list dan pointer ke posisi setelahnya
        pointer = kepala.berikut;
        while (pointer != null && pointer.item.compareTo(sisipItem) < 0) {
            // Pindahkan sebelum dan pointer ke posisi berikutnya hingga pointer
            // sampai di akhir list atau sampai pada item yang isinya lebih besar
            // dari sisipItem. Setelah perulangan selesai, pointer menunjuk
            // pada posisi di mana sisipItem akan disisipkan
            sebelum = pointer;
            pointer = pointer.berikut;
        }
        simpulBaru.berikut = pointer;     // Sisipkan simpulBaru setelah "sebelum"
        sebelum.berikut = simpulBaru;
    }
}  // akhir sisip()

Jika Anda memperhatikan dengan seksama diskusi di atas, mungkin Anda akan ingat bahwa ada satu kasus lagi yang tidak pernah disebutkan. Apa yang terjadi jika simpul baru harus disisipkan di akhir list? Ini terjadi jika semua item di dalam list lebih kecil daripada item baru.

Sebenarnya, kasus ini sudah ditangani dengan benar oleh subrutin, yaitu di bagian akhir pernyataan if . Jika sisipItem lebih besar dari semua item di dalam list, maka perulangan while akan berhenti ketika pointer selesai menelusuri sampai pada akhir list hingga pointer bernilai null. Akan tetapi, ketika ini terjadi, sebelum masih tetap menunjuk pada item terakhir pada list. Perintah sebelum.berikut = simpulBaru menambahkan simpul baru di akhir list. Karena isi pointer adalah null, maka perintah [code]simpulBaru.berikut = pointer akan mengisi simpulBaru.berikut dengan null. null adalah nilai yang tepat untuk menandakan akhir list.

Operasi untuk menghapus mirip dengan operasi menyisipkan item, meskupun sedikit lebih mudah. Masih ada beberapa kasus khusus yang harus dipikirkan. Ketika simpul pertama akan dihapus, maka isi kepala harus diubah ke simpul kedua. Karenakepala.berikut adalah simpul berikutnya, maka ini bisa dilakukan dengan perintah kepala = kepala.berikut. (Sekali lagi, perhatikan bahwa perintah ini juga berlaku jika kepala.berkut berisi null[code], yaitu ketika hanya ada satu item di dalam list. Ketika satu-satunya item ini dihapus, maka list bernilai [code]null yang artinya list sudah kosong.)

Jika simpul yang akan dihapus ada di tengah-tengah list, maka kita bisa membuat variabel sebelum dan pointer di manapointer menunjuk pada simpul yang akan dihapus, dan sebelum menunjuk pada simpul sebelumnya. Setelah diposisikan dengan benar, perintah "sebelum.berikut = pointer.berikut" akan menghapus simpul tersebut. Simpul yang dihapus akan diambil oleh pemulung memori.

Berikut ini adalah kode lengkap dari metode hapus() :

public boolean hapus(String hapusItem) {
    // Jika hapusItem ada dalam list, hapus.
    // Kembalikan true jika string ditemukan dan dihapus.
    // Jika string tidak ditemukan kembalikan false.
    // (Jika ada beberapa item dengan isi yang sama, hanya
    // hapus yang pertama)
 
    if ( kepala == null ) {
        // Jika list kosong, sudah pasti tidak ada string hapusItem
        return false;
    }
    else if ( kepala.item.equals(hapusItem) ) {
        // Jika hapusItem ada pada simpul pertama, hapus.
        kepala = kepala.berikut;
        return true;
    }
    else {
        // Di sini, maka ada kemungkinan string terdapat
        // di tengah-tengah list. Cari itemnya di dalam list.
        Simpul pointer;     // Simpul untuk menelusuri list
        Simpul sebelum;   // Selalu menunjuk pada simpul sebelum pointer
        sebelum = kepala;  // Mulai dari awal list
        pointer = kepala.berikut;
        while (pointer != null && pointer.item.compareTo(hapusItem) < 0) {
            // Pindahkan sebelum dan pointer di dalam list hingga
            // pointer sampai pada akhir list atau sampai pada item yang
            // lebih besar atau sama dengan hapusItem. Ketika perulangan
            // selesai, pointer menunjuk pada posisi di mana hapusItem
            // seharusnya berada (jika ada)
            sebelum = pointer;
            pointer = pointer.berikut;
        }
        if ( pointer != null && pointer.item.equals(hapusItem) ) {
            // Pointer menunjuk pada simpul yang akan dihapus
            // Hapus dengan mengubah simpul sebelumnya
            sebelum.berikut= pointer.berikut;
            return true;
        }
        else {
            // Item yang dicari tidak ada
            return false;
        }
    }
} // akhir hapus()