Dari blog Pak Risman yang berjudul "What is your favorite data structure?", saya coba untuk menjawab pertanyaan "What is your favorite data structure?". Dari berbagai struktur data yang pernah saya pelajari, seranai berantai (linked list) adalah struktur data yang paling saya sukai.
Seranai berantai menjadi favorit saya karena menjadi dasar struktur data pada pemprograman komputer. Berbagai struktur data yang lain dapat dibuat dengan seranai berantai, seperti larik (array), antrian (queue), tumpukan (stack), pohon (tree), dan lain sebagainya.
Pada dasarnya, seranai berantai merupakan rangkaian beberapa simpul (node) dengan masing-masing simpul mengandung data dan referensi (taut [link]) ke simpul lainnya. Seranai berantai dapat digambarkan seperti gambar di bawah.
Gambar 1. Seranai berantai
Kelebihan seranai berantai dibandingkan dengan seranai (list) biasa adalah sangat dinamis dan efisien dalam pengalokasian sumber daya memory. Urutan Seranai berantai tidak harus sama dengan urutan data yang tersimpan di memory. Urutan simpul dapat diubah atau dibalik hanya dengan merubah referensinya saja, tanpa memindahkan lokasi objek tersebut dalam memory. Pengaksesan simpul seranai berantai tidak bisa dilakukan secara acak, simpul hanya bisa diakses dengan menelusuri jalur maju atau mundur. Penambahan dapat dilakukan dengan mengaitkan simpul baru ke dalam rantai. Penghapusan dapat dilakukan dengan memutus sambungan simpul dari rantai dan melepaskan alokasi memory untuk simpul tersebut. Beberapa jenis seranai berantai adalah seranai berantai tunggal (singly-linked list), seranai berantai ganda (doubly-linked list) dan seranai berantai melingkar (circularly-linked list).
Seranai berantai dapat dibuat dengan berbagai macam bahasa pemprograman seperti Pascal, C, C++, C#, Java dan bahkan Assembler. Pada .NET Framework 2.0 terdapat class generic yang khusus menangani seranai berantai, yaitu LinkedList dan LinkedListNode. Kedua class tersebut terdapat dalam namespace System.Collections.Generic.
Seranai Berantai Linier
Seranai Berantai Tunggal
Seranai berantai paling sederhana adalah seranai berantai tunggal (singly-linked list, atau disingkat slist). Pada seranai berantai ini, tiap simpul hanya memiliki satu taut (link) yang merujuk ke simpul berikutnya atau nilai null pada akhir simpul. Seranai berantai ini hanya bisa diakses maju dari awal simpul ke akhir simpul, seperti ditunjukkan pada Gambar 1.
Pembuatan simpul
Simpul dapat didefinisikan menggunakan struct (C), Record (Pascal) atau class. Dalam tulisan ini, saya akan paparkan bagaimana membuat seranai berantai menggunakan C#. Untuk membuat simpul kita dapat mendefinisikan objek LinkedListNode (.NET 2.0). Pada contoh berikut tidak digunakan objek LinkedListNode dengan maksud untuk memperjelas pemaparan. Berikut contoh deklarasi class simpul menggunakan C#.
class Node
{
public int value;
public Node next;
public Node(int value, Node next)
{
this.value = value;
this.next = next;
}
}
Code 1. Class Node, simpul untuk seranai berantai tunggal
Pada contoh di atas, class Node memiliki dua object value untuk data dan next yang mengacu pada class Node itu sendiri. Contoh berikit kita akan membuat tiga buah simpul dan kemudian dirangkai dalam satu rangkaian seranai berantai.
Node node1 = new Node(1, null); // buat node1
Node node2 = new Node(2, node1); // buat node2 dan sambungkan ke node1
Node node3 = new Node(3, node2); // buat node3 dan sambungkan ke node2
Code 2. Pembuatan simpul seranai berantai
Pembuatan simpul disini dilakukan dengan membuat instance class baru. Pertama dibuat node1 yang berisi nilai 1 dan taut berisi null. Simpul kedua ditambahkan dengan nilai 2 dan taut merujuk pada node1. Simpul berikutnya berisi nilai 3 dan taut merujuk pada node2. Kode di atas dapat diilustrasikan dengan gambar di bawah ini.
Gambar 2. Seranai berantai tunggal
Penambahan simpul
Pada contoh sebelumnya, masing-masing simpul memiliki nama sendiri yang dapat diakses dengan nama objek (node1, node2, node3). Hal ini tidak dapat dilakukan untuk seranai berantai dinamis, karena tidak bisa memberikan nama pada setiap simpul. Mari lihat contoh berikut.
Node node, newNode; // deklarasi simpul node dan newNode
node = new Node(1, null); // buat simpul node dengan nilai 1
newNode = new Node(2, null); // buat simpul baru (newNode) dengan nilai 2
newNode.next = node; // sambungkan simpul newNode ke simpul node
node = newNode; // pindahkan referensi objek node ke objek newNode
newNode = new Node(3, null); // buat simpul baru (newNode) dengan nilai 2
newNode.next = node; // sambungkan simpul newNode ke simpul node
node = newNode; // pindahkan referensi objek node ke objek newNode
Code 3. Penambahan simpul di awal seranai berantai
Contoh di atas menghasilkan seranai berantai yang sama dengan contoh sebelumnya. Perbedaannya pada bagaimana cara menambahkan simpul baru pada seranai berantai. Di sini, dibutuhkan simpul bantu (newNode) untuk menambahkan simpul di awal seranai berantai. Dengan cara tersebut, berapapun panjang seranai berantai dapat ditambahkan.
Langkah-langkah penambahan simpul di awal seranai berantai dilakukan sebagai berikut.
- Pada mulanya dibuat simpul (node) dengan nilai 1
- Selanjutnya dibuat simpul baru (newNode) dengan nilai 2
- Simpul baru disambungkan ke simpul sebelumnya (node)
- Referensi objek simpul awal (node) disamakan dengan simpul baru (newNode).
- Untuk menambahkan simpul lagi, ulangi langkah 2 sampai 4.
Untuk lebih memahami bagaimana cara menambahkan simpul baru di awal seranai berantai, dapat dilihat ilustrasi berikut.
// buat simpul node dengan nilai 1
node = new Node(1, null); |
 |
// buat simpul baru (newNode) dengan nilai 2
newNode = new Node(2, null); |
 |
// sambungkan simpul newNode ke simpul node
newNode.next = node; |
 |
// pindahkan referensi objek node ke objek newNode
node = newNode; |
 |
Ilustrasi 1. Penambahan simpul pada seranai berantai
Untuk memudahkan penambahan simpul baru di awal seranai berantai dapat dibuat method seperti contoh kode berikut.
static void insertBegining(int value, Node node)
{
Node newNode = new Node(value, null); // buat simpul baru (newNode)
newNode.next = node; // sambungkan simpul newNode ke simpul node
node = newNode; // jadikan newNode sebagai awal simpul
}
Code 4. Method insertBegining untuk menambahkan simpul pada awal seranai berantai
Simpul ditambahkan pada seranai berantai dengan cara sebagai berikut.
node = new Node(1, null);// buat simpul node dengan nilai 1
insertBegining(2, node); // tambahkan simpul dengan nilai 2
insertBegining(3, node); // tambahkan simpul dengan nilai 3
Code 5. Contoh penggunaan method insertBegining
Dari contoh di atas, seranai berantai yang dihasilkan dapat digambarkan pada gambar berikut.
Gambar 3. Penambahan simpul pada awal seranai berantai
Untuk menambahkan simpul di akhir seranai berantai dibutuhkan sebuah simpul bantu yang dinamakan simpul ekor (Tail). Simpul ekor ini yang digunakan sebagai acuan akhir dari seranai berantai.
Langkah-langkah penambahan simpul di akhir seranai berantai dilakukan sebagai berikut.
- Pada mulanya dibuat simpul (node) dengan nilai 1 dan simpul ekor (tail), sambungkan tail.next ke node.
- Selanjutnya dibuat simpul baru (newNode) dengan nilai 2
- Simpul yang direferensikan oleh tail.next disambungkan ke simpul baru(newNode)
- Simpul ekor (tail) disambungkan ke simpul terakhir yang merupakan simpul baru (newNode).
- Untuk menambahkan simpul lagi, ulangi langkah 2 sampai 4.
Untuk lebih memahami bagaimana cara menambahkan simpul baru di akhir seranai berantai, dapat dilihat ilustrasi berikut.
Ilustrasi 1. Penambahan simpul di akhir seranai berantai
Untuk memudahkan penambahan simpul baru di akhir seranai berantai dapat dibuat method seperti contoh kode berikut.
static void insertEnding(int value, Node tail)
{
Node newNode = new Node(value, null); // buat simpul baru (newNode)
tail.next.next = newNode; // sambungkan simpul terakir ke simpul baru (newNode)
tail.next = newNode; // pindahkan taut simpul tail ke simpul terakir
}
Code 4. Method insertBegining untuk menambahkan simpul pada akhir seranai berantai
Pembacaan simpul
Pembacaan simpul pada seranai berantai tunggal dilakukan secara berurutan dari awal sampai akhir. Pembacaan dilakukan dengan simpul bantu sebagai cursor yang menunjukkan posisi pembacaan saat ini.
static void PrintNodes(Node node)
{
Node currentNode = node;
while (currentNode != null)
{
Console.WriteLine(currentNode.value);
currentNode = currentNode.next;
}
}
Code 5. Pembacaan simpul
Pada kode di atas, digunakan simpul bantu currentNode yang menunjukkan posisi pembacaan. Langhak-langkah pembacaan simpul sebagai berikut.
- Pada awalnya referensi objek currentNode menunjuk pada awal simpul (currentNode = node;)
- Dilakukan pembacaan nilai simpul (currentNode.value)
- Pindahkan currentNode ke simpul berikutnya (currentNode = currentNode.next;)
- Dilakukan perulangan dari langkah no 2 sampai currentNode.next bernilai null
Penyisipan simpul di tengah seranai berantai
Penyisipan simpul di tengah seranai berantai dibutuhkan cursor untuk menentukan posisi simpul yang akan disisipkan. Langkah-langkah penyisipan simpulsebagai berikut.
- Buat simpul baru (newNode)
- Sambungkan simpul baru ke depan simpul yang sedang ditunjuk oleh cursor (newNode.next = cursor.next.next)
- Sambungkan simpul yang ditunjuk oleh cursor dengan simpul baru (cursor.next.next = newNode)
Untuk memudahkan penyisipan simpul baru dapat dibuat method seperti contoh kode berikut.
static void insertNode(int value, ref Node cursor)
{
Node newNode = new Node(value, null); // buat simpul baru (newNode)
if (cursor.next.next != null) // jika cursor tidak di akhir simpul
{
newNode.next = cursor.next.next; // Sambungkan simpul baru ke depan simpul yang sedang ditunjuk oleh cursor
}
cursor.next.next = newNode; // Sambungkan simpul yang ditunjuk oleh cursor dengan simpul baru
}
Code 6. Penyisipan simpul
Menghapus simpul
Penghapusan simpul dilakukan dengan memutus rantai simpul kemudian menghapus simpul. Jika simpul berada di tengah rangkaian, rangkaian yang terputus perlu disambung kembali. Untuk memudahkan penghapusan simpul dibutuhkan dua cursor sebagai simpul bantu. Selain cursor juga dibutuhkan simpul head sebagai acuan awal simpul dalam rangkaian.
Berikut langkah langkah untuk menghapus simpul dalam rangkaian.
- Buat cursor bantu yang ke dua (cursor2) yang menunjuk ke awal simpul.
- Jika cursor berada di awal rangkaian, kerjakan no 3 sampai 7, jika tidak kerjakan no 8
- Jika simpul yang ditunjuk cursor bukan simpul terakhir (hanya satu simpul) dalam rangkaian, kerjakan no 3 - 6, jika tidak kerjakan no 7
- Pindahkan cursor ke simpul berikutnya
- Putus sambungan awal simpul dengan simpul berikutnya.
- Pindahkan head ke simpul yang ditunjuk oleh cursor.
- Hapus rangkaian (karena hanya ada satu simpul dalam seranai berantai).
- Pindahkan cursor2 ke pisisi sebelum cursor.
- Jika cursor berada di akhir rangkaian, putuskan dari rangkaian sebelumnya (cursor2.next.next = null)
- Jika tidak berada di akhir rangkaian, pindahkan penunjukan simpul yang ditunjuk oleh cursor2 ke simpul setelah simpul yang ditunjuk oleh cursor (cursor2.next.next = cursor.next.next) dan putus sambungan simpul yang ditunjuk oleh cursor dengan simpul berikutnya (cursor.next.next = null)
- Pindahkan cursor ke simpul berikutnya (ditunjuk oleh cursor2).
Untuk lebih memahami bagaimana cara menambahkan simpul baru di akhir seranai berantai, dapat dilihat ilustrasi berikut.
Ilustrasi 1. Penghapusan simpul pada seranai berantai
Untuk memudahkan penghapusan simpul dapat dibuat method seperti contoh kode berikut.
static void deleteNode(ref Node head, Node cursor)
{
Node cursor2 = new Node(-1, head.next);
if (cursor.next == head.next) // jika di awal rangkaian
{
if (cursor.next.next != null) // jika cursor yang ditunjuk bukan akhir rangkaian
{
cursor.next = cursor.next.next; // pindahkan cursor ke simpul berikutnya
head.next.next = null; // Putus sambungan awal simpul dengan simpul berikutnya.
head.next = cursor.next; // Pindahkan head ke simpul yang ditunjuk oleh cursor.
}
else
{
cursor.next = null; // hapus rangkaian, dengan set null pada cursor.next
head.next = null; // dan head.next
}
}
else
{
if (cursor.next != null)
{
/* Pindahkan cursor2 ke posisi sebelum cursor */
while (cursor2.next.next != cursor.next)
{
cursor2.next = cursor2.next.next;
}
if (cursor.next.next == null) // jika cursor di akhir rangkaian
{
cursor2.next.next = null; // putuskan dari rangkaian sebelumnya
}
else {
// pindahkan penunjukan simpul yang ditunjuk oleh cursor2 ke
// simpul setelah simpul yang ditunjuk oleh cursor
cursor2.next.next = cursor.next.next;
// putus sambungan simpul yang ditunjuk oleh cursor dengan simpul berikutnya
cursor.next.next = null;
}
cursor.next = cursor2.next; // Pindahkan cursor ke simpul berikutnya
}
}
}
Code 7. Method penghapusan simpul
Secara keseluruhan baik dalam penambahan/penyisipan, pembacaan, dan penghapusan simpul dalam seranai berantai dibutuhkan beberapa simpul pembantu yaitu kepala (head), ekor (tail) dan cursor. Berikut contoh program secara keseluruhan berdasarkan beberapa contoh kode sebelumnya.
using System;
using System.Collections.Generic;
using System.Text;
class Program
{
class Node
{
public int value;
public Node next;
public Node(int value, Node next)
{
this.value = value;
this.next = next;
}
}
static void insertEnding(int value, Node tail)
{
Node newNode = new Node(value, null); // buat simpul baru (newNode)
tail.next.next = newNode; // sambungkan simpul terakir ke simpul baru (newNode)
tail.next = newNode; // pindahkan taut simpul tail ke simpul terakir
}
static void insertBegining(int value, Node head)
{
// buat simpul baru (newNode) dan sambungkan ke awal simpul
Node newNode = new Node(value, head.next);
// set simpul kepala (head) ke simpul baru
head.next = newNode;
}
static void insertNode(int value, Node cursor)
{
Node newNode = new Node(value, null); // buat simpul baru (newNode)
if (cursor.next.next != null) // jika cursor tidak di akhir simpul
{
newNode.next = cursor.next.next; // Sambungkan simpul baru ke depan simpul yang sedang ditunjuk oleh cursor
}
cursor.next.next = newNode; // Sambungkan simpul yang ditunjuk oleh cursor dengan simpul baru
}
static void deleteNode(Node head, Node cursor)
{
Node cursor2 = new Node(-1, head.next);
if (cursor.next == head.next) // jika di awal rangkaian
{
if (cursor.next.next != null) // jika cursor yang ditunjuk bukan akhir rangkaian
{
cursor.next = cursor.next.next; // pindahkan cursor ke simpul berikutnya
head.next.next = null; // Putus sambungan awal simpul dengan simpul berikutnya.
head.next = cursor.next; // Pindahkan head ke simpul yang ditunjuk oleh cursor.
}
else
{
cursor.next = null; // hapus rangkaian, dengan set null pada cursor.next
head.next = null; // dan head.next
}
}
else
{
if (cursor.next != null)
{
/* Pindahkan cursor2 ke posisi sebelum cursor */
while (cursor2.next.next != cursor.next)
{
cursor2.next = cursor2.next.next;
}
if (cursor.next.next == null) // jika cursor di akhir rangkaian
{
cursor2.next.next = null; // putuskan dari rangkaian sebelumnya
}
else
{
// pindahkan penunjukan simpul yang ditunjuk oleh cursor2 ke
// simpul setelah simpul yang ditunjuk oleh cursor
cursor2.next.next = cursor.next.next;
// putus sambungan simpul yang ditunjuk oleh cursor dengan simpul berikutnya
cursor.next.next = null;
}
cursor.next = cursor2.next; // Pindahkan cursor ke simpul berikutnya
}
}
}
static void PrintNodes(Node cursor)
{
while (cursor.next != null)
{
Console.Write(cursor.next.value + ", ");
cursor.next = cursor.next.next;
}
Console.WriteLine("\n------------");
}
static void Main(string[] args)
{
Node head, tail, cursor; // deklarasi simpul head, tail dan cursor
head = new Node(-1, null); // buat simpul head
head.next = new Node(1, null); // buat simpul pertama yang ditunjuk oleh head dengan nilai 1
tail = new Node(-1, head.next); // buat simpul tail menunjuk ke simpul pertama
cursor = new Node(-1, head.next); // buat simpul cursor menunjuk ke simpul pertama
Console.WriteLine("Penambahan simpul di depan");
insertBegining(2, head); // tambahkan simpul dengan nilai 2 di awal rangkaian
insertBegining(3, head); // tambahkan simpul dengan nilai 3 di awal rangkaian
/* Tampilkan dari awal rangkaian */
cursor.next = head.next;
PrintNodes(cursor);
Console.WriteLine("Penambahan simpul di akhir");
insertEnding(4, tail); // tambahkan simpul dengan nilai 2
insertEnding(5, tail); // tambahkan simpul dengan nilai 3
/* Tampilkan dari awal rangkaian */
cursor.next = head.next;
PrintNodes(cursor);
Console.WriteLine("Penyisipan simpul di tengah (setelah simpul ke-2)");
cursor.next = head.next.next; // set cursor ke simpul ke-2
insertNode(6, cursor);
/* Tampilkan dari awal rangkaian */
cursor.next = head.next;
PrintNodes(cursor);
Console.WriteLine("Penghapusan simpul ke-2");
//cursor.next = cursor.next.next;
cursor.next = head.next.next; // set cursor ke simpul ke-2
deleteNode(head, cursor);
/* Tampilkan dari awal rangkaian */
cursor.next = head.next;
PrintNodes(cursor);
Console.ReadKey();
}
}
Code 8. Contoh program seranai berantai tunggal
Seranai Berantai Ganda
Seranai berantai ganda dapat diakses dalam dua arah, bisa maju dan mundur. Masing-masing simpul memiliki dua taut, satu taut merujuk ke simpul berikutnya (atau null pada akhir simpul) dan taut lainnya ke simpul sebelumnya (pada awal simpul). Penambahan, penyisipan dan penghapusan simpul tidak jauh beda dengan dengan seranai berantai tunggal.
Gambar 4. Seranai berantai ganda
Seranai Berantai Melingkar
Seranai berantai melingkar memiliki struktur simpul yang sama seperti seranai berantai tunggal yaitu hanya memiliki satu penunjuk. Seranai berantai melingkar hanya dapat diakses maju. Perbedaannya, seranai berantai melingkar tidak memiliki simpul kepala dan ekor. Simpul akhir akan menunjuk ke simpul paling depan. Penambahan, penyisipan dan penghapusan simpul tidak jauh beda dengan dengan seranai berantai tunggal.
Gambar 5. Seranai berantai melingkar