senarai berantai (senarai bertaut atau daftar bertaut 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 senarai dilakukan secara lebih efektif.
pada praktiknya sebuah struktur data memiliki elemen yang digunakan untuk saling menyimpan rujukan antara satu dengan lainnya sehingga membentuk sebuah senarai abstrak, tiap-tiap elemen yang terdapat pada senarai abstrak ini seringkali disebut sebagai node.
karena mekanisme rujukan yang saling terkait inilah disebut sebagai senarai berantai.
berkas:singly-linked-list.svgsebuah senarai berantai dengan tiap-tiap node yang terdiri atas dua elemen, data integer, dan elemen 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 assosiatif.
keuntungan dan kerugian
keuntungan utama pemanfaatan senarai berantai dibandingkan larik, ataupun senarai biasa adalah kemudahan dan efektifitas kerja yang lebih baik dalam hal menambah, mengurangi, serta mencari suatu elemen/node yang terdapat dalam senarai.
hal tersebut dimungkinkan karena elemen-elemen yang terdapat pada sebuah senarai berantai tidak ditempatkan pada sebuah blok memori komputer seperti halnya larik ataupun senarai 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 senarai 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 senarai berantai
bila struktur data sebuah node hanya memiliki satu tautan atas node berikutnya dalam sebuah senarai, maka senarai tersebut dinamakan sebagai senarai tunggal.
berkas:singly-linked-list.svgsenarai tunggal dengan tiap-tiap node yang terdiri atas dua elemen, data integer, dan elemen rujukan ke node berikutnya
berbeda halnya dengan senarai tunggal, pada senarai ganda, struktur data atas tiap-tiap node memiliki rujukan pada node sebelum dan berikutnya.
sebagian algoritma membutuhkan taut ganda, contohnya sorting dan reverse traversing.
berkas:doubly-linked-list.svgsenarai ganda dengan tiap-tiap node yang terdiri atas tiga elemen, data integer, dan dua elemen rujukan ke node sebelum serta berikutnya
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.
berkas:circularly-linked-list.svgsenarai sirkuler dengan menggunakan model implementasi senarai tungal.
node terakhir menyimpan rujukan pada node pertama