Tips menggunakan koleksi

1. Daftar koleksi

Seperti yang mungkin Anda ingat, Java memiliki koleksi — alat praktis untuk menyimpan objek dengan tipe yang sama.

Mari kita coba mengingat antarmuka terkait koleksi utama:

Daftar , Tetapkan , Peta dan Antrean .

Seperti biasa, alat tidak selalu baik atau buruk — yang penting adalah apakah Anda menggunakannya untuk tujuan yang dimaksudkan. Dan untuk melakukan itu, kita harus benar-benar memahami fitur spesifiknya untuk mengetahui koleksi mana yang akan digunakan dan kapan.

1. Daftar

Mari kita mulai dengan koleksi yang paling banyak digunakan.

Daftar sedekat mungkin dengan array lama biasa.

Koleksi ini memungkinkan kita dengan mudah menyimpan daftar objek dengan tipe yang sama tanpa mengkhawatirkan ukuran koleksi itu sendiri, seperti yang harus kita lakukan jika menggunakan array. Elemen koleksi diakses oleh index. Jika kita tahu persis di mana sebuah objek berada dan perlu sering mengaksesnya tanpa harus sering menambah atau menghapus elemen, List sangat ideal.

2. Tetapkan

Set memiliki struktur yang sama sekali berbeda.

Set paling cocok saat kita perlu menyimpan benda-benda unik. Misalnya, kumpulan penulis di perpustakaan yang setiap penulisnya unik. Tapi kita tidak bisa begitu saja pergi dan mengambil penulis tertentu darinya. Set memungkinkan kita memeriksa dengan cepat apakah penulis tertentu ada di perpustakaan kita, yaitu kita dapat memeriksa apakah objek unik ada di Set . Kami juga dapat mengulangi seluruh koleksi, mengakses setiap elemen, tetapi melakukannya tidak optimal.

Dengan kata lain, untuk perpustakaan kami, Set dapat mewakili koleksi semua penulis unik untuk memeriksa dengan cepat apakah ada penulis tertentu.

3. Peta

Peta lebih seperti lemari arsip, di mana setiap file ditandatangani dan dapat menyimpan objek individual atau seluruh struktur. Peta harus digunakan dalam kasus di mana kita perlu mempertahankan pemetaan dari satu nilai ke nilai lainnya.

Untuk Map , hubungan ini disebut key-value pair.

Kita dapat menggunakan struktur ini di perpustakaan kita dengan menggunakan objek penulis sebagai kunci dan daftar ( Daftar objek) buku sebagai nilainya. Jadi, setelah memeriksa Set untuk melihat apakah objek penulis ada di pustaka, kita bisa menggunakan objek penulis yang sama untuk mendapatkan Daftar bukunya dari Map .

4. Antrian

Queue adalah kumpulan yang — mengejutkan! — mengimplementasikan perilaku antrian. Dan antriannya bisa berupa LIFO (Last In, First Out) atau FIFO (First In, First Out). Terlebih lagi, antrean bisa dua arah, atau "berakhir ganda".

Struktur ini berguna ketika objek yang ditambahkan ke kelas perlu digunakan sesuai urutan penerimaannya. Misalnya, ambil perpustakaan kami.

Kami dapat menambahkan pengunjung yang baru tiba ke Antrean dan melayani mereka secara bergiliran, menerbitkan buku yang mereka inginkan.

Seperti yang bisa kita lihat, masing-masing struktur ini bagus jika digunakan untuk tujuan yang dimaksudkan. Dan kami menemukan penggunaan yang baik untuk keempat jenis koleksi dalam satu contoh perpustakaan.

2. Kompleksitas

Seperti yang telah disebutkan, koleksi yang kami pertimbangkan di atas adalah antarmuka, yang artinya harus memiliki implementasi agar kami dapat menggunakannya.

Sama seperti memalu paku dengan mikroskop bukanlah ide terbaik, tidak setiap implementasi koleksi cocok untuk setiap situasi.

Saat memilih alat yang tepat untuk suatu pekerjaan, kami biasanya melihat 2 karakteristik:

• Seberapa cocok alat tersebut dengan pekerjaannya?
• Seberapa cepat itu akan menyelesaikan pekerjaan?

Kami telah menghabiskan beberapa waktu mencari tahu cara memilih alat yang cocok untuk suatu pekerjaan, tetapi kecepatannya adalah sesuatu yang baru.

Dalam komputasi, kecepatan alat sering dinyatakan dalam kompleksitas waktu dan dilambangkan dengan huruf kapital O.

Apa sih kompleksitas waktu itu?

Secara sederhana, kompleksitas waktu menunjukkan waktu yang dibutuhkan oleh suatu algoritma dalam koleksi untuk melakukan tindakan tertentu (menambahkan/menghapus elemen, mencari elemen).

ArrayList vs LinkedList

Mari kita lihat ini menggunakan dua implementasi interface List — ArrayList dan LinkedList .

Untuk penampilan luar, mengerjakan koleksi ini serupa:

List<String> arrayList = new ArrayList<>();
arrayList.add(String);
arrayList.get(index);
arrayList.remove(index);
arrayList.remove(String);
 
List<String> linkedList = new LinkedList<>();
 
linkedList.add(String);
 
linkedList.get(index);
linkedList.remove(index);
linkedList.remove(String);
    

Seperti yang Anda lihat, untuk kedua jenis koleksi, penambahan, pengambilan, dan penghapusan elemen terlihat sama. Ini karena ini adalah implementasi pada antarmuka yang sama. Tapi di situlah kesamaan berakhir.

Karena implementasi antarmuka Daftar yang berbeda , kedua struktur ini melakukan tindakan yang berbeda secara lebih efisien daripada yang lain.

Pertimbangkan untuk menghapus dan menambahkan elemen.

Jika kita perlu menghapus elemen dari tengah ArrayList , kita harus menimpa bagian manapun dari daftar yang mengikuti elemen yang kita hapus.

Misalkan kita memiliki daftar 5 elemen dan kita ingin menghapus yang ke-3.

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
list.remove(2);
    

Dalam hal ini, penghapusan membebaskan satu sel, jadi kita perlu menulis elemen ke-4 di mana yang ke-3, dan yang ke-5 di mana yang ke-4.

Ini sangat tidak efisien.

Hal yang sama terjadi saat menambahkan elemen ke tengah daftar.

LinkedList disusun secara berbeda. Menambah atau menghapus elemen cepat, karena kita hanya perlu mengubah referensi di elemen sebelumnya dan berikutnya, dengan demikian mengecualikan objek yang kita hapus dari rangkaian elemen.

Kembali ke contoh daftar 5 elemen yang sama, setelah menghapus elemen ke-3, yang perlu kita lakukan hanyalah mengubah referensi elemen ke-2 ke elemen berikutnya dan referensi elemen ke-4 ke elemen sebelumnya.

Ketika sebuah elemen ditambahkan ke daftar, proses yang sama terjadi, tetapi sebaliknya.

Perhatikan betapa lebih sedikit pekerjaan yang perlu kita lakukan di LinkedList dibandingkan dengan ArrayList . Dan itu baru 5 elemen. Jika daftar kami memiliki 100 elemen atau lebih, keunggulan LinkedList akan menjadi lebih terlihat.

Tapi bagaimana situasinya berubah jika kita mengakses elemen berdasarkan indeks?

Semuanya justru sebaliknya di sini.

Karena ArrayList disusun sebagai array biasa, mendapatkan elemen apa pun dengan indeksnya akan sangat mudah bagi kita. Kami cukup memindahkan penunjuk ke tempat tertentu dan mendapatkan elemen dari sel yang sesuai.

Tapi LinkedList tidak berfungsi seperti itu. Kita harus menelusuri semua elemen daftar untuk menemukan elemen dengan indeks tertentu.

Haruskah kita mencoba mengungkapkan semua ini dalam istilah O besar?

Mari kita mulai dengan mengakses elemen berdasarkan indeks.

Dalam ArrayList , ini terjadi dalam satu langkah, terlepas dari di mana elemen tersebut berada dalam daftar. Entah di akhir atau di awal.

Dalam hal ini, kompleksitas waktu akan menjadi O(1) .

Dalam LinkedList , kita harus mengulangi sejumlah elemen yang sama dengan nilai indeks yang kita butuhkan.

Kompleksitas waktu untuk tindakan seperti itu adalah O(n) , di mana n adalah indeks elemen yang kita butuhkan.

Di sini Anda melihat bahwa angka yang kita masukkan ke dalam tanda kurung O besar sesuai dengan jumlah tindakan yang dilakukan.

Apakah kita akan kembali menghapus dan menambahkan?

Mari kita mulai dengan LinkedList.

Karena kita tidak perlu melakukan banyak tindakan untuk menambah atau menghapus elemen, dan kecepatan operasi ini tidak bergantung pada lokasi elemen, kompleksitasnya dinyatakan sebagai O(1) dan dikatakan menjadi konstan.

Kompleksitas waktu dari operasi untuk ArrayList ini juga O(n) , yang kita sebut kompleksitas linier.

Dalam algoritme dengan kompleksitas linier, waktu berjalan bergantung langsung pada jumlah elemen yang akan diproses. Mungkin juga tergantung pada posisi elemen, apakah itu di awal daftar atau menjelang akhir.

Kompleksitas waktu juga bisa logaritmik. Ini dinyatakan sebagai O(log n) .

Sebagai contoh, pertimbangkan TreeSet yang diurutkan yang terdiri dari 10 angka. Kami ingin menemukan nomor 2.

Karena daftar disortir dan tidak mengandung duplikat, kita dapat membaginya menjadi dua dan memeriksa separuh mana yang berisi nomor yang diinginkan, buang bagian yang tidak relevan, lalu ulangi proses ini hingga kita mencapai elemen yang diinginkan. Pada akhirnya, kita akan menemukan (atau tidak menemukan) nomor setelah memproses log(n) jumlah elemen.

Berikut adalah tabel yang merangkum kompleksitas waktu dari koleksi lainnya.

Sekarang kita memiliki tabel yang menunjukkan kompleksitas waktu dari koleksi populer, kita dapat menjawab pertanyaan mengapa, dari sekian banyak koleksi, kita paling sering menggunakan ArrayList , HashSet dan HashMap .

Hanya saja mereka yang paling efisien untuk sebagian besar tugas :)