Tentang Struktur Data LinkedList

baca 3 menit
Tentang Struktur Data LinkedList

Pada kesempatan kali ini kita akan coba membahas secara umum mengenai salah satu struktur data linear, yaitu linked list. Kita akan membahas tentang apa itu linked list, perbandingannya dengan array, hingga implementasi sederhananya.

Mari kita mulai.

Tentang Linked List

Linked List merupakan struktur berupa hubungan linear antara node-node. Dalam setiap node ada 2 komponen yaitu data dan pointer.

Struktur data ini dikatakan struktur linear karena setiap 1 node hanya bisa merujuk ke 1 node lainnya. Kalau kita gambarkan linked list ini mirip seperti ular.

Untuk mengakses data pada linked list kita perlu sebuah titik mulai. Titik ini biasa disebut dengan node head. Node yang disebut head punya ciri khas yaitu tidak dirujuk oleh node manapun tapi merujuk ke node lainnya.

Penanda akhir dari linked list adalah nilai null, yaitu nilai yang diberikan ketika node yang tidak merujuk ke mana-mana. Node ini biasa disebut sebagai tail.

Dalam implementasinya, ada beberapa jenis dari linked list, diantaranya: Singly Linked List, Doubly Linked List, dan Circular Linked List. Tentang implementasi dan pembahasannya akan kita bahas pada kesempatan selanjutnya.

Kenapa Tidak Pakai Array?

Pada intinya, baik array maupun linked list memiliki fungsi yang sama, yaitu menyimpan kumpulan data. Kalau begitu kenapa tidak pakai array saja?

Walaupun fungsinya sama, 2 struktur data ini punya perbedaan mendasar yaitu pada cara penyimpanan datanya.

Array, seperti yang kita tahu disimpan secara urut dalam memori, karena itulah kita bisa mengaksesnya dengan menggunakan indeks. Proses indexing ini juga sangat cepat. Akibat dari penyimpanan seperti ini adalah data yang bisa masuk dalam array terbatas. Sekali array ditentukan ukurannya maka tidak akan bisa berubah lagi.

Nah linked list ada untuk mengatasi masalah ini.

Alih-alih disimpan secara urut dalam memori, data pada linked list bisa disimpan secara acak berkat pointer yang ada pada setiap node. Akibatnya adalah ukuran linked list tidak terikat dengan proses deklarasinya, ukurannya pun bisa bertambah terus selama memori di komputer masih cukup.

Tapi hal ini juga membawa dampak. Pengaksesan elemen pada linked list relatif lebih lambat dibanding array. Ini karena setiap node harus ditelusuri satu per satu untuk menemukan node yang diinginkan. Penggunaan memori juga lebih besar karena selain menyimpan data, setiap node harus menyimpan pointer juga.

Properti dan Representasi Linked List

Tokoh utama dari linked list adalah node. Setiap node memiliki 2 komponen yaitu:

  • data — data yang akan disimpan
  • pointer — perujuk pada node lainnya

Kalau kita buat representasi kodenya jadi seperti ini:

java
class Node<T> {
    T data;        // data yang akan disimpan
    Node<T> next;  // pointer yang merujuk ke node selanjutnya
}

Nah, untuk membuat linked list, kita hanya perlu menyimpan satu node saja sebagai tempat akses. Node ini biasa disebut sebagai node head. Dengan node ini semua node yang lain dapat diakses datanya dengan mengakses pointer yang ada secara berantai.

Untuk memudahkan dalam operasinya, biasanya juga disimpan node paling belakang atau yang disebut dengan tail. Ciri dari node ini adalah tidak merujuk ke node manapun, alias nilai pointernya adalah null.

Secara sederhana implementasi linked list kurang lebih seperti ini:

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

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

  static Node head;

  public static void main(String[] args) {
    // Memasukkan data ke dalam linked list
    head = new Node(1);                 // isi list: 1
    head.next = new Node(2);            // isi list: 1, 2
    head.next.next = new Node(3);       // isi list: 1, 2, 3
    head.next.next.next = new Node(4);  // isi list: 1, 2, 3, 4

    // coba mencetak data dengan menelusuri tiap node
    // mulai dari node head sampai ditemukan null
    Node currentNode = head;
    while (currentNode != null) {
      System.out.println(currentNode.data);
      currentNode = currentNode.next;
    }
  }
}

Kalau kita jalankan pasti hasilnya seperti ini:

plain
1
2
3
4

Operasi pada Linked List

Beberapa operasi yang terdapat pada Linked List antara lain:

  • insertHead(T data) — Memasukkan elemen baru di awal sebagai head
  • insertTail(T data) — Memasukkan elemen baru di akhir sebagai tail
  • removeHead() — Menghapus node head dan mengatur head ke node setelahnya
  • removeTail() — Menghapus node tail dan mengatur tail ke node sebelumnya
  • removeAt(int index) — Menghapus node pada indeks tertentu
  • getAt(int index) — Mengambil data pada node sesuai indeks

Tentang pembahasan dan implementasinya akan kita bahas pada kesempatan selanjutnya.

Selanjutnya

Setelah mengetahui secara umum mengenai linked list, pada kesempatan selanjutnya kita akan coba membuat struktur data Singly Linked List. Mulai dari pembuatan node, class wrapper, hingga implementasi methodnya.

Selamat berkoding ria 👋