Linked List: Single, Double, dan Circular Linked List

Dalam dunia struktur data, linked list merupakan salah satu konsep penting yang wajib dipahami setelah array. Jika array memiliki ukuran tetap dan penyimpanan berurutan di memori, maka linked list menawarkan fleksibilitas yang lebih tinggi karena bersifat dinamis. Inilah alasan mengapa linked list banyak digunakan dalam berbagai aplikasi, terutama yang membutuhkan penambahan dan penghapusan data secara efisien.

Namun, tidak semua linked list itu sama. Ada single linked list, double linked list, dan circular linked list, masing-masing dengan karakteristik, kelebihan, dan penerapan yang berbeda. Artikel ini akan membahas secara lengkap konsep linked list, jenis-jenisnya, cara kerja, hingga contoh implementasinya dalam program dengan bahasa yang mudah dipahami.

Pengertian Linked List

Linked list adalah struktur data linear yang terdiri dari kumpulan elemen yang disebut node, di mana setiap node menyimpan dua bagian utama:

• Data

• Referensi (pointer) ke node berikutnya

Berbeda dengan array, linked list tidak disimpan secara berurutan di memori. Setiap node dapat berada di lokasi memori yang berbeda, tetapi tetap terhubung melalui pointer.

Karakteristik Linked List

Beberapa karakteristik utama linked list:

• Bersifat dinamis (ukuran dapat berubah)

• Tidak membutuhkan alokasi memori berurutan

• Setiap elemen saling terhubung

• Akses data harus dilakukan secara berurutan

Karakteristik ini membuat linked list lebih fleksibel dibanding array.

Setiap node pada linked list umumnya terdiri dari:

1. Data – nilai yang disimpan

2. Pointer/Reference – alamat node berikutnya

Pada beberapa jenis linked list, node juga dapat memiliki pointer ke node sebelumnya.

Pengertian Single Linked List

Single linked list adalah jenis linked list paling sederhana, di mana setiap node hanya memiliki satu pointer yang menunjuk ke node berikutnya.

Struktur alurnya:
Node1 → Node2 → Node3 → NULL

Node terakhir menunjuk ke NULL sebagai penanda akhir.

Kelebihan Single Linked List

• Struktur sederhana

• Penggunaan memori lebih hemat

• Mudah diimplementasikan

Kekurangan Single Linked List

• Tidak bisa mundur ke node sebelumnya

• Proses pencarian harus dimulai dari awal

• Akses data lebih lambat dibanding array

Contoh Penerapan

• Sistem antrian sederhana

• Penyimpanan data yang sering bertambah di akhir

• Implementasi stack dan queue

Pengertian Double Linked List

Double linked list (atau doubly linked list) adalah linked list yang setiap node-nya memiliki dua pointer:

• Pointer ke node berikutnya

• Pointer ke node sebelumnya

Strukturnya:
NULL ← Node1 ↔ Node2 ↔ Node3 → NULL

Dengan dua arah ini, navigasi menjadi lebih fleksibel.

Kelebihan Double Linked List

• Bisa bergerak maju dan mundur

• Penghapusan node lebih mudah

• Navigasi lebih fleksibel

Kekurangan Double Linked List

• Membutuhkan memori lebih besar

• Struktur lebih kompleks

Contoh Penerapan

• Fitur undo dan redo pada aplikasi

• Navigasi halaman (back dan forward) pada browser

• Sistem playlist lagu

Double linked list sangat cocok untuk sistem yang membutuhkan navigasi dua arah.

Pengertian Circular Linked List

Circular linked list adalah linked list di mana node terakhir tidak menunjuk ke NULL, melainkan kembali ke node pertama. Dengan demikian, struktur membentuk lingkaran.

Strukturnya:
Node1 → Node2 → Node3 → kembali ke Node1

Circular linked list bisa berbentuk single maupun double.

Kelebihan Circular Linked List

• Tidak memiliki akhir NULL

• Cocok untuk sistem berulang

• Efisien untuk manajemen siklus

Kekurangan Circular Linked List

• Risiko infinite loop jika tidak hati-hati

• Lebih kompleks dalam pengelolaan

Contoh Penerapan

• Sistem penjadwalan CPU (round-robin)

• Sistem antrian melingkar

• Manajemen giliran pemain dalam game

Circular linked list sangat efektif untuk sistem yang berjalan secara berulang.

1. Traversal

Traversal adalah proses mengakses setiap node secara berurutan.

Kompleksitas waktu: O(n)

2. Insertion (Penambahan Data)

Penambahan node dapat dilakukan di:

• Awal (head)

• Tengah

• Akhir (tail)

Linked list lebih efisien dibanding array dalam operasi ini, terutama jika dilakukan di awal.

3. Deletion (Penghapusan Data)

Penghapusan node dilakukan dengan mengubah pointer agar node tersebut tidak lagi terhubung.

Operasi ini relatif efisien jika posisi node sudah diketahui.

4. Searching

Pencarian dilakukan dengan traversal dari awal hingga data ditemukan.

Kompleksitas waktu: O(n)

Perbandingan Linked List dan Array

Linked list unggul dalam fleksibilitas, sedangkan array unggul dalam kecepatan akses.

Gunakan linked list jika:

• Data sering berubah

• Sering melakukan penambahan dan penghapusan

• Tidak membutuhkan akses langsung berdasarkan indeks

Namun, jika membutuhkan akses cepat berdasarkan indeks, array mungkin lebih tepat.

Beberapa kompleksitas dasar:

• Akses node tertentu → O(n)

• Insertion di awal → O(1)

• Insertion di tengah → O(n)

• Deletion → O(n)

• Traversal → O(n)

Pemahaman kompleksitas ini membantu menentukan kapan linked list menjadi pilihan terbaik.

Beberapa tantangan umum:

• Memahami konsep pointer

• Menghindari kesalahan referensi

• Mengelola node dengan benar

Namun, dengan latihan konsisten, konsep linked list akan menjadi lebih mudah dipahami.

Linked list adalah struktur data dinamis yang sangat fleksibel dan penting dalam pemrograman. Dengan memahami single linked list, double linked list, dan circular linked list, programmer dapat memilih jenis struktur yang paling sesuai dengan kebutuhan sistem.

Meskipun memiliki keterbatasan dalam akses data dibanding array, linked list unggul dalam pengelolaan data yang sering berubah. Pemahaman yang baik tentang linked list akan menjadi fondasi penting untuk mempelajari struktur data lanjutan.