List (Java)

Ada dua cara paling umum untuk membuat list : sebagai array dinamis dan sebagai list berantai. Kita telah membahas keduanya sebelumnya (di sini dan di sini). Keduanya tersedia dalam bentuk generik dalam kelasjava.util.ArrayList dan java.util.LinkedList.

ArrayList adalah urutan objek yang disimpan dalam bentuk array yang ukurannya bisa membesar jika item baru ditambahkan. Sedangkan LinkedList adalah urutan objek yang disimpan dalam simpul yang terhubung dengan pointer seperti rantai. Kedua kelas ini mengimplementasikan interface java.util.List, yang memiliki operasi yang sama untuk semua jenis list.

Kedua list tersebut mendukung operasi list dasar. Tipe data abstrak didefinisikan dalam bentuk operasi yang bisa dilakukannya, bukan bagaimana data disusun. Lalu kenapa kita memiliki 2 kelas? Mengapa bukan satu kelas List saja dengan satu jenis struktur data?

Masalahnya, tidak ada satupun struktur data list yang bisa melakukan semua operasi list secara efisien. Untuk operasi tertentu, list berantai lebih efisien daripada array. Untuk operasi lainnya, array lebih efisien. Tergantung daripada bagaimana list tersebut digunakan. Kita harus bisa memilih bentuk mana yang paling cocok dengan melihat operasi apa yang sering digunakan.

Secara garis besar, kelas LinkedList lebih efisien untuk aplikasi di mana item-itemnya lebih sering ditambah atau dibuang dari dalam list, terutama dari depan atau dari tengah list. Dalam array, operasi tersebut memerlukan waktu yang cukup besar, karena untuk setiap penyisipan atau pengurangan item, item harus digeser untuk membuat tempat kosong baru ditengah list. Pada list berantai, simpul bisa diputus di tengah-tengah untuk menambahkan item baru, yaitu dengan mengubah pointernya saja.

Kelas ArrayList lebih efisien digunakan jika akses random (random access) dibutuhkan oleh aplikasi. Akses random maksudnya mengakses item ke-n di tengah-tengah list dan pindah dari satu item ke item lain yang letaknya mungkin berjauhan.

Operasi yang bisa dilakukan dengan efisien oleh kedua kelas tersebut adalah mengurutkan dan menambah item di akhir list.

Semua list mengimplementasikan metode dalam Collection, termasuk size(), isEmpty, add(Object), remove(Object), dan clear().

Metode add(Object) digunakan untuk menambah objek di akhir list. Metode remove(Object) dilakukan dengan mencari itemnya dahulu, yang tidak efisien dilakukan pada list berantai karena pada list berantai item dibandingkan satu per satu dari awal list hingga item ditemukan.

Interface List menambah beberapa metode untuk mengakses item pada list tergantung dari urutannya dalam list. Untuk objeklist bertipe List, metode-metode yang tersedia adalah :

- list.get(indeks) -- mengembalikan Object di posisi indeks dalam list, di mana indeks dimulai dari 0, 1, 2, .... hinggalist.size() - 1. Parameter indeks harus ada dalam rentang ini, jika tidak maka pengecualianIndexOutOfBoundsException akan dilemparkan.

- list.set(indeks, obj) -- menyimpan obj di dalam list pada posisi indeks, dan mengganti isi objek yang sudah ada di posisi tersebut. Metode ini tidak mengubah jumlah elemen di dalam list atau memindahkan elemen lain.

- list.add(indeks, obj) -- menyisipkan objek obj di dalam list pada posisi indeks. Jumlah item di dalam list akan bertambah satu, dan item setelah posisi indeks akan digeser ke belakang. Nilai indeks harus berada pada rentang 0 hinggalist.size().

- list.remove(indeks) -- menghapus objek pada posisi indeks. Item setelah posisi ini akan digeser maju untuk mengisi kekosongan objek pada posisi tersebut setelah item dihapus.

- list.indexOf(obj) -- mencari objek obj di dalam list dan mengembalikan indeksnya pada list, jika ada. Jika objek yang dicari tidak ada maka nilai -1 akan dikembalikan. Jika obj ada lebih dari satu dalam list, hanya indeks pertama yang dikembalikan.

Metode-metode ini didefinisikan pada kelas ArrayList dan LinkedList, meskipun metode-metode ini hanya efisien padaArrayList. Kelas LinkedList memiliki beberapa metode tambahan yang tidak ada pada ArrayList. Jika linkedlist adalah objek bertipe LinkedList, maka

- linkedlist.getFirst() -- mengembalikan Object pada posisi pertama di dalam list. List tidak diubah sama sekali.

- linkedlist.getLast() -- mengembalikan Object pada posisi terakhir di dalam list. List tidak diubah sama sekali.

- linkedlist.removeFirst() -- menghapus Objek pada posisi pertama di dalam list. Object yang dihapus akan dikembalikan sebagai nilai keluaran.

- linkedlist.removeLast() -- menghapus Objek pada posisi terakhir di dalam list. Object yang dihapus akan dikembalikan sebagai nilai keluaran.

- linkedlist.addFirst(obj) -- menambah obj pada posisi pertama di dalam list.

