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 ini punya ciri yaitu hanya merujuk ke node lainnya tanpa dirujuk node manapun.

Kebalikan dari head, penanda akhir dari linked list ini disebut dengan tail. Node ini hanya dirujuk oleh node lain tanpa merujuk ke node manapun.

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?

Array dan linked list memiliki fungsi yang sama yaitu untuk menyimpan kumpulan data. Namun, keduanya memiliki perbedaan mendasar pada cara penyimpanan datanya.

Array disimpan secara teratur dalam memori sehingga bisa diakses dengan cepat menggunakan indeks. Namun, ukuran array terbatas dan tidak bisa diubah setelah dideklarasikan.

Di sisi lain, linked list disimpan secara acak berkat adanya pointer pada setiap node. Ini memungkinkan linked list untuk memiliki ukuran yang fleksibel dan bisa bertambah seiring dengan kebutuhan. Namun, pengaksesan elemen pada linked list relatif lebih lambat karena harus menelusuri satu per satu node untuk menemukan data yang diinginkan.

Penggunaan memori pada linked list juga lebih besar karena setiap node harus menyimpan data dan pointer. Oleh karena itu, pilihan antara array dan linked list tergantung pada kebutuhan dan situasi yang dihadapi.

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:

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

Dalam membuat linked list sederhana kita perlu referensi ke node head. Node ini berfungsi sebagai entry point untuk mengakses node lainnya. Walau bukan sesuatu yang wajib, node tail juga sering disimpan untuk memudahkan pengaksesan ketika memasukkan data pada linked list.

Secara sederhana, implementasi linked list kurang lebih seperti ini:

public class SimpleLinkedList {
  // Representasi node pada linked list
  static class Node {
    int data;   // data dengan tipe integer
    Node next;  // pointer

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

  static Node head; // Simpan 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:

1
2
3
4

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 👋