Linked Lists are one of the most fundamental data structures in computer science. While Swift’s standard library provides powerful Array and Set types, understanding Linked Lists is crucial for coding interviews and understanding memory management.

What is a Linked List?

A Linked List is a linear data structure where elements are not stored in contiguous memory locations. Instead, each element (called a Node) points to the next one.

Linked List vs Array

Anatomy of a Node

Each node contains two things:

1. Value: The data it holds.
2. Next: A reference to the next node.

  graph LR
    Head[HEAD] --> Node1
    subgraph Node1 [Node 1]
    Val1[Value: 10]
    Next1[Next]
    end
    Next1 --> Node2
    subgraph Node2 [Node 2]
    Val2[Value: 20]
    Next2[Next]
    end
    Next2 --> Null[Nil]

Implementation in Swift

Let’s build a Generic Node class.

1class Node<T> {
2    var value: T
3    var next: Node?
4
5    init(value: T) {
6        self.value = value
7    }
8}

Now, the LinkedList class to manage the nodes.

 1struct LinkedList<T> {
 2    var head: Node<T>?
 3    var tail: Node<T>?
 4
 5    var isEmpty: Bool {
 6        return head == nil
 7    }
 8
 9    // 1. Append (Add to end) - O(1) thanks to tail pointer
10    mutating func append(_ value: T) {
11        let newNode = Node(value: value)
12        if let tailNode = tail {
13            tailNode.next = newNode
14        } else {
15            head = newNode
16        }
17        tail = newNode
18    }
19    
20    // 2. Prepend (Add to start) - O(1)
21    mutating func prepend(_ value: T) {
22        let newNode = Node(value: value)
23        newNode.next = head
24        head = newNode
25        if tail == nil {
26            tail = head
27        }
28    }
29}

Advanced Operations

Inserting at a Specific Index

To insert into the middle, we must traverse the list to find the node before the target index.

  graph LR
    A[A] --> B[B]
    B --> C[C]
    style B fill:#f9f,stroke:#333,stroke-width:2px
    style New fill:#bbf,stroke:#333,stroke-width:2px
    New[New Node] -.-> C
    B -.-> New

1    mutating func insert(_ value: T, after node: Node<T>) {
2        let newNode = Node(value: value)
3        newNode.next = node.next
4        node.next = newNode
5        if newNode.next == nil {
6            tail = newNode
7        }
8    }

Removing a Value

Removing requires updating the next pointer of the previous node to skip the current one.

 1    @discardableResult
 2    mutating func removeLast() -> T? {
 3        // 1. Empty case
 4        if head == nil { return nil }
 5        
 6        // 2. Single element case
 7        if head?.next == nil {
 8            return pop()
 9        }
10        
11        // 3. Traverse to find node before tail
12        var prev = head
13        var current = head
14        while let next = current?.next {
15            prev = current
16            current = next
17        }
18        
19        // 4. Update interactions
20        prev?.next = nil
21        tail = prev
22        return current?.value
23    }

Doubly Linked List

In a Singly Linked List, you can only move forward. A Doubly Linked List adds a previous pointer, allowing traversal in both directions.

Pros:

• Can traverse backwards.
• Deletion is O(1) if you have the node reference (no need to traverse from head).

Cons:

• Uses more memory (extra pointer per node).

Conclusion

Linked Lists are powerful tools for specific scenarios like implementing Queues, Stacks, or when you need constant-time insertions/deletions. While Swift Arrays are usually faster due to CPU caching, knowing how to build a Linked List is a badge of honor for any developer.