A few years ago, I was interviewing a candidate for a senior role. They were brilliant with SwiftUI and knew the Combine framework better than I did, but when I asked them to implement a basic singly linked list on the whiteboard, they completely froze. They kept trying to use an Array to simulate the behavior, which defeated the entire purpose of the exercise. It was a classic case of "framework fluency" masking a gap in fundamental data structure knowledge. In a real production environment, you'll mostly use Swift's built-in collections, but understanding linked lists is how you stop thinking about data as a contiguous block of memory and start thinking about it as a web of references. This shift is critical when you start dealing with complex graphs or custom memory management.

Designing the Node and the List

In Swift, you can't build a linked list using structs because a node needs to hold a reference to another node of the same type. If you tried this with a struct, the compiler would scream at you about "value type having infinite size." We need classes here because they are reference types, allowing us to create that recursive chain.

First, we define the Node. I always recommend making this a generic class so your list can hold integers, strings, or custom objects without rewriting the logic. The most important part is the next property, which must be an optional. Why? Because the very last node in your list points to nothing—it's the end of the line.

class Node<T> {
    var value: T
    var next: Node<T>?

    init(value: T) {
        self.value = value
    }
}

Now, we wrap that node in a LinkedList class. This class doesn't actually hold the data itself; it just keeps track of the head—the first node in the chain. If the head is nil, your list is empty. It's a simple entry point, but it's the only way you can navigate the rest of the structure.

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

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

Managing the Pointers

The real "whiteboard" challenge comes when you have to append an item to the end of the list. Unlike an array, where you just call append() and the language handles the memory, a linked list requires you to manually "walk" from the head all the way to the tail. I've seen developers forget to handle the empty-list case here, which leads to a crash when they try to access a property on a nil head.

To do this correctly, you create a temporary pointer—usually called current—and use a while loop to move forward until current.next is nil. Once you've reached that final node, you simply attach your new node to it. It's a bit tedious, but it illustrates why linked lists have $O(n)$ time complexity for appending (unless you maintain a separate tail pointer, which is a great optimization to mention in an interview).

func append(_ value: T) {
    let newNode = Node(value: value)
    
    guard let headNode = head else {
        head = newNode
        return
    }
    
    var current = headNode
    while let nextNode = current.next {
        current = nextNode
    }
    current.next = newNode
}

When you're practicing this, pay close attention to how you're handling the optionals. Swift's while let and guard let patterns make this much safer than doing it in C++, but the logic remains the same: you are manually stitching memory addresses together. If you lose the reference to the head, you've effectively lost the entire list to the garbage collector (or ARC in Swift's case).

📋 Practical Task

Implementing a Custom Undo Manager via Linked List

In this exercise, you will build a simplified "Undo Manager" that stores a history of strings representing user actions. Because we only care about the most recent action (the head), a linked list is an efficient choice for this pattern.

Requirements:

• Create a Node class and a UndoManager class using the linked list logic from the lesson.
• Implement a method recordAction(_ action: String) that prepends a new action to the list.
• Implement a method undo() -> String? that removes the current head of the list and returns the action that was just "undone."
• Implement a method showHistory() that prints all recorded actions from newest to oldest.

Test your implementation with this scenario:

1. Record "Typed 'Hello'"
2. Record "Changed font to Bold"
3. Record "Inserted Image"
4. Call showHistory() (Should see: Inserted Image → Changed font to Bold → Typed 'Hello')
5. Call undo() (Should return "Inserted Image" and remove it from the list)
6. Call showHistory() (Should see: Changed font to Bold → Typed 'Hello')