Linked Lists
In Chapter 6, you encountered linked list nodes as self-referential structures perfect for recursive algorithms. In Chapter 8, we learned that different data structures offer different performance trade-offs. Now it’s time to build a complete linked list implementation—a fundamental data structure that trades random access speed for insertion and deletion flexibility.
Arrays vs linked lists
A linked list provides similar functionality to an array—the ability to insert, retrieve, update, and remove elements. However, because elements are managed independently (scattered in memory) rather than contiguously (in a single block), linked lists excel when dealing with frequent modifications to large datasets.
Memory organization
-
Arrays store elements in contiguous memory—a single continuous block. This enables fast random access (base address + index × size = element location) but requires copying the entire array to a larger block when capacity is exceeded.
-
Linked lists store elements anywhere in memory, with each element pointing to the next (and optionally previous). No resizing needed—just allocate new nodes as needed. The cost is slower access by index since you must traverse from the beginning.
Performance comparison
| Operation | Array | Linked List |
|---|---|---|
| Access by index | O(1) |
O(n) |
| Insert at beginning | O(n) |
O(1) |
| Insert at end | O(1)* |
O(1)** |
| Remove from beginning | O(n) |
O(1) |
| Search for value | O(n) |
O(n) |
* Amortized O(1) with capacity doubling
** If maintaining a tail pointer
When to use each
Linked lists excel in scenarios requiring frequent insertions or deletions at the beginning or middle of the sequence, particularly when the data size is unknown or highly dynamic. They’re ideal for sequential-only access patterns and often serve as building blocks for more complex data structures. Use linked lists when you need flexibility in modifying the sequence structure without the cost of shifting elements.
Arrays prove superior when your application requires frequent random access by index or primarily reads data with few modifications. For small datasets under 100 elements, arrays typically outperform linked lists despite their insertion overhead. Arrays also offer better memory efficiency due to lower per-element overhead and integrate seamlessly with Swift’s functional methods like map, filter, and reduce.
The node structure
Our implementation uses LLNode to represent individual nodes in a doubly-linked list. This structure supports both singly-linked lists (using only next) and doubly-linked lists (using both next and previous). The generic type T allows storing any type, and optional values enable representing empty nodes and list boundaries.
// Generic linked list node - doubly-linked with previous and next pointers
public class LLNode<T> {
var tvalue: T?
var next: LLNode?
var previous: LLNode?
public init() {}
}
Building the LinkedList class
The LinkedList<T> class manages a collection of nodes:
// Generic linked list implementation
public class LinkedList<T> {
private var head = LLNode<T>()
private var counter: Int = 0
// Number of elements in list - O(1)
var count: Int {
return counter
}
// Check if list is empty - O(1)
public func isEmpty() -> Bool {
return counter == 0 || head.tvalue == nil
}
}
The head node represents the beginning of the list. The counter tracks the number of elements for O(1) count operations.
Appending elements
Adding elements to the end of a linked list requires traversing to the last node:
// Add element to end of list - O(n)
public func append(_ tvalue: T) {
// Handle empty list
guard head.tvalue != nil else {
head.tvalue = tvalue
counter += 1
return
}
var current: LLNode = head
// Traverse to end of list
while let item = current.next {
current = item
}
// Create and append new node
let childToUse = LLNode<T>()
childToUse.tvalue = tvalue
childToUse.previous = current
current.next = childToUse
counter += 1
}
This operation is O(n) because we must traverse the entire list to find the end. A production implementation might maintain a tail pointer to make appending O(1).
Finding elements
Accessing elements by index requires linear traversal:
// Find element at specific index - O(n)
public func find(at index: Int) -> LLNode<T>? {
// Validate index
if index < 0 || index > (count - 1) || head.tvalue == nil {
return nil
}
var current: LLNode<T> = head
var x: Int = 0
// Traverse to index
while index != x {
guard let nextNode = current.next else {
return nil
}
current = nextNode
x += 1
}
return current
}
// Subscript support for convenient access
public subscript(index: Int) -> LLNode<T>? {
get {
return find(at: index)
}
}
Unlike arrays where array[5] is instant, linked lists must walk through nodes 0, 1, 2, 3, 4 to reach index 5. This makes random access inefficient.
Inserting elements
Insertion at a specific position involves adjusting pointer references:
// Insert element at specific index - O(n)
public func insert(_ tvalue: T, at index: Int) {
// Validate and handle empty list
guard index >= 0 && index <= count - 1 else {
print("Index out of bounds")
return
}
guard head.tvalue != nil else {
head.tvalue = tvalue
counter += 1
return
}
var current: LLNode<T>? = head
var trailer: LLNode<T>?
var listIndex: Int = 0
// Find insertion point
while current != nil {
if index == listIndex {
let childToUse = LLNode<T>()
childToUse.tvalue = tvalue
// Link new node into chain
childToUse.next = current
childToUse.previous = trailer
if let linktrailer = trailer {
linktrailer.next = childToUse
}
if let linkCurrent = current {
linkCurrent.previous = childToUse
}
// Update head if inserting at beginning
if index == 0 {
head = childToUse
}
break
}
trailer = current
current = current?.next
listIndex += 1
}
counter += 1
}
Once at the correct position, insertion is O(1)—just adjust a few pointers. The O(n) cost comes from finding the position.
Removing elements
Removal requires relinking nodes to skip the deleted element:
// Remove element at specific index - O(n)
public func remove(at index: Int) {
guard head.tvalue != nil else { return }
// Handle removing first element
if index == 0 {
if let item = head.next {
head = item
counter -= 1
} else {
head.tvalue = nil
counter = 0
}
return
}
var current: LLNode<T>? = head
var trailer: LLNode<T>?
var nodeindex: Int = 0
// Find node to remove
while let item = current {
if nodeindex == index {
// Bypass removed node in chain
if let tnode = trailer, let cnode = current {
tnode.next = cnode.next
}
current = nil
break
}
trailer = current
current = item.next
nodeindex += 1
}
counter -= 1
}
Removing from the beginning is O(1), but removing from elsewhere requires O(n) traversal to find the node.
Traversing the list
Processing all elements uses iteration:
// Print all values in list - O(n)
public func printValues() {
var current: LLNode? = head
while current != nil {
if let item = current, let tvalue = item.tvalue {
print("link item is: \(tvalue)")
}
current = current?.next
}
}
This pattern—using a current pointer that advances through the list—is fundamental to all linked list operations.
Building algorithmic intuition
Linked lists demonstrate fundamental trade-offs between data structures: arrays provide fast index access but expensive insertions, while linked lists provide fast insertions but require linear traversal. Pointer manipulation—following next pointers, updating references, managing node connections—forms the foundation for more complex structures like stacks and queues (Chapter 10), binary search trees (Chapter 11), and graphs (Chapter 13). Understanding when dynamic structure matters more than random access reveals when linked lists provide the optimal solution.