Linked List

Linked list adalah struktur data dinamis di mana setiap elemen yang disebut node menyimpan data dan pointer (referensi) ke node berikutnya. Bayangkan seperti rantai di mana setiap mata rantai terhubung ke mata rantai berikutnya. Berbeda dengan array yang menggunakan memori berurutan, node-node dalam linked list bisa tersebar di berbagai lokasi memori.

Keuntungan utama linked list adalah kemampuannya untuk melakukan penyisipan dan penghapusan dengan efisien tanpa perlu menggeser elemen-elemen lain. Namun, akses ke elemen tertentu memerlukan traversal dari awal, berbeda dengan array yang bisa akses langsung.

Kompleksitas Operasi

Untuk linked list, akses ke elemen ke-n memerlukan O(n) karena kita harus melakukan traversal dari head. Penyisipan di awal memiliki kompleksitas O(1) karena kita hanya perlu mengubah beberapa pointer. Penyisipan di akhir adalah O(n) jika kita tidak memiliki pointer tail, atau O(1) jika ada. Penghapusan node setelah node tertentu adalah O(1), tetapi mencari node yang akan dihapus tetap O(n).

Contoh Implementasi

package main

import "fmt"

// Node merepresentasikan satu elemen dalam linked list
type Node struct {
    Value int
    Next  *Node
}

// LinkedList adalah struktur yang memegang head dari list
type LinkedList struct {
    Head *Node
}

// Insert menambahkan node baru di awal list
// Kompleksitas Waktu: O(1) - hanya operasi pointer
// Kompleksitas Ruang: O(1) - satu node baru
func (ll *LinkedList) Insert(value int) {
    newNode := &Node{Value: value}
    // Node baru menunjuk ke head yang lama
    newNode.Next = ll.Head
    // Head sekarang menunjuk ke node baru
    ll.Head = newNode
}

// Delete menghapus node pertama dengan value tertentu
// Kompleksitas Waktu: O(n) - mungkin perlu traverse seluruh list
// Kompleksitas Ruang: O(1) - tidak ada alokasi memori tambahan
func (ll *LinkedList) Delete(value int) bool {
    // Kasus khusus: list kosong
    if ll.Head == nil {
        return false
    }
    
    // Kasus khusus: node yang akan dihapus adalah head
    if ll.Head.Value == value {
        ll.Head = ll.Head.Next
        return true
    }
    
    // Traverse untuk mencari node sebelum node yang akan dihapus
    current := ll.Head
    for current.Next != nil {
        if current.Next.Value == value {
            // Skip node yang akan dihapus dengan menghubungkan
            // node sebelumnya langsung ke node setelahnya
            current.Next = current.Next.Next
            return true
        }
        current = current.Next
    }
    
    return false
}

// Reverse membalik urutan linked list
// Kompleksitas Waktu: O(n) - satu pass melalui list
// Kompleksitas Ruang: O(1) - hanya menggunakan tiga pointer
func (ll *LinkedList) Reverse() {
    var prev *Node = nil
    current := ll.Head
    
    // Ide: untuk setiap node, ubah arah pointer Next-nya
    // untuk menunjuk ke node sebelumnya
    for current != nil {
        // Simpan node berikutnya sebelum kita mengubah pointer
        nextTemp := current.Next
        
        // Balik pointer current untuk menunjuk ke prev
        current.Next = prev
        
        // Gerakkan prev dan current satu langkah ke depan
        prev = current
        current = nextTemp
    }
    
    // Setelah loop, prev adalah node terakhir (head baru)
    ll.Head = prev
}

// HasCycle mendeteksi apakah linked list memiliki cycle
// Kompleksitas Waktu: O(n) - dalam kasus terburuk traverse seluruh list
// Kompleksitas Ruang: O(1) - hanya dua pointer
func (ll *LinkedList) HasCycle() bool {
    if ll.Head == nil {
        return false
    }
    
    // Floyd's Cycle Detection Algorithm (Tortoise and Hare)
    // Slow bergerak 1 step, fast bergerak 2 steps
    // Jika ada cycle, mereka pasti akan bertemu
    slow := ll.Head
    fast := ll.Head
    
    for fast != nil && fast.Next != nil {
        slow = slow.Next        // Bergerak 1 step
        fast = fast.Next.Next   // Bergerak 2 steps
        
        // Jika slow dan fast bertemu, ada cycle
        if slow == fast {
            return true
        }
    }
    
    // Fast mencapai akhir, tidak ada cycle
    return false
}

