Java ArrayList vs LinkedList

1. Ikhtisar

Untuk koleksi, pustaka standar Java menyediakan banyak opsi untuk dipilih. Di antara opsi tersebut adalah dua implementasi Daftar terkenal yang dikenal sebagai ArrayList dan LinkedList, masing-masing dengan properti dan kasus penggunaannya sendiri.

Dalam tutorial ini, kita akan melihat bagaimana keduanya sebenarnya diterapkan. Kemudian, kami akan mengevaluasi aplikasi yang berbeda untuk masing-masing aplikasi.

2. ArrayList

Secara internal, ArrayList menggunakan array untuk mengimplementasikan antarmuka Daftar . Karena array berukuran tetap di Java, ArrayList membuat array dengan beberapa kapasitas awal. Sepanjang jalan, jika kita perlu menyimpan lebih banyak item daripada kapasitas default itu, itu akan mengganti array itu dengan yang baru dan lebih luas.

Untuk lebih memahami propertinya, mari kita evaluasi struktur data ini sehubungan dengan tiga operasi utamanya: menambahkan item, mendapatkannya berdasarkan indeks, dan menghapus menurut indeks.

2.1. Menambahkan

Saat kita membuat ArrayList kosong , ini menginisialisasi array pendukungnya dengan kapasitas default (saat ini 10):

Menambahkan item baru saat array itu belum penuh sesederhana menugaskan item itu ke indeks array tertentu. Indeks array ini ditentukan oleh ukuran array saat ini karena kita secara praktis menambahkan ke daftar:

backingArray[size] = newItem; size++;

Jadi, dalam kasus terbaik dan rata-rata, kompleksitas waktu untuk operasi penambahan adalah O (1) , yang cukup cepat. Namun, saat larik dukungan penuh, implementasi add menjadi kurang efisien:

Untuk menambahkan item baru, pertama-tama kita harus menginisialisasi array baru dengan kapasitas lebih dan menyalin semua item yang ada ke array baru. Hanya setelah menyalin elemen saat ini kita dapat menambahkan item baru. Oleh karena itu, kompleksitas waktu adalah O (n) dalam kasus terburuk karena kita harus menyalin n elemen terlebih dahulu.

Secara teoritis, menambahkan elemen baru berjalan dalam waktu konstan yang diamortisasi. Artinya, menambahkan n elemen membutuhkan waktu O (n) . Namun, beberapa tambahan tunggal mungkin berkinerja buruk karena kelebihan salinan.

2.2. Akses berdasarkan Indeks

Mengakses item dengan indeks mereka adalah tempat ArrayList benar-benar bersinar. Untuk mengambil item di indeks i, kita hanya perlu mengembalikan item yang berada di indeks ke - i dari backing array. Akibatnya, kompleksitas waktu untuk akses oleh operasi indeks selalu O (1).

2.3. Hapus berdasarkan Indeks

Misalkan kita akan menghapus indeks 6 dari ArrayList kita , yang sesuai dengan elemen 15 di backing array kita:

Setelah menandai elemen yang diinginkan sebagai dihapus, kita harus memindahkan semua elemen setelahnya kembali dengan satu indeks. Jelas, semakin dekat elemen ke awal larik, semakin banyak elemen yang harus kita pindahkan. Jadi kompleksitas waktu adalah O (1) pada kasus terbaik dan O (n) pada rata-rata dan kasus terburuk.

2.4. Aplikasi dan Batasan

Biasanya, ArrayList adalah pilihan default bagi banyak pengembang ketika mereka membutuhkan implementasi Daftar . Faktanya, ini sebenarnya adalah pilihan yang masuk akal ketika jumlah bacaan jauh lebih banyak daripada jumlah tulis .

Terkadang kita perlu membaca dan menulis dengan frekuensi yang sama. Jika kita memiliki perkiraan jumlah maksimum item yang mungkin, maka masih masuk akal untuk menggunakan ArrayList . Jika demikian, kita dapat menginisialisasi ArrayList dengan kapasitas awal:

int possibleUpperBound = 10_000; List items = new ArrayList(possibleUpperBound);

Estimasi ini dapat mencegah banyak penyalinan dan alokasi array yang tidak perlu.

Selain itu, array diindeks oleh nilai int di Java. Jadi, tidak mungkin menyimpan lebih dari 232 elemen dalam larik Java dan, akibatnya, di ArrayList .

3. LinkedList

LinkedList , seperti namanya, menggunakan kumpulan node tertaut untuk menyimpan dan mengambil elemen . Misalnya, berikut tampilan implementasi Java setelah menambahkan empat elemen:

Setiap node memiliki dua pointer: satu menunjuk ke elemen berikutnya dan satu lagi merujuk ke elemen sebelumnya. Memperluas ini, daftar tertaut ganda memiliki dua petunjuk yang menunjuk ke item pertama dan terakhir.

Sekali lagi, mari kita evaluasi implementasi ini sehubungan dengan operasi dasar yang sama.

3.1. Menambahkan

Untuk menambahkan node baru, pertama, kita harus menghubungkan node terakhir saat ini ke node baru:

Dan kemudian perbarui penunjuk terakhir:

Karena kedua operasi ini sepele, kompleksitas waktu untuk operasi penambahan selalu O (1) .

3.2. Akses berdasarkan Indeks

LinkedList, sebagai lawan ArrayList, tidak mendukung akses acak cepat. Jadi, untuk menemukan elemen berdasarkan indeks, kita harus melintasi beberapa bagian daftar secara manual .

Dalam kasus terbaik, ketika item yang diminta mendekati awal atau akhir daftar, kerumitan waktu akan secepat O (1). Namun, dalam skenario rata-rata dan kasus terburuk, kita mungkin berakhir dengan waktu akses O (n) karena kita harus memeriksa banyak node satu demi satu.

3.3. Hapus berdasarkan Indeks

Untuk menghapus sebuah item, pertama-tama kita harus menemukan item yang diminta dan kemudian membatalkan tautannya dari daftar . Akibatnya, waktu akses menentukan kompleksitas waktu - yaitu, O (1) pada kasus terbaik dan O (n) rata-rata dan dalam skenario kasus terburuk.

3.4. Aplikasi

LinkedLists lebih cocok ketika tingkat penambahan jauh lebih tinggi daripada tingkat pembacaan .

Juga, ini dapat digunakan dalam skenario read-heavy ketika sebagian besar waktu kita menginginkan elemen pertama atau terakhir. Perlu disebutkan bahwa LinkedList juga mengimplementasikan antarmuka Deque - mendukung akses efisien ke kedua ujung koleksi.

Secara umum, jika kita mengetahui perbedaan penerapannya, maka kita dapat dengan mudah memilih satu untuk kasus penggunaan tertentu.

Misalnya, kita akan menyimpan banyak kejadian deret waktu dalam struktur data seperti daftar. Kami tahu bahwa kami akan menerima semburan peristiwa setiap detik.

Juga, kita perlu memeriksa semua kejadian satu demi satu secara berkala dan memberikan beberapa statistik. Untuk kasus penggunaan ini, LinkedList adalah pilihan yang lebih baik karena kecepatan penambahan jauh lebih tinggi daripada kecepatan baca.

Juga, kita akan membaca semua item, jadi kita tidak bisa mengalahkan batas atas O (n) .

4. Kesimpulan

Dalam tutorial ini, pertama, kita mempelajari bagaimana ArrayList dan LinkLists diimplementasikan di Java.

Kami juga mengevaluasi kasus penggunaan yang berbeda untuk masing-masing kasus tersebut.