- linkedlist.addLast(obj) -- menambah obj pada posisi terakhir di dalam list. (Sama persis denganlinkedlist.add(obj))

Metode-metode di atas sepertinya dibuat sehingga LinkedList mudah digunakan sebagai tumpukan atau antrian (lihat bagian sebelumnya dan bagian ini). Misalnya kita bisa menggunakan LinkedList sebagai antrian dengan menambah item di akhir list (menggunakan metode addLast()) dan menghapus item dari awal list (menggunakan metode removeFirst()).

Jika list adalah objek bertipe List maka metode list.iterator() yang didefinisikan pada interface Collection, akan mengembalikan Iterator yang bisa digunakan untuk menelusuri list tersebut dari awal hingga akhir.

Akan tetapi, untuk List ada tipe Iterator khusus yang bernama ListIterator yang memiliki kemampuan tambahan. Metodelist.listIterator() mengembalikan objek bertipe ListIterator dari list.

ListIterator memiliki metode Iterator biasa, seperti hasNext() dan next(), tetapi juga hasPrevious() dan previoussehingga kita bisa melakukan penelusuran mundur.

Untuk mengerti lebih dalam, mungkin ada baiknya jika iterator diibaratkan sebagai iterator yang menunjuk pada posisi di antara dua elemen, atau di akhir atau di depan list. Dalam diagram berikut, item dalam list digambarkan sebagai kotak, dan panah menunjukkan posisi dari iterator :

Jika iter adalah suatu ListIterator, maka

- iter.next() memindahkan iterator satu tempat ke kanan dan mengembalikan item yang baru dilewatinya.

- Metode iter.previous() memindahkan iterator ke kiri dan mengambalikan item yang dilewatinya.

- Metode iter.remove() menghapus item dari dalam list. Item yang dihapus adalah item yang baru saja dilewati olehiter.next() atau iter.previous().

- iter.add(Object) akan menambah Object ke dalam list pada posisi iterator sekarang. Artinya bisa berada di tengah-tengah dua item, di awal list atau di akhir list.

(Untuk pengetahuan, list yang digunakan oleh kelas LinkedList adalah list berantai ganda (doubly linked list). Artinya, setiap simpul pada list memiliki dua pointer, yaitu satu yang menunjuk pada simpul setelahnya dan satu lagi menunjuk pada simpul sebelumnya. Sehingga metode next() dan previous() bisa diimplementasikan dengan efisien. Dan juga, metode addLast()dan getLast() menjadi efisien karena kelas LinkedList juga memiliki variabel instansi yang menunjuk pada simpul terakhir di dalam list.)

Sebagai contoh untuk menggunakan ListIterator, misalnya kita ingin menjaga agar suatu list selalu terurut dalam urutan menaik. Ketika kita menambah item di dalam list, kita bisa menggunakan ListIterator untuk menemukan posisi yang tepat di dalam list untuk meletakkan item baru itu.

Idenya adalah memulai dari awal list, kemudian memindahkan iterator melalui semua item yang lebih kecil dari item yang ingin sisipkan. Pada posisi tersebut, metode add() dari iterator itu bisa digunakan untuk menyisipkan item pada posisi yang tepat.

Untuk menentukan bahwa item baru tersebut lebih besar dari item di dalam list, maka kita asumsikan bahwa item dalam list sudah mengimplementasikan interface Comparable dan memiliki metode compareTo(). (Interface ini didiskusikan pada bagian sebelumnya). Berikut ini adalah metode untuk melakukannya.

static void sisipTerurut(List list, Comparable itemBaru) {
 
    // Kondisi awal : Item dalam ist diurut dalam urutan menaik
    //                menurut metode compareTo.
    //                itemBaru.compareTo(item) harus didefinisikan untuk 
    //                setiap item di dalam list.
    //
    // Kondisi akhir : itemBaru yang sudah ditambahkan
    //                ada pada posisi yang benar, sehingga list
    //                masih dalam keadaan terurut menaik
 
    ListIterator iter = list.listIterator();
 
    // Pindahkan iterator sehingga menunjuk pada posisi yang tepat
    // Jika itemBaru lebih besar dari semua item di dalam list, maka
    // perulangan while akan berhenti ketika iter.hasNext() bernilai
    // false, yaitu ketika iterator sampai pada akhir list.
 
    while (iter.hasNext()) {
        Object item = iter.next();
        if (itemBaru.compareTo(item) <= 0) {
            // itemBaru harus ada SEBELUM item pada iter
            // Pindahkan iterator satu tempat sehingga
            // menunjuk pada posisi penyisipan yang benar,
            // dan pada akhir perulangan.
            iter.previous();
            break;
        }
    }
 
    iter.add(itemBaru);
 
} // akhir sisipTerurut()

Karena parameter pada metode ini bertipe List, maka metode ini bisa digunakan pada ArrayList maupun LinkedList, dan kira-kira akan berjalan dengan tingkat efisiensi yang sama untuk kedua jenis list. Mungkin akan lebih mudah untuk menulis metode di atas dengan menggunakan indeks seperti pada array, dan dengan menggunakan metode get(indeks) danadd(indeks,obj). Akan tetapi metode ini akan berjalan sangat lambat untuk LinkedList karena get(indeks) padaLinkedList berjalan tidak efisien.