Perbezaan antara tatasusunan dan senarai yang dipautkan

Senarai Arrays vs Linked

Array adalah struktur data yang paling biasa digunakan untuk menyimpan koleksi elemen. Kebanyakan bahasa pengaturcaraan menyediakan kaedah untuk mengisytiharkan array dan elemen akses dengan mudah. Senarai yang dipautkan, senarai yang lebih tepat berkaitan, juga merupakan struktur data yang boleh digunakan untuk menyimpan koleksi elemen. Ia terdiri daripada urutan nod dan setiap nod mempunyai rujukan kepada nod seterusnya dalam urutan.

Ditunjukkan dalam Rajah 1, adalah sekeping kod yang biasanya digunakan untuk mengisytiharkan dan memberikan nilai kepada array. Rajah 2 menggambarkan bagaimana array kelihatan seperti dalam ingatan.

Kod di atas mentakrifkan array yang boleh menyimpan 5 bilangan bulat dan mereka diakses menggunakan indeks 0 hingga 4. Satu harta penting dalam array adalah bahawa keseluruhan array diperuntukkan sebagai satu blok memori dan setiap elemen mendapat ruang sendiri dalam array. Setelah array ditakrifkan, saiznya tetap. Oleh itu, jika anda tidak pasti mengenai saiz array pada masa penyusunan, anda perlu menentukan array yang cukup besar untuk berada di sisi yang selamat. Tetapi, kebanyakan masa kita sebenarnya akan menggunakan kurang bilangan elemen daripada yang telah kita peruntukkan. Oleh itu, sejumlah besar memori sebenarnya sia -sia. Sebaliknya jika "array cukup besar" sebenarnya tidak cukup besar, program itu akan terhempas.

Senarai yang dipautkan memperuntukkan memori ke unsur -unsurnya secara berasingan dalam blok memori sendiri dan struktur keseluruhan diperoleh dengan menghubungkan unsur -unsur ini sebagai pautan dalam rantai. Setiap elemen dalam senarai yang dipautkan mempunyai dua bidang seperti yang ditunjukkan dalam Rajah 3. Medan data memegang data sebenar yang disimpan dan medan seterusnya memegang rujukan kepada elemen seterusnya dalam rantai. Unsur pertama senarai yang dipautkan disimpan sebagai ketua senarai yang dipautkan.

Rajah 3: Elemen senarai yang dipautkan

Rajah 4 menggambarkan senarai yang dipautkan dengan tiga elemen. Setiap elemen menyimpan datanya dan semua elemen kecuali yang terakhir menyimpan rujukan kepada elemen seterusnya. Elemen terakhir memegang nilai null dalam bidang seterusnya. Sebarang elemen dalam senarai boleh diakses dengan bermula di kepala dan mengikuti penunjuk seterusnya sehingga anda memenuhi elemen yang diperlukan.

Walaupun array dan senarai yang dipautkan adalah serupa dalam erti kata bahawa kedua -dua mereka digunakan untuk menyimpan koleksi unsur -unsur, mereka menanggung perbezaan kerana strategi yang mereka gunakan untuk memperuntukkan ingatan kepada unsur -unsurnya. Array memperuntukkan memori ke semua elemennya sebagai satu blok dan saiz array harus ditentukan pada masa runtime. Ini akan menjadikan array tidak cekap dalam situasi di mana anda tidak mengetahui saiz array pada masa penyusunan. Oleh kerana senarai yang dipautkan memperuntukkan memori ke unsur -unsurnya secara berasingan, ia akan menjadi sangat efisien dalam situasi di mana anda tidak mengetahui saiz senarai pada masa penyusunan. Perisytiharan dan mengakses elemen dalam senarai yang dipautkan tidak akan terus maju berbanding dengan cara anda mengakses elemen secara langsung dalam array menggunakan indeksnya.