Perbezaan antara senarai array dan senarai yang dipautkan

Bagaimana data disimpan?

Senarai Array dan Senarai Berkaitan adalah istilah biasa ketika datang ke penyimpanan data dan pengambilan semula. Walaupun terdapat banyak peranti penyimpanan, akhirnya, mereka bergantung pada mekanisme penyimpanan. Kedua -dua mekanisme penyimpanan ini meletakkan data anda dalam peranti penyimpanan dan mengambilnya apabila diperlukan. Mari kita lihat bagaimana mereka menyimpan data dalam ingatan mereka. Senarai Array menggunakan storan berurutan, dan kepingan data disimpan satu demi satu. Ini mungkin merupakan bentuk penyimpanan yang lebih mudah - ia mengelakkan kekeliruan. Ya, kita boleh mengambil item atau data seterusnya dari lokasi memori seterusnya senarai array; Walau bagaimanapun, ia disimpan dengan bantuan petunjuk dalam senarai yang dipautkan. Di sini kita memerlukan dua lokasi memori untuk penyimpanan - satu untuk data, yang lain untuk penunjuk. Penunjuk menangani lokasi memori data seterusnya. Kami dapat dengan mudah memahami bahawa senarai yang dipautkan tidak pernah menyimpan data secara berurutan; Sebaliknya, ia menggunakan mekanisme penyimpanan rawak. Petunjuk adalah elemen utama dalam mencari lokasi data dalam ingatan.

Arahan dinamik dan senarai yang dipautkan

Kami telah membincangkan bagaimana kedua -dua mekanisme penyimpanan dimasukkan ke dalam data dan kami dapat memberikan istilah 'array dinamik' untuk skim penyimpanan dalaman senarai array. Ia hanya meletakkan kepingan data satu demi satu - oleh itu nama - sedangkan senarai yang dipautkan menggunakan senarai dalaman dengan bantuan petunjuk untuk mengesan item seterusnya. Oleh itu, ia menggunakan senarai dikaitkan dalaman, seperti senarai yang berkaitan dengan tunggal atau berganda untuk menunjukkan kepada kami data seterusnya.

Penggunaan memori

Oleh kerana senarai array hanya menyimpan data sebenar, kami memerlukan ruang hanya untuk data yang kami simpan. Sebaliknya, dalam senarai yang dipautkan, kami juga menggunakan petunjuk. Oleh itu, dua lokasi memori diperlukan, dan kita boleh mengatakan bahawa senarai yang dipautkan menggunakan lebih banyak memori daripada senarai array. Sisi yang berfaedah dalam senarai yang dipautkan adalah bahawa ia tidak memerlukan lokasi memori yang berterusan untuk menyimpan data kami, berbanding dengan senarai array. Petunjuk mampu memegang kedudukan lokasi data seterusnya, dan kami juga dapat menggunakan slot memori yang lebih kecil yang tidak berterusan. Ketika datang ke penggunaan memori, petunjuk memainkan peranan utama dalam senarai yang dipautkan, dan begitu juga keberkesanannya.

Saiz senarai array awal dan senarai yang dipautkan

Dengan senarai array, walaupun senarai kosong memerlukan saiz 10, tetapi dengan senarai yang dipautkan, kami tidak memerlukan ruang yang begitu besar. Kita boleh membuat senarai berkaitan kosong dengan saiz 0. Kemudian, kita dapat meningkatkan saiz yang diperlukan.

Pengambilan data

Pengambilan data lebih mudah dalam senarai array kerana ia menyimpan secara berurutan. Apa yang dilakukan adalah mengenal pasti lokasi data pertama; Dari sana, lokasi seterusnya diakses secara berurutan untuk mendapatkan yang lain. Ia mengira seperti kedudukan data pertama + 'n', di mana 'n' adalah urutan data dalam senarai array. Senarai yang dipautkan merujuk penunjuk awal untuk mencari lokasi data pertama, dan dari sana ia merujuk penunjuk yang berkaitan dengan setiap data untuk mencari lokasi data seterusnya. Proses pengambilan kebanyakannya bergantung kepada petunjuk di sini, dan mereka secara efektif menunjukkan kepada kami lokasi data seterusnya.

Akhir data

Senarai Array menggunakan nilai null untuk menandakan akhir data, sedangkan senarai yang dipautkan menggunakan penunjuk null untuk tujuan ini. Sebaik sahaja sistem mengiktiraf data null, senarai array menghentikan pengambilan data seterusnya. Dengan cara yang sama, penunjuk null menghentikan sistem dari meneruskan ke pengambilan data seterusnya.

Traversal terbalik

Senarai yang dipautkan membolehkan kami melintasi arah terbalik dengan bantuan DescendingIterator (). Walau bagaimanapun, kami tidak mempunyai kemudahan sedemikian dalam senarai array - Traversal terbalik menjadi masalah di sini.

Sintaks

Mari kita lihat sintaks Java dari kedua -dua mekanisme penyimpanan.

Penciptaan Senarai Array:

Senaraikan ArrayListSample = New ArrayList ();

Menambah objek ke senarai array:

ArrayListSample.tambah ("nama1");

ArrayListSample.tambah ("name2");

Ini adalah bagaimana senarai array yang dihasilkan akan kelihatan seperti - [name1, name2].

Penciptaan senarai yang dipautkan:

Senarai LinkedListSample = New LinkedList ();

Menambah objek ke senarai yang dipautkan:

LinkedListSample.tambah ("nama3");

LinkedListSample.tambah ("nama4");

Ini adalah bagaimana senarai yang dihasilkan akan kelihatan seperti - [name3, name4].

 Yang lebih baik untuk mendapatkan operasi mendapatkan atau carian?

Senarai array mengambil masa o (1) untuk menjalankan sebarang carian data, sedangkan senarai yang dipautkan mengambil u o (n) untuk n^th carian data. Oleh itu, senarai array sentiasa menggunakan masa yang berterusan untuk sebarang carian data, tetapi dalam senarai yang dipautkan, masa yang diambil bergantung pada kedudukan data. Oleh itu, senarai array selalu menjadi pilihan yang lebih baik untuk mendapatkan atau mencari operasi.

Yang lebih baik untuk operasi penyisipan atau penambahan?

Kedua -dua senarai array dan senarai yang dipautkan mengambil o (1) masa untuk penambahan data. Tetapi jika array penuh, maka senarai array memerlukan banyak masa untuk mengubah saiznya dan menyalin item tersebut kepada yang lebih baru. Dalam kes sedemikian, senarai yang dipautkan adalah pilihan yang lebih baik.

Yang lebih baik untuk menghapuskan operasi?

Operasi mengalih keluar hampir sama dengan jumlah masa yang sama dalam kedua -dua senarai array dan senarai yang dipautkan. Dalam senarai array, operasi ini memadamkan data dan kemudian mengalihkan kedudukan data untuk membentuk array yang lebih baru - diperlukan o (n) masa. Dalam senarai yang dipautkan, operasi ini melintasi data tertentu dan perubahan kedudukan penunjuk untuk membentuk senarai yang lebih baru. Masa untuk traversal dan penyingkiran adalah o (n) di sini juga.

Yang lebih cepat?

Kami tahu bahawa senarai array menggunakan array dalaman untuk menyimpan data sebenar. Oleh itu, jika ada data yang dipadam, maka semua data yang akan datang memerlukan peralihan memori. Jelas sekali, ini memerlukan banyak masa dan melambatkan perkara. Peralihan memori seperti ini tidak diperlukan dalam senarai yang dipautkan, kerana semua itu adalah mengubah lokasi penunjuk. Oleh itu, senarai yang dipautkan lebih cepat daripada senarai array dalam apa -apa jenis penyimpanan data. Walau bagaimanapun, ini semata -mata bergantung kepada jenis operasi, i.e. Untuk operasi mendapatkan atau carian, senarai yang dipautkan memerlukan lebih banyak masa daripada senarai array. Apabila kita melihat prestasi keseluruhan, kita boleh mengatakan bahawa senarai yang dipautkan lebih cepat.

Bilakah menggunakan senarai array dan senarai yang dipautkan?

Senarai Array paling sesuai untuk keperluan data yang lebih kecil di mana memori berterusan tersedia. Tetapi apabila kita menangani sejumlah besar data, ketersediaan memori berterusan melaksanakan mekanisme penyimpanan data, sama ada kecil atau besar. Seterusnya, tentukan mana yang hendak dipilih - senarai array atau senarai yang dipautkan. Anda boleh meneruskan senarai array apabila anda hanya memerlukan penyimpanan dan pengambilan data. Tetapi senarai dapat membantu anda melampaui itu dengan memanipulasi data. Sebaik sahaja anda memutuskan berapa kerap manipulasi data diperlukan, penting untuk memeriksa jenis pengambilan data yang biasanya anda lakukan. Apabila ia hanya mendapatkan atau mencari, maka senarai array adalah pilihan yang lebih baik; Untuk operasi lain seperti penyisipan atau penghapusan, teruskan dengan senarai yang dipautkan.

Mari kita lihat perbezaan dalam bentuk jadual.