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.
Last updated