Linked List

Rangkaian node, di mana setiap node menyimpan sebuah nilai dan pointer ke node berikutnya.

Kompleksitas

Waktu (Terbaik)

O(1)

Waktu (Rata-rata)

O(n)

Waktu (Terburuk)

O(n)

Memori

O(n)

Poin Penting

›Insert/delete O(1) di head (atau di node mana pun yang pointer-nya sudah dipegang)
›Pencarian O(n) karena harus ditelusuri dari head, tidak ada akses acak
›Butuh memori lebih banyak per elemen dibanding array (ada pointer tambahan di setiap node)
›Insert/delete tidak perlu menggeser elemen, cukup sambungkan ulang pointer-nya
›Doubly linked list menambahkan pointer prev agar bisa menelusuri mundur dalam O(1)

Contoh Kode

Swift

class Node<T> {
    var value: T
    var next: Node<T>?
    init(_ value: T) { self.value = value }
}

class LinkedList<T: Equatable> {
    var head: Node<T>?

    func append(_ value: T) {
        let node = Node(value)
        guard var curr = head else { head = node; return }
        while curr.next != nil { curr = curr.next! }
        curr.next = node
    }

    func prepend(_ value: T) {
        let node = Node(value)
        node.next = head
        head = node
    }

    func delete(_ value: T) {
        if head?.value == value { head = head?.next; return }
        var curr = head
        while curr?.next != nil {
            if curr?.next?.value == value {
                curr?.next = curr?.next?.next; return
            }
            curr = curr?.next
        }
    }
}

Latihan Soal

Reverse Linked List

MudahLeetCode ↗

Linked List Cycle

MudahLeetCode ↗

Merge Two Sorted Lists

MudahLeetCode ↗

Remove Nth Node From End of List

SedangLeetCode ↗