Tentang Struktur Data LinkedList

Linked list menyimpan kumpulan data sebagai rantai objek kecil, bukan sebagai satu blok memori. Artikel ini membahas rantai itu, perbandingannya dengan array, dan implementasi paling sederhana yang bisa kamu jalankan sendiri.

Tentang Linked List

Linked list adalah rantai linear berisi node. Setiap node menyimpan dua hal: data dan pointer ke node berikutnya.

Struktur ini disebut linear karena setiap node merujuk tepat ke satu node lain. Kalau digambarkan, bentuknya mirip ular: satu ruas mengikuti ruas berikutnya, tanpa cabang.

Untuk membaca isinya dibutuhkan titik mulai. Titik itu disebut node head. Tidak ada yang merujuk ke head, dan head merujuk ke node berikutnya.

Ujung sebaliknya disebut tail. Node lain merujuk ke tail, tapi tail tidak merujuk ke mana pun.

Ada tiga jenis yang umum: singly, doubly, dan circular linked list. Pembahasannya menyusul.

Kenapa Tidak Pakai Array?

Array dan linked list punya tugas yang sama, yaitu menyimpan kumpulan data. Bedanya di cara data itu ditata di memori.

Array bersifat berurutan. Elemennya duduk berdampingan, jadi elemen mana pun bisa kamu capai lewat indeks dalam O(1). Batasnya, panjang array tetap sejak kamu mendeklarasikannya.

Linked list bersifat tersebar. Node-nya bisa berada di mana saja di memori, dan pointer yang menyambungnya. Karena itu list bisa tumbuh node demi node. Batasnya, mencapai posisi ke-k berarti menelusuri k node dari head, yaitu O(k).

Memori per elemen juga lebih besar, karena setiap node menyimpan satu pointer tambahan di samping datanya.

Tidak ada yang menang secara umum. Pilihannya tergantung apa yang paling sering kamu kerjakan di program.

Node dan Implementasi Sederhana

Node adalah bagian utamanya, jadi dia dapat class sendiri. Isinya field data dan field next, yaitu pointer ke node berikutnya. Di Java, pointer itu tidak lain adalah referensi objek biasa.

Untuk list sederhana, yang perlu kamu simpan cuma referensi ke head. Itu pintu masuk ke seluruh node lain. Menyimpan referensi ke tail sifatnya opsional, walau sering dipakai supaya menambah data di ujung jadi lebih mudah.

Program berikut menyusun list 1, 2, 3, 4, lalu mencetak isinya dengan mulai dari head dan mengikuti next sampai bertemu null:

public class SimpleLinkedList {
  static class Node {
    int data;
    Node next;

    Node(int data) {
      this.data = data;
    }
  }

  public static void main(String[] args) {
    Node head = new Node(1);
    head.next = new Node(2);
    head.next.next = new Node(3);
    head.next.next.next = new Node(4);

    for (Node current = head; current != null; current = current.next) {
      System.out.println(current.data);
    }
  }
}

Sudah dicoba compile dan jalankan dengan javac 21, hasilnya:

1
2
3
4

Perulangannya sama sekali tidak memakai indeks. Yang diikuti cuma pointer, dan itulah penelusuran O(k) dari bagian sebelumnya.

Selanjutnya

Pada artikel berikutnya, singly linked list dibuat dengan rapi: node, class pembungkusnya, dan method yang bekerja di atas list.

Selamat berkoding ria 👋