// Print menampilkan semua elemen dalam list
func (ll *LinkedList) Print() {
    current := ll.Head
    for current != nil {
        fmt.Printf("%d -> ", current.Value)
        current = current.Next
    }
    fmt.Println("nil")
}

Studi Kasus: Merge Two Sorted Lists

Permasalahan ini sering muncul dalam sistem yang perlu menggabungkan data yang sudah terurut dari berbagai sumber, seperti merge sort atau menggabungkan hasil query dari database yang berbeda.

// MergeSortedLists menggabungkan dua sorted linked lists menjadi satu sorted list
// Kompleksitas Waktu: O(n + m) dimana n dan m adalah panjang kedua list
// Kompleksitas Ruang: O(1) jika tidak menghitung output, atau O(n + m) untuk list baru
func MergeSortedLists(l1, l2 *Node) *Node {
    // Dummy node untuk mempermudah handling edge cases
    // Ini adalah teknik umum dalam linked list problems
    dummy := &Node{}
    current := dummy
    
    // Traverse kedua list secara bersamaan
    for l1 != nil && l2 != nil {
        // Ambil node dengan value lebih kecil
        if l1.Value <= l2.Value {
            current.Next = l1
            l1 = l1.Next
        } else {
            current.Next = l2
            l2 = l2.Next
        }
        current = current.Next
    }
    
    // Tambahkan sisa elemen dari list yang lebih panjang
    // Hanya salah satu dari kondisi ini yang akan terpenuhi
    if l1 != nil {
        current.Next = l1
    }
    if l2 != nil {
        current.Next = l2
    }
    
    // Return head dari merged list (skip dummy node)
    return dummy.Next
}

// FindMiddle mencari node tengah dari linked list
// Kompleksitas Waktu: O(n)
// Kompleksitas Ruang: O(1)
func FindMiddle(head *Node) *Node {
    if head == nil {
        return nil
    }
    
    // Two pointer technique: slow bergerak 1, fast bergerak 2
    // Ketika fast mencapai akhir, slow ada di tengah
    slow := head
    fast := head
    
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    
    return slow
}

func main() {
    // Test basic operations
    ll := &LinkedList{}
    ll.Insert(3)
    ll.Insert(2)
    ll.Insert(1)
    
    fmt.Println("Original list:")
    ll.Print() // 1 -> 2 -> 3 -> nil
    
    ll.Reverse()
    fmt.Println("Reversed list:")
    ll.Print() // 3 -> 2 -> 1 -> nil
    
    // Test merge
    l1 := &Node{Value: 1, Next: &Node{Value: 3, Next: &Node{Value: 5}}}
    l2 := &Node{Value: 2, Next: &Node{Value: 4, Next: &Node{Value: 6}}}
    
    merged := MergeSortedLists(l1, l2)
    fmt.Println("Merged list:")
    current := merged
    for current != nil {
        fmt.Printf("%d -> ", current.Value)
        current = current.Next
    }
    fmt.Println("nil")
}

Penjelasan Kompleksitas untuk Cycle Detection

Floyd's Cycle Detection Algorithm sangat clever karena menggunakan konsep matematika sederhana. Jika ada cycle, fast pointer yang bergerak 2x lebih cepat pasti akan bertemu dengan slow pointer di dalam cycle. Kompleksitas waktunya O(n) karena dalam kasus terburuk, slow pointer hanya perlu traverse sekali melalui bagian non-cycle plus jarak tertentu dalam cycle. Kompleksitas ruang O(1) karena kita hanya menggunakan dua pointer tanpa struktur data tambahan, berbeda dengan pendekatan hash set yang memerlukan O(n) space.