Linked List

A sequence of nodes where each node holds a value and a pointer to the next node.

Complexity

Time (Best)

O(1)

Time (Avg)

O(n)

Time (Worst)

O(n)

Space

O(n)

Key Points

›O(1) insertion/deletion at head (or any node with a pointer)
›O(n) search — must traverse from head, no random access
›More memory per element than arrays (extra pointer per node)
›No shifting required for insertion/deletion — just re-link pointers
›Doubly linked list adds prev pointer for O(1) backwards traversal

Code Examples

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
        }
    }
}

Practice Problems

Reverse Linked List

EasyLeetCode ↗

Linked List Cycle

EasyLeetCode ↗

Merge Two Sorted Lists

EasyLeetCode ↗

Remove Nth Node From End of List

MediumLeetCode ↗