Daftar bertaut

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

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

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

Keuntungan dan kerugian

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

Jenis-jenis daftar berantai

Daftar bertaut tunggal

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

Daftar bertaut tunggal dengan tiap-tiap node yang terdiri atas dua elemen, data integer, dan elemen rujukan ke node berikutnya

Daftar bertaut ganda

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

Daftar bertaut ganda dengan tiap-tiap node yang terdiri atas tiga elemen, data integer, dan dua elemen rujukan ke node sebelum serta berikutnya

Daftar bertaut sirkular

Pada dua jenis daftar sebelumnya, node terakhir dalam daftar tersebut merujuk pada null yang artinya akhir dari sebuah daftar, begitu pula null sebagai rujukan node sebelumnya pada node pertama bila daftar yang dimaksudkan adalah daftar bertaut ganda. Pada daftar bertaut sirkular, 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 daftar bertaut ganda.

Daftar bertaut sirkular dengan menggunakan model implementasi daftar bertaut tungal. Node terakhir menyimpan rujukan pada node pertama

Lihat pula

• Daftar
• Larik
• Ilmu komputer

Rujukan

• Juan, Angel (2006) (pdf), Ch20 –Data Structures; ID06 - PROGRAMMING with JAVA (slide part of the book “Big Java”, by CayS. Horstmann), hlm. 3, http://www.uoc.edu/in3/emath/docs/java/ch20.pdf 
• "Definition of a linked list". National Institute of Standards and Technology. 16 Agustus 2004. http://nist.gov/dads/HTML/linkedList.html. Diakses pada 14 Desember 2004. 
• 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. http://www-formal.stanford.edu/jmc/recursive.html. 
• 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". Stanford University. http://cslibrary.stanford.edu/103/LinkedListBasics.pdf. Diakses pada 21 September 2009. 
• 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". http://isis.poly.edu/kulesh/stuff/src/klist/. Diakses pada 21 September 2009.