Perbedaan antara daftar array dan daftar tertaut

Bagaimana data disimpan?

Daftar Array dan Daftar Tertaut adalah istilah umum dalam hal penyimpanan dan pengambilan data. Meskipun ada banyak perangkat penyimpanan, pada akhirnya, mereka bergantung pada mekanisme penyimpanan. Dua mekanisme penyimpanan ini menempatkan data Anda di perangkat penyimpanan dan mengambilnya saat dibutuhkan. Mari kita lihat bagaimana mereka menyimpan data dalam memori mereka. Daftar array menggunakan penyimpanan berurutan, dan potongan data disimpan satu demi satu yang lain. Ini mungkin bentuk penyimpanan yang lebih sederhana - menghindari kebingungan. Ya, kami dapat mengambil item atau data berikutnya dari lokasi memori berikutnya dari daftar array; Namun, itu disimpan dengan bantuan pointer dalam daftar tertaut. Di sini kita membutuhkan dua lokasi memori untuk penyimpanan - satu untuk data, yang lain untuk pointer. Pointer membahas lokasi memori dari data berikutnya. Kami dapat dengan mudah memahami bahwa Daftar Tertaut tidak pernah menyimpan data secara berurutan; melainkan menggunakan mekanisme penyimpanan acak. Pointer adalah elemen kunci dalam menemukan lokasi data dalam memori.

Array Dinamis dan Daftar Tertaut

Kami telah membahas bagaimana kedua mekanisme penyimpanan dimasukkan ke dalam data dan kami dapat memberikan istilah 'array dinamis' untuk skema penyimpanan internal daftar array. Itu hanya menempatkan potongan data satu demi satu - karena itu namanya - sedangkan daftar tertaut menggunakan daftar internal dengan bantuan pointer untuk melacak item berikutnya. Oleh karena itu, ia menggunakan daftar tertaut internal, seperti daftar tautan tunggal atau ganda untuk menunjukkan kepada kami data berikutnya.

Penggunaan memori

Karena daftar array hanya menyimpan data aktual, kami hanya membutuhkan ruang untuk data yang kami simpan. Sebaliknya, dalam daftar tertaut, kami juga menggunakan pointer. Oleh karena itu, dua lokasi memori diperlukan, dan kita dapat mengatakan bahwa daftar tertaut mengkonsumsi lebih banyak memori daripada daftar array. Sisi yang menguntungkan dari daftar tertaut adalah tidak pernah membutuhkan lokasi memori yang berkelanjutan untuk menyimpan data kami, sebagai lawan dari daftar array. Pointer mampu memegang posisi lokasi data berikutnya, dan kami bahkan dapat menggunakan slot memori yang lebih kecil yang tidak kontinu. Ketika datang ke penggunaan memori, pointer memainkan peran utama dalam daftar tertaut, dan begitu pula keefektifannya.

Ukuran daftar array awal dan daftar tertaut

Dengan daftar array, bahkan daftar kosong membutuhkan ukuran 10, tetapi dengan daftar tertaut, kami tidak membutuhkan ruang yang begitu besar. Kita dapat membuat daftar tertaut kosong dengan ukuran 0. Nanti, kita dapat meningkatkan ukuran sesuai kebutuhan.

Pengambilan data

Pengambilan data lebih sederhana dalam daftar array karena menyimpan secara berurutan. Yang dilakukan hanyalah mengidentifikasi lokasi data pertama; Dari sana, lokasi berikutnya diakses secara berurutan untuk mengambil sisanya. Itu menghitung seperti posisi data pertama + 'n', di mana 'n' adalah urutan data dalam daftar array. Daftar tertaut mengacu pada penunjuk awal untuk menemukan lokasi data pertama, dan dari sana ia merujuk pointer yang terkait dengan setiap data untuk menemukan lokasi data berikutnya. Proses pengambilan terutama tergantung pada pointer di sini, dan mereka secara efektif menunjukkan kepada kita lokasi data berikutnya.

Akhir data

Daftar array menggunakan nilai nol untuk menandai akhir data, sedangkan daftar tertaut menggunakan penunjuk nol untuk tujuan ini. Segera setelah sistem mengenali data nol, daftar array menghentikan pengambilan data berikutnya. Dengan cara yang sama, penunjuk nol menghentikan sistem dari melanjutkan ke pengambilan data berikutnya.

Reverse traversal

Daftar Tertaut memungkinkan kita untuk melintasi arah terbalik dengan bantuan DescendentIterator (). Namun, kami tidak memiliki fasilitas seperti itu dalam daftar array - traversal terbalik menjadi masalah di sini.

Sintaksis

Mari kita lihat sintaks Java dari kedua mekanisme penyimpanan.

Pembuatan Daftar Array:

Daftar ArrayLandSample = ArrayList baru ();

Menambahkan objek ke daftar array:

Contoh ArrayList.tambahkan ("name1");

Contoh ArrayList.tambahkan ("name2");

Ini adalah bagaimana daftar array yang dihasilkan akan terlihat seperti - [name1, name2].

Pembuatan Daftar Tertaut:

Daftar LinkedListSample = new LinkedList ();

Menambahkan objek ke daftar tertaut:

Contoh LinkedLand.tambahkan ("name3");

Contoh LinkedLand.tambahkan ("name4");

Ini adalah bagaimana daftar tertaut yang dihasilkan akan terlihat seperti - [name3, name4].

 Mana yang lebih baik untuk operasi GET atau pencarian?

Daftar array membutuhkan waktu (1) waktu untuk menjalankan pencarian data apa pun, sedangkan daftar tertaut membutuhkan u (n) untuk n^th Pencarian Data. Oleh karena itu, daftar array selalu menggunakan waktu konstan untuk pencarian data apa pun, tetapi dalam daftar yang ditautkan, waktu yang dibutuhkan tergantung pada posisi data. Oleh karena itu, daftar array selalu menjadi pilihan yang lebih baik untuk operasi GET atau pencarian.

Yang lebih baik untuk operasi penyisipan atau penambahan?

Baik daftar array dan daftar tertaut mengambil waktu untuk penambahan data. Tetapi jika array penuh, maka daftar array membutuhkan banyak waktu untuk mengubah ukurannya dan menyalin item ke yang lebih baru. Dalam kasus seperti itu, daftar yang ditautkan adalah pilihan yang lebih baik.

Mana yang lebih baik untuk operasi lepas?

Operasi Hapus membutuhkan waktu yang hampir sama di kedua daftar array dan daftar yang ditautkan. Dalam daftar array, operasi ini menghapus data dan kemudian menggeser posisi data untuk membentuk array yang lebih baru - dibutuhkan waktu O (n). Dalam daftar tertaut, operasi ini melintasi data tertentu dan mengubah posisi pointer untuk membentuk daftar yang lebih baru. Waktu untuk traversal dan pemindahan adalah O (n) di sini juga.

Yang lebih cepat?

Kami tahu bahwa daftar array menggunakan array internal untuk menyimpan data aktual. Oleh karena itu, jika ada data yang dihapus, maka semua data yang akan datang membutuhkan pergeseran memori. Jelas, ini membutuhkan banyak waktu dan memperlambat segalanya. Pergeseran memori seperti itu tidak diperlukan dalam daftar tertaut, seperti yang dilakukannya hanyalah mengubah lokasi pointer. Oleh karena itu, daftar tertaut lebih cepat dari daftar array dalam segala jenis penyimpanan data. Namun, ini murni tergantung pada jenis operasi, saya.e. Untuk operasi GET atau pencarian, daftar tertaut membutuhkan lebih banyak waktu daripada daftar array. Saat kita melihat kinerja keseluruhan, kita dapat mengatakan bahwa daftar yang ditautkan lebih cepat.

Kapan Menggunakan Daftar Array dan Daftar Tertaut?

Daftar array paling cocok untuk persyaratan data yang lebih kecil di mana memori kontinu tersedia. Tetapi ketika kita menangani sejumlah besar data, ketersediaan memori kontinu mengimplementasikan mekanisme penyimpanan data, apakah itu kecil atau besar. Selanjutnya, putuskan mana yang harus dipilih - daftar array atau daftar yang ditautkan. Anda dapat melanjutkan daftar array saat Anda hanya perlu penyimpanan dan pengambilan data. Tetapi daftar dapat membantu Anda melampaui itu dengan memanipulasi data. Setelah Anda memutuskan seberapa sering manipulasi data diperlukan, penting untuk memeriksa jenis pengambilan data apa yang biasanya Anda lakukan. Ketika hanya dapatkan atau cari, maka daftar array adalah pilihan yang lebih baik; Untuk operasi lain seperti penyisipan atau penghapusan, silakan dengan daftar tertaut.

Mari kita lihat perbedaan dalam bentuk tabel.