Senarai berantai

Senarai berantai atau daftar bertaut (bahasa Inggris: linked list) dalam ilmu komputer merupakan sebuah struktur data yang digunakan untuk menyimpan sejumlah objek data biasanya secara terurut sehingga memungkinkan penambahan, pengurangan, dan pencarian atas unsur data yang tersimpan dalam senarai dilakukan secara lebih efektif. Pada praktiknya sebuah struktur data memiliki unsur yang digunakan untuk saling menyimpan rujukan antara satu dengan lainnya sehingga membentuk sebuah senarai abstrak, tiap-tiap unsur yang terdapat pada senarai abstrak ini sering kali disebut sebagai node. karena mekanisme rujukan yang saling terkait inilah disebut sebagai senarai berantai.

Sebuah senarai berantai dengan tiap-tiap node yang terdiri atas dua unsur, data integer, dan unsur rujukan ke node berikutnya

Senarai berantai merupakan bentuk struktur data paling umum dan sederhana yang banyak digunakan untuk mengimplementasikan model struktur data lainnya, termasuk antrian, stack, ataupun larik asosiatif.

Keuntungan dan kerugian

Keuntungan utama pemanfaatan senarai berantai dibandingkan larik, ataupun senarai biasa adalah kemudahan dan efektivitas kerja yang lebih baik dalam hal menambah, mengurangi, serta mencari suatu unsur/node yang terdapat dalam senarai. Hal tersebut dimungkinkan karena unsur-unsur yang terdapat pada sebuah senarai berantai tidak ditempatkan pada sebuah blok memori komputer seperti halnya larik ataupun senarai biasa, melainkan tiap-tiap unsur/node tersebut tersimpan dalam blok memori terpisah, penambahan, pengurangan, ataupun penggantian node dapat dilakukan dengan mengubah unsur rujukan atas tiap-tiap node yang terkait. Kerugiannya, sebuah senarai berantai tidak memungkinkan pengaksesan unsur secara acak, dalam artian untuk dapat mengakses node ke tiga pada contoh di atas harus dilakukan dengan cara mengunjungi unsur-unsur sebelumnya, dimulai dari unsur pertama, ke dua, seterusnya hingga pada lokasi unsur yang dimaksudkan.

Jenis-jenis senarai berantai

Senarai tunggal

Bila struktur data sebuah node hanya memiliki satu tautan atas node berikutnya dalam sebuah senarai, maka senarai tersebut dinamakan sebagai senarai tunggal.

Senarai tunggal dengan tiap-tiap node yang terdiri atas dua unsur, data integer, dan unsur rujukan ke node berikutnya

Senarai ganda

Berbeda halnya dengan senarai tunggal, pada senarai ganda, struktur data atas tiap-tiap node memiliki rujukan pada node sebelum dan berikutnya. Sebagian algoritme membutuhkan taut ganda, contohnya sorting dan reverse traversing.

Senarai ganda dengan tiap-tiap node yang terdiri atas tiga unsur, data integer, dan dua unsur rujukan ke node sebelum serta berikutnya

Senarai sirkuler

Pada dua jenis senarai sebelumnya, node terakhir dalam senarai tersebut merujuk pada null yang artinya akhir dari sebuah senarai, begitu pula null sebagai rujukan node sebelumnya pada node pertama bila senarai yang dimaksudkan adalah senarai ganda. Pada senarai sirkuler, informasi rujukan pada node terakhir akan merujuk pada node pertama, dan rujukan pada node pertama akan merujuk pada node terakhir bila yang digunakan sebagai dasar implementasi adalah senarai ganda.

Senarai sirkuler dengan menggunakan model implementasi senarai tungal. Node terakhir menyimpan rujukan pada node pertama

Lihat pula

Rujukan

Juan, Angel (2006), Ch20 –Data Structures; ID06 - PROGRAMMING with JAVA (slide part of the book “Big Java”, by CayS. Horstmann) (PDF), hlm. 3, diarsipkan dari versi asli (pdf) tanggal 2012-01-06, diakses tanggal 2011-07-13
"Definition of a linked list". National Institute of Standards and Technology. 2004-08-16. Diakses tanggal 2004-12-14.
Antonakos, James L. (1999). Practical Data Structures Using C/C++. Prentice-Hall. hlm. 165–190. ISBN 0-13-280843-9.
Collins, William J. (2005) [2002]. Data Structures and the Java Collections Framework. New York: McGraw Hill. hlm. 239–303. ISBN 0-07-282379-8.
Cormen, Thomas H. (2003). Introduction to Algorithms. MIT Press. hlm. 205–213 & 501–505. ISBN 0-262-03293-7.
Cormen, Thomas H. (2001). "10.2: Linked lists". Introduction to Algorithms (edisi ke-2md). MIT Press. hlm. 204–209. ISBN 0-262-03293-7.
Green, Bert F. Jr. (1961). "Computer Languages for Symbol Manipulation". IRE Transactions on Human Factors in Electronics (2): 3–8.
McCarthy, John (1960). "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I". Communications of the ACM.
Knuth, Donald (1997). "2.2.3-2.2.5". Fundamental Algorithms (edisi ke-3rd). Addison-Wesley. hlm. 254–298. ISBN 0-201-89683-4.
Newell, Allen (1957). "Programming the Logic Theory Machine". Proceedings of the Western Joint Computer Conference: 230–240.
Parlante, Nick (2001). "Linked list basics" (PDF). Stanford University. Diakses tanggal 2009-09-21.
Sedgewick, Robert (1998). Algorithms in C. Addison Wesley. hlm. 90–109. ISBN 0-201-31452-5.
Shaffer, Clifford A. (1998). A Practical Introduction to Data Structures and Algorithm Analysis. New Jersey: Prentice Hall. hlm. 77–102. ISBN 0-13-660911-2.
Wilkes, Maurice Vincent (1964). "An Experiment with a Self-compiling Compiler for a Simple List-Processing Language". Annual Review in Automatic Programming. Pergamon Press. 4 (1).
Wilkes, Maurice Vincent (1964). "Lists and Why They are Useful". Proceeds of the ACM National Conference, Philadelphia 1964. ACM (P-64): F1–1.
Shanmugasundaram, Kulesh (2005-04-04). "Linux Kernel Linked List Explained". Diarsipkan dari versi asli tanggal 2009-09-25. Diakses tanggal 2009-09-21.