Array dan Senarai Berantai

Array dan senarai berantai adalah dua cara dasar untuk menyimpan urutan elemen: array menempatkannya dalam memori yang berdekatan untuk akses terindeks waktu-konstan, sementara senarai berantai menghubungkannya melalui pointer untuk penyisipan dan penghapusan yang murah.

Definition

Array menyimpan elemen dalam lokasi memori yang berdekatan yang diindeks berdasarkan posisi, memungkinkan akses acak waktu-konstan; senarai berantai menyimpan elemen dalam node terpisah yang masing-masing memegang referensi ke node berikutnya (dan mungkin sebelumnya), memungkinkan penyisipan atau penghapusan waktu-konstan jika diberikan referensi node.

Scope

Topik ini mencakup struktur linier berbasis urutan dan tipe data abstrak yang dibangun di atasnya — array statis dan dinamis, senarai berantai tunggal dan ganda, serta ADT tumpukan (stack) dan antrean (queue). Ini membandingkan biaya akses, penyisipan, dan penghapusannya, mencakup pengubahan ukuran array dinamis dan analisis amortisasinya, serta menjelaskan konsekuensi tata letak memori seperti lokalitas cache. Ini tidak termasuk struktur asosiatif dan hierarkis yang tercakup dalam tabel hash dan pohon pencarian.

Core questions

• Kapan penyimpanan berdekatan (array) mengungguli penyimpanan yang terhubung dengan pointer (senarai)?
• Bagaimana array dinamis mencapai penambahan waktu-konstan teramortisasi meskipun ada pengubahan ukuran sesekali?
• Apa saja pertukaran biaya antara array dan senarai berantai untuk penyisipan, penghapusan, dan akses?
• Bagaimana tumpukan dan antrean diimplementasikan di atas struktur ini?
• Bagaimana tata letak memori memengaruhi kinerja dunia nyata melalui perilaku cache?

Key concepts

• memori berdekatan
• akses terindeks
• pengubahan ukuran array dinamis
• senarai berantai tunggal dan ganda
• tumpukan (LIFO)
• antrean (FIFO)
• biaya teramortisasi
• lokalitas cache

Key theories

Akses acak versus hubungan sekuensial

Array mendukung akses terindeks O(1) tetapi penyisipan atau penghapusan O(n) di tengah, sedangkan senarai berantai mendukung penyambungan O(1) jika diberikan node tetapi akses O(n) berdasarkan posisi; pilihan yang tepat bergantung pada campuran operasi.

Pertumbuhan teramortisasi array dinamis

Array dinamis yang menggandakan kapasitasnya saat penuh melakukan penyalinan O(n) sesekali tetapi teramortisasi menjadi O(1) per penambahan selama urutan operasi apa pun, dengan metode agregat atau potensial.

Clinical relevance

Array dan senarai adalah substrat dari hampir setiap program: array dinamis mengimplementasikan tipe daftar/vektor default di sebagian besar bahasa, antrean mendasari penjadwalan dan pencarian lebar-pertama (breadth-first search), tumpukan mendasari manajemen panggilan fungsi dan evaluasi ekspresi, dan pertukaran array-versus-senarai adalah keputusan desain praktis rutin yang memengaruhi kinerja.

History

Array adalah salah satu struktur data paling awal, hadir dalam bahasa pemrograman pertama, dan senarai berantai diperkenalkan untuk pemrosesan simbolik dan daftar (terutama dalam IPL Newell, Shaw, dan Simon dan kemudian Lisp) pada akhir 1950-an. Perlakuan sistematis Knuth dalam The Art of Computer Programming menetapkan analisis kanoniknya.

Key figures

• Donald Knuth
• Robert Sedgewick

Seminal works

• knuth1997vol1
• cormen2009

Frequently asked questions

Mengapa menggunakan senarai berantai jika array mendukung akses acak yang cepat?

Senarai berantai memungkinkan penyisipan atau penghapusan dalam waktu konstan jika diberikan referensi ke node, tanpa menggeser elemen lain, yang tidak dapat dilakukan array di tengah. Ini berguna ketika urutan sering berubah dan akses acak posisi tidak diperlukan.

Mengapa penambahan array dianggap waktu konstan jika pengubahan ukuran menyalin semuanya?

Pengubahan ukuran jarang terjadi karena kapasitas biasanya berlipat ganda, sehingga total pekerjaan penyalinan selama n penambahan sebanding dengan n. Jika disebarkan ke semua penambahan, ini memberikan biaya konstan teramortisasi per penambahan meskipun pengubahan ukuran individual adalah O(n).