Linked list: cara kerja, kode Python, dan kompleksitasnya

Masalah apa yang diselesaikan linked list

Array (list di Python) menyimpan elemennya dalam satu blok memori yang berurutan. Membaca a[i] sangat cepat, tetapi menyisipkan di awal menggeser semua elemen lain satu slot ke kanan, yang butuh O(n). Linked list menghindari pergeseran itu: tiap elemen berada di node-nya sendiri, dan node-node dihubungkan lewat referensi. Untuk menyisipkan, Anda hanya mengubah beberapa referensi.

Linked list adalah fondasi banyak struktur data lain: stack, queue, bucket hash table (separate chaining), LRU cache, dan adjacency list pada graf.

Ide dasarnya dengan bahasa sederhana

Bayangkan permainan berburu harta karun: setiap petunjuk memberi tahu di mana petunjuk berikutnya. Anda tidak bisa langsung melompat ke petunjuk nomor 7; Anda harus mengikuti petunjuk 1 sampai 6 dulu. List itu sendiri hanya mengingat node pertama, yang disebut head. Node terakhir menunjuk ke kosong (None).

Contoh langkah demi langkah: insert dan delete

Mulai dari list 3 -> 7 -> 9. Kita menyisipkan 5 setelah 3, lalu menghapus 7.

1. Buat node baru dengan nilai 5.
2. Set new.next ke node setelah 3 (yaitu node 7).
3. Set node3.next ke node baru. Sekarang list-nya 3 -> 5 -> 7 -> 9.
4. Untuk menghapus 7, cari node sebelumnya (5) dengan menelusuri dari head.
5. Set node5.next = node5.next.next, yang melewati 7. Sekarang list-nya 3 -> 5 -> 9. Garbage collector Python membebaskan node yang sudah tidak terjangkau.

Implementasi singly linked list di Python

Kelas ini menyimpan referensi ke head dan penghitung ukuran. Ia mendukung penambahan di depan dan belakang, penghapusan nilai pertama yang cocok, dan iterasi.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next
class LinkedList:
    def __init__(self):
        self.head = None
        self.size = 0
    def push_front(self, value):
        self.head = Node(value, self.head)
        self.size += 1
    def push_back(self, value):
        node = Node(value)
        if self.head is None:
            self.head = node
        else:
            cur = self.head
            while cur.next:
                cur = cur.next
            cur.next = node
        self.size += 1
    def remove(self, value):
        prev, cur = None, self.head
        while cur and cur.value != value:
            prev, cur = cur, cur.next
        if cur is None:
            return False          # not found
        if prev is None:
            self.head = cur.next  # removing the head
        else:
            prev.next = cur.next
        self.size -= 1
        return True
    def __iter__(self):
        cur = self.head
        while cur:
            yield cur.value
            cur = cur.next

items = LinkedList()
for x in [3, 7, 9]:
    items.push_back(x)
items.push_front(1)
items.remove(7)
print(list(items), items.size)  # [1, 3, 9] 3

push_back di sini menelusuri seluruh list, jadi kompleksitasnya O(n). Dengan menyimpan referensi tail tambahan, ia menjadi O(1); begitulah implementasi queue yang sebenarnya.

Operasi klasik: reverse dan deteksi siklus

Membalik list di tempat (in place) adalah soal wawancara linked list yang paling umum. Telusuri list satu kali dan balikkan arah setiap pointer next.

def reverse(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next     # remember the rest
        cur.next = prev    # turn the pointer around
        prev, cur = cur, nxt
    return prev            # new head
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False
head = Node(1, Node(2, Node(3)))
head = reverse(head)
print(head.value, head.next.value, head.next.next.value)  # 3 2 1
print(has_cycle(head))  # False

has_cycle adalah algoritma tortoise and hare milik Floyd: pointer lambat bergerak satu langkah dan pointer cepat dua langkah. Jika ada loop, pointer cepat akhirnya bertemu pointer lambat; jika tidak, ia mencapai None. Memori tambahan yang dipakai hanya O(1).

Kompleksitas waktu dan ruang

Dalam praktik, array sering lebih cepat bahkan untuk operasi yang Big O-nya lebih baik pada linked list, karena elemen array berdekatan di memori dan memanfaatkan cache CPU dengan baik. Node linked list tersebar.

Varian dan kesalahan umum

• Lupa menangani list kosong: selalu periksa head is None sebelum membaca head.next.
• Kehilangan sisa list karena menimpa next sebelum menyimpannya (lihat nxt di reverse).
• Tidak memperbarui head saat node pertama dihapus, atau tail saat node terakhir dihapus.
• Memakai rekursi pada list yang sangat panjang: batas rekursi default Python sekitar 1000 frame, jadi kode iteratif lebih aman.
• Node head dummy (sentinel) menghilangkan sebagian besar kasus khusus: setiap node asli jadi punya node sebelumnya.
• Pada doubly linked list, setiap insert dan delete harus memperbarui empat referensi; melewatkan satu saja merusak list secara diam-diam.

Kapan memakai linked list, dan apa yang dipakai di Python

Gunakan linked list ketika Anda sering menyisipkan dan menghapus di ujung atau di tengah pada posisi yang sudah Anda pegang referensinya, dan jarang butuh akses acak. Contoh: LRU cache (doubly linked list plus hash map), free list pada memory allocator, riwayat undo, atau bucket pada hash table.

Dalam kode Python sehari-hari Anda jarang menulis sendiri. Untuk queue atau deque, pakai collections.deque, yang menyediakan append dan pop O(1) di kedua ujung. Untuk urutan umum, pakai list. Tulis linked list sendiri untuk belajar, untuk wawancara, dan ketika Anda perlu menyambung node dalam O(1), seperti pada LRU cache.

from collections import deque
q = deque([1, 2, 3])
q.appendleft(0)
q.append(4)
print(q.popleft(), q.pop(), list(q))  # 0 4 [1, 2, 3]