Belajar Data Structure - Linked List

#Pendahuluan

Setelah di episode 4 kita memahami rekursi dan stack frame — fondasi untuk tree traversal dan backtracking — pada episode ini kita mempelajari linked list, struktur data linear di mana elemen-elemen tidak disimpan berurutan di memori seperti array, tetapi dihubungkan oleh pointer atau referensi.

Linked list mungkin terlihat seperti array yang "kurang bagus" karena tidak ada random access. Tetapi justru di sinilah kekuatannya: insert dan delete di awal list bisa dilakukan dalam O(1), tanpa perlu menggeser elemen seperti pada array. Memahami trade-off ini adalah kunci untuk memilih struktur data yang tepat di kemudian hari.

#Variasi Linked List

#Singly Linked List

Setiap node memiliki data dan pointer ke node berikutnya (next). Traversal hanya bisa dilakukan dari head ke tail — tidak bisa mundur.

[10|next] -> [20|next] -> [30|next] -> None

#Doubly Linked List

Setiap node memiliki data, pointer ke node berikutnya (next), dan pointer ke node sebelumnya (prev). Traversal bisa dilakukan ke kedua arah, tetapi setiap node membutuhkan lebih banyak memori.

None <- [10|prev|next] <-> [20|prev|next] <-> [30|prev|next] -> None

#Circular Linked List

Node terakhir (tail) mengarah kembali ke node pertama (head). Berguna untuk implementasi queue circular dan rotasi data.

[10|next] -> [20|next] -> [30|next] -+
   ^                                  |
   +----------------------------------+

#Perbandingan

#Operasi Linked List

#Insert

Insert di head: buat node baru, set next-nya ke head saat ini, lalu update head. O(1).

Insert di tail: traverse sampai akhir, set next node terakhir ke node baru. O(n) untuk singly list, O(1) jika ada tail pointer.

Insert di tengah: traverse ke posisi yang tepat, update pointer. O(n).

#Delete

Delete di head: update head ke head.next. O(1).

Delete di tengah: traverse ke posisi sebelum node yang akan dihapus, update pointer untuk melewati node tersebut. O(n).

#Implementasi Singly Linked List

Singly linked list dari nol

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
 
class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.size = 0
 
    def insert_head(self, value):
        node = Node(value)
        node.next = self.head
        self.head = node
        self.size += 1
 
    def insert_tail(self, value):
        node = Node(value)
        if not self.head:
            self.head = node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = node
        self.size += 1
 
    def delete(self, value):
        if not self.head:
            return
        if self.head.value == value:
            self.head = self.head.next
            self.size -= 1
            return
        current = self.head
        while current.next:
            if current.next.value == value:
                current.next = current.next.next
                self.size -= 1
                return
            current = current.next
 
    def traverse(self):
        elements = []
        current = self.head
        while current:
            elements.append(current.value)
            current = current.next
        return elements

#Reverse Linked List

#Reverse Iteratif

Reverse iteratif

def reverse_iterative(self):
    prev = None
    current = self.head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    self.head = prev

Kompleksitas: O(n) waktu, O(1) ruang. Cukup satu traversal dengan tiga pointer.

#Reverse Rekursif

Reverse rekursif

def reverse_recursive(self):
    def _reverse(current, prev=None):
        if not current:
            return prev
        next_node = current.next
        current.next = prev
        return _reverse(next_node, current)
    self.head = _reverse(self.head)

Kompleksitas: O(n) waktu, O(n) ruang karena stack frame rekursif. Lebih elegan tetapi kurang efisien secara memori.

#Cycle Detection: Floyd's Algorithm

#Floyd's Tortoise and Hare

Floyd's algorithm menggunakan dua pointer dengan kecepatan berbeda: slow bergerak satu langkah, fast bergerak dua langkah. Jika ada cycle, keduanya akan bertemu. Jika tidak ada cycle, fast akan mencapai None.

Floyd's cycle detection

def has_cycle(head):
    slow = head
    fast = head
 
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
 
    return False

#Mengapa Ini Bekerja?

Bayangkan lintasan lari atlet di trek bundar. Jika dua atlet berlari dengan kecepatan berbeda dari titik yang sama, mereka pasti akan bertemu lagi. Sama seperti slow dan fast pointer — jika ada cycle, fast akan "mengejar" slow dari belakang.

#Menemukan Titik Masuk Cycle

Modifikasi Floyd's algorithm bisa menemukan titik masuk cycle — node pertama dari cycle:

Menemukan titik masuk cycle

def detect_cycle_start(head):
    slow = head
    fast = head
 
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow
 
    return None

#Kapan Pakai Linked List

#Kelebihan

• Insert/delete di head: O(1)
• Tidak perlu alokasi kontinu memori
• Mudah diimplementasikan secara dinamis
• Building block untuk stack, queue, hash chaining, LRU cache

#Kekurangan

• Tidak ada random access: O(n) untuk akses element ke-i
• Overhead memori untuk pointer (terutama doubly linked list)
• Cache-unfriendly: elemen tersebar di memori

#Penutup

Inti yang harus dibawa pulang:

• Singly linked list: node dengan value + next; doubly: tambah prev; circular: tail ke head.
• Insert/delete di head: O(1); akses by index: O(n).
• Reverse iteratif O(1) ruang, reverse rekursif O(n) ruang.
• Floyd's algorithm: slow + fast pointer mendeteksi cycle dalam O(n) waktu dan O(1) ruang.
• Linked list adalah building block untuk stack, queue, hash chaining, dan LRU cache.

Di episode 6 selanjutnya kita akan membahas stack dan queue — dua struktur linear paling penting yang masing-masing menerapkan prinsip LIFO dan FIFO. Keduanya bisa diimplementasikan dengan array maupun linked list, dan masing-masing memiliki kelebihan. Pastikan kalian sudah praktik linked list karena implementasi stack dan queue akan menggunakannya!