Struktur Data Senarai Berantai (Linked List)

Pengertian Senarai Berantai

Senarai berantai atau linked list adalah sebuah struktur data linear yang menyimpan data dalam kotak-kotak yang disebut simpul atau node, dan setiap simpul memiliki sebuah pointer yang menunjuk ke alamat simpul urutan berikutnya (kecuali untuk simpul paling ujung, pointernya menunjuk ke NULL alias tidak menunjuk ke manapun). Biasanya ada dua buah pointer bantuan, yaitu pointer Head/Start yang menunjuk ke elemen pertama, dan pointer Tail/End yang menunjuk ke elemen terakhir. Kedua pointer ini berperan dalam operasi-operasi pada senarai berantai ini.

Berbeda dengan sebuah array, dimana setiap elemen pasti dan harus bersampingan di dalam memori, elemen-elemen dalam sebuah senarai berantai tidak perlu bersampingan, asalkan tiap simpul saling terhubung melalui pointer-pointernya. Maka dari itu array tidak perlu pointer, karena sudah tahu bahwa elemen berikutnya pasti ada di sampingnya persis. Sementara itu senarai berantai perlu pointer yang menunjuk ke elemen berikutnya.

Karena sifat unik ini, operasi-operasi pada senarai berantai berbeda dengan array biasa, dan membuatnya mampu melakukan beberapa operasi secara efisien, dimana jika operasi itu dilakukan pada array tidak akan efisien.

Berikut adalah contoh implementasi class LinkedList dalama bahasa Java. Tentu ini bukan variasi satu-satunya, tetapi kita akan memakai implementasi ini sebagai dasar dari contoh-contoh kode berikutnya. Metode-metode lain akan ditambahkan di pembahasan operasi pada senarai.

public class LinkedList{
  Node head;  // Pointer ke simpul pertama
  Node tail;  // Pointer ke simpul terakhir
  private int length; // Panjang senarai, alias banyaknya simpul yang ada. 
                      // Dibuat private agar tidak diganti-ganti di luar metode dalam class ini

  public boolean isEmpty(){
    return head == null; // Memeriksa apakah senarai kosong, jika iya return true
  }
  public int length(){
    return this.length(); // Memberikan nilai length, yaitu panjang senarai
  }

  // Metode-metode lain menyusul
}

Jenis-jenis dan Implementasi Senarai Berantai

Secara garis besar, ada 3 jenis senarai berantai, yaitu:

1. Senarai berantai searah (Singly linked list)
2. Senarai berantai dua arah (Doubly linked list)
3. Senarai berantai melingkar (Circular linked list)

Ketiga jenis senarai di atas memakai dasaran class LinkedList yang sama, yang berbeda hanya pada implementasi class Node masing-masing.

Dibawah ini adalah penjelasan berikut implementasinya dalam bahasa Java

Senarai Berantai Searah (Singly Linked List)

Senarai berantai searah atau singly linked list adalah sebuah senarai berantai dimana tiap simpul memiliki tepat satu pointer saja, yaitu pointer ke arah elemen berikutnya. Hal ini membuatnya jadi ‘searah’, karena tiap simpul tahu dimana elemen berikutnya, tetapi tidak tahu dimana elemen sebelumnya, maka penjelajahan pada senarai ini hanya bisa satu arah yaitu dari Head ke Tail.

Implementasi:

class Node{
  int data;  // Data yang disimpan, bisa tipe apa saja
  Node next; // Pointer yang menunjuk ke Node berikutnya

  public Node(int data){
    this.data = data;  // Constructor Method
  }
}

Senarai Berantai Dua Arah (Doubly Linked List)

Senarai berantai dua arah atau doubly linked list adalah senarai berantai dimana setiap node memiliki tepat dua pointer, yaitu pointer ke elemen berikutnya dan pointer ke elemen sebelumnya. Dengan tambahan pointer ke elemen sebelumnya, kita dapat melakukan penelusuran baik dari Head ke Tail maupun Tail ke Head

Implementasi:

class Node{
  int data;  // Data yang disimpan, bisa tipe apa saja
  Node next; // Pointer yang menunjuk ke Node berikutnya
  Node prev; // Pointer yang menunjuk ke Node sebelumnya

  public Node(int data){
    this.data = data; // Constructor Method
  }
}

Senarai Berantai Melingkar (Circular Linked List)

Senarai berantai melingkar atau circular linked list adalah senarai berantai dimana node paling ujung tidak menunjuk ke NULL, tetapi kembali menunjuk ke alamat elemen paling pertama. Dengan begitu, penelusuran yang sudah sampai di ujung dapat langsung kembali ke elemen pertama dengan melihat pointer elemen paling terakhir. Senarai melingkar bisa juga memiliki satu atau dua pointer seperti senarai searah atau dua arah di atas

Seringkali sebuah senarai melingkar hanya perlu satu pointer bantuan, yaitu Head/Start. Karena biasanya dalam senarai melingkar sebenarnya tidak ada ‘urutan’, jadi tidak ada yang disebut ‘elemen pertama’ atau ‘elemen terakhir’ karena dari perspektif program tidak bisa dibedakan karena sifat melingkar dari senarai itu.

Implementasi senarai melingkar sama saja dengan senarai searah atau dua arah, tergantung pilihan. Bedanya adalah simpul posisi terakhir kembali menunjuk ke alamat simpul pertama.

Artikel ini akan berlanjut ke Operasi-operasi pada Senarai Berantai, yang akan membahas tiga operasi dasar dalam senarai berantai dan variasi-variasinya. Sampai bertemu di artikel itu.