6. Linked Lists

Written by Kelvin Lau

A linked list is a collection of values arranged in a linear, unidirectional sequence. A linked list has some theoretical advantages over contiguous storage options such as the Swift Array:

• Constant time insertion and removal from the front of the list.
• Reliable performance characteristics.

As the diagram suggests, a linked list is a chain of nodes. Nodes have two responsibilities:

1. Hold a value.
2. Hold a reference to the next node. A nil value represents the end of the list.

In this chapter, you’ll implement a linked list and learn about the common operations associated with it. You’ll learn about the time complexity of each operation, and you’ll implement a neat little Swift feature known as copy-on-write.

Open up the starter playground for this chapter so that you can dive right into the code.

Node

Create a new Swift file in the Sources directory and name it Node.swift. Add the following to the file:

public class Node<Value> {

  public var value: Value
  public var next: Node?

  public init(value: Value, next: Node? = nil) {
    self.value = value
    self.next = next
  }
}

extension Node: CustomStringConvertible {

  public var description: String {
    guard let next = next else {
      return "\(value)"
    }
    return "\(value) -> " + String(describing: next) + " "
  }
}

Navigate to the playground page and add the following:

example(of: "creating and linking nodes") {
  let node1 = Node(value: 1)
  let node2 = Node(value: 2)
  let node3 = Node(value: 3)

  node1.next = node2
  node2.next = node3

  print(node1)
}

You’ve just created three nodes and connected them:

In the console, you should see the following output:

---Example of creating and linking nodes---
1 -> 2 -> 3

As far as practicality goes, the current method of building lists leaves a lot to be desired. You can easily see that building long lists this way is impractical. A common way to alleviate this problem is to build a LinkedList that manages the Node objects. You’ll do just that!

LinkedList

Create a new file in the Sources directory and name it LinkedList.swift. Add the following to the file:

public struct LinkedList<Value> {

  public var head: Node<Value>?
  public var tail: Node<Value>?

  public init() {}

  public var isEmpty: Bool {
    head == nil
  }
}

extension LinkedList: CustomStringConvertible {

  public var description: String {
    guard let head = head else {
      return "Empty list"
    }
    return String(describing: head)
  }
}

A linked list has the concept of a head and tail, which refers to the first and last nodes of the list, respectively:

Adding values to the list

As mentioned before, you’re going to provide an interface to manage the Node objects. You’ll first take care of adding values. There are three ways to add values to a linked list, each having unique performance characteristics:

1. push: Adds a value at the front of the list.
2. append: Adds a value at the end of the list.
3. insert(after:): Adds a value after a particular list node.

You’ll implement each of these in the next section and analyze their performance characteristics.

push operations

Adding a value at the front of the list is known as a push operation. This is also known as head-first insertion. The code for it is deliciously simple.

Add the following method to LinkedList:

public mutating func push(_ value: Value) {
  head = Node(value: value, next: head)
  if tail == nil {
    tail = head
  }
}

If you’re pushing into an empty list, the new node is both the head and tail of the list.

In the playground page, add the following:

example(of: "push") {
  var list = LinkedList<Int>()
  list.push(3)
  list.push(2)
  list.push(1)

  print(list)
}

Your console output should show this:

---Example of push---
1 -> 2 -> 3

append operations

The next operation you’ll look at is append. This adds a value at the end of the list, known as tail-end insertion.

In LinkedList.swift, add the following code just below push:

public mutating func append(_ value: Value) {

  // 1
  guard !isEmpty else {
    push(value)
    return
  }

  // 2
  tail!.next = Node(value: value)

  // 3
  tail = tail!.next
}

This code is relatively straightforward:

1. Like before, if the list is empty, you’ll need to update both head and tail to the new node. Since append on an empty list is functionally identical to push, you invoke push to do the work for you.
2. You create a new node after the tail node in all other cases. Force unwrapping is guaranteed to succeed since you push in the isEmpty case with the above guard statement.
3. Since this is tail-end insertion, your new node is also the tail of the list.

Leap back into the playground and write the following at the bottom:

example(of: "append") {
  var list = LinkedList<Int>()
  list.append(1)
  list.append(2)
  list.append(3)

  print(list)
}

You should see the following output in the console:

---Example of append---
1 -> 2 -> 3

insert(after:) operations

The third and final operation for adding values is insert(after:). This operation inserts a value at a particular place in the list and requires two steps:

1. Finding a particular node in the list.
2. Inserting the new node.

First, you’ll implement the code to find the node where you want to insert your value.

In LinkedList.swift, add the following code just below append:

public func node(at index: Int) -> Node<Value>? {
  // 1
  var currentNode = head
  var currentIndex = 0

  // 2
  while currentNode != nil && currentIndex < index {
    currentNode = currentNode!.next
    currentIndex += 1
  }

  return currentNode
}

node(at:) will try to retrieve a node in the list based on the given index. Since you can only access the nodes of the list from the head node, you’ll have to make iterative traversals. Here’s the play-by-play:

1. You create a new reference to head and track the current number of traversals.

2. Using a while loop, you move the reference down the list until you’ve reached the desired index. Empty lists or out-of-bounds indexes will result in a nil return value.

Now you need to insert the new node.

Add the following method just below node(at:):

// 1
@discardableResult
public mutating func insert(_ value: Value,
                            after node: Node<Value>)
                            -> Node<Value> {
  // 2
  guard tail !== node else {
    append(value)
    return tail!
  }
  // 3
  node.next = Node(value: value, next: node.next)
  return node.next!
}

Here’s what you’ve done:

1. @discardableResult lets callers ignore the return value of this method without the compiler jumping up and down warning you about it.
2. In the case where this method is called with the tail node, you’ll call the functionally equivalent append method. This will take care of updating tail.
3. Otherwise, you simply link up the new node with the rest of the list and return the new node.

Hop back to the playground page to test this out. Add the following to the bottom of the playground:

example(of: "inserting at a particular index") {
  var list = LinkedList<Int>()
  list.push(3)
  list.push(2)
  list.push(1)

  print("Before inserting: \(list)")
  var middleNode = list.node(at: 1)!
  for _ in 1...4 {
    middleNode = list.insert(-1, after: middleNode)
  }
  print("After inserting: \(list)")
}

You should see the following output:

---Example of inserting at a particular index---
Before inserting: 1 -> 2 -> 3
After inserting: 1 -> 2 -> -1 -> -1 -> -1 -> -1 -> 3

Performance analysis

Whew! You’ve made good progress so far. To recap, you’ve implemented the three operations that add values to a linked list and a method to find a node at a particular index.

Next, you’ll focus on the opposite action: removal operations.

Removing values from the list

There are three main operations for removing nodes:

1. pop: Removes the value at the front of the list.
2. removeLast: Removes the value at the end of the list.
3. remove(at:): Removes a value anywhere in the list.

You’ll implement all three and analyze their performance characteristics.

pop operations

Removing a value at the front of the list is often referred to as pop. This operation is almost as simple as push, so dive right in.

Add the following method to LinkedList:

@discardableResult
public mutating func pop() -> Value? {
  defer {
    head = head?.next
    if isEmpty {
      tail = nil
    }
  }
  return head?.value
}

pop returns the value that was removed from the list. This value is optional since the list may be empty.

By moving the head down a node, you’ve effectively removed the first node of the list. ARC will remove the old node from memory once the method finishes since no more references will be attached to it. If the list becomes empty, you set tail to nil.

Head back inside the playground page and test it out by adding the following code at the bottom:

example(of: "pop") {
  var list = LinkedList<Int>()
  list.push(3)
  list.push(2)
  list.push(1)

  print("Before popping list: \(list)")
  let poppedValue = list.pop()
  print("After popping list: \(list)")
  print("Popped value: " + String(describing: poppedValue))
}

You should see the following output:

---Example of pop---
Before popping list: 1 -> 2 -> 3
After popping list: 2 -> 3
Popped value: Optional(1)

removeLast operations

Removing the last node of the list is somewhat inconvenient. Although you have a reference to the tail node, you can’t chop it off without having a reference to the node before it. Thus, you’ll have to do an arduous traversal. Add the following code just below pop:

@discardableResult
public mutating func removeLast() -> Value? {
  // 1
  guard let head = head else {
    return nil
  }
  // 2
  guard head.next != nil else {
    return pop()
  }
  // 3
  var prev = head
  var current = head

  while let next = current.next {
    prev = current
    current = next
  }
  // 4
  prev.next = nil
  tail = prev
  return current.value
}

Here’s what’s happening in the code:

1. If head is nil, there’s nothing to remove, so you return nil.
2. If the list only consists of one node, removeLast is functionally equivalent to pop. Since pop will handle updating the head and tail references, you’ll just delegate this work to it.
3. You keep searching for a next node until current.next is nil. This signifies that current is the last node of the list.
4. Since current is the last node, you simply disconnect it using the prev.next reference. You also make sure to update the tail reference.

Head back to the playground page and add the following to the bottom:

example(of: "removing the last node") {
  var list = LinkedList<Int>()
  list.push(3)
  list.push(2)
  list.push(1)

  print("Before removing last node: \(list)")
  let removedValue = list.removeLast()

  print("After removing last node: \(list)")
  print("Removed value: " + String(describing: removedValue))
}

You should see the following at the bottom of the console:

---Example of removing the last node---
Before removing last node: 1 -> 2 -> 3
After removing last node: 1 -> 2
Removed value: Optional(3)

removeLast requires you to traverse all the way down the list. This makes for an O(n) operation, which is relatively expensive.

remove(after:) operations

The final remove operation is removing a particular node at a particular point in the list. This is achieved much like insert(after:); You’ll first find the node immediately before the node you wish to remove and then unlink it.

Navigate back to LinkedList.swift and add the following method below removeLast:

@discardableResult
public mutating func remove(after node: Node<Value>) -> Value? {
  defer {
    if node.next === tail {
      tail = node
    }
    node.next = node.next?.next
  }
  return node.next?.value
}

The unlinking of the nodes occurs in the defer block. Special care needs to be taken if the removed node is the tail node since the tail reference must be updated.

Head back to the playground to try it out. You know the drill:

example(of: "removing a node after a particular node") {
  var list = LinkedList<Int>()
  list.push(3)
  list.push(2)
  list.push(1)

  print("Before removing at particular index: \(list)")
  let index = 1
  let node = list.node(at: index - 1)!
  let removedValue = list.remove(after: node)

  print("After removing at index \(index): \(list)")
  print("Removed value: " + String(describing: removedValue))
}

You should see the following output in the console:

---Example of removing a node after a particular node---
Before removing at particular index: 1 -> 2 -> 3
After removing at index 1: 1 -> 3
Removed value: Optional(2)

Try adding more elements and play around with the value of index. Similar to insert(at:), the time complexity of this operation is O(1), but it requires you to have a reference to a particular node beforehand.

Performance analysis

You’ve hit another checkpoint! To recap, you’ve implemented the three operations that remove values from a linked list:

At this point, you’ve defined an interface for a linked list that most programmers around the world can relate to. However, there’s work to be done to adorn the Swift semantics. In the next half of the chapter, you’ll focus on making the interface as Swifty as possible.

Swift collection protocols

The Swift standard library has a set of protocols that help define what’s expected of a particular type. Each of these protocols provides certain guarantees on characteristics and performance. From this set of protocols, you’ll focus on four collection related protocols.

Here’s a quick summary of what each protocol does:

• Tier 1, Sequence: A sequence type provides sequential access to its elements. It comes with an important caveat: Using the sequential access may destructively consume the elements so that you can’t revisit them.

• Tier 2, Collection: A collection type is a sequence type that provides additional guarantees. A collection type is finite and allows for repeated nondestructive sequential access.

• Tier 3, BidirectionalColllection: A collection type can be a bidirectional collection type if it, as the name suggests, can allow for bidirectional travel up and down the sequence. This isn’t possible for the linked list since you can only go from the head to the tail, but not the other way around.

• Tier 4, RandomAccessCollection: A bidirectional collection type can be a random-access collection type if it can guarantee that accessing an element at a particular index will take just as long as access an element at any other index. This is not possible for the linked list since accessing a node near the front of the list is substantially quicker than one further down the list.

There’s more to be said for each of these. You’ll learn more about each as you write conformances for them.

A linked list can earn two qualifications from the Swift collection protocols. First, since a linked list is a chain of nodes, adopting the Sequence protocol makes sense. Second, since the chain of nodes is a finite sequence, it makes sense to adopt the Collection protocol.

Becoming a Swift collection

In this section, you’ll look into implementing the Collection protocol. A collection type is a finite sequence and provides nondestructive sequential access. A Swift Collection also allows for access via a subscript, a fancy term for saying an index can be mapped to a value in the collection.

Here’s an example of using the subscript of a Swift Array:

array[5]

The index of an array is an Int value — value of 5 in this example. The subscript operation is defined with the square brackets. Using the subscript with an index will return you a value from the collection.

Custom collection indexes

A defining metric for performance of the Collection protocol methods is the speed of mapping an Index to a value. Unlike other storage options such as the Swift Array, the linked list cannot achieve O(1) subscript operations using integer indexes. Thus, your goal is to define a custom index that contains a reference to its respective node.

In LinkedList.swift, add the following extension:

extension LinkedList: Collection {

  public struct Index: Comparable {

    public var node: Node<Value>?

    static public func ==(lhs: Index, rhs: Index) -> Bool {
      switch (lhs.node, rhs.node) {
      case let (left?, right?):
        return left.next === right.next
      case (nil, nil):
        return true
      default:
        return false
      }
    }

    static public func <(lhs: Index, rhs: Index) -> Bool {
      guard lhs != rhs else {
        return false
      }
      let nodes = sequence(first: lhs.node) { $0?.next }
      return nodes.contains { $0 === rhs.node }
    }
  }
}

You’ll use this custom index to fulfill Collection requirements. Write the following inside the extension to complete it:

// 1
public var startIndex: Index {
  Index(node: head)
}
// 2
public var endIndex: Index {
  Index(node: tail?.next)
}
// 3
public func index(after i: Index) -> Index {
  Index(node: i.node?.next)
}
// 4
public subscript(position: Index) -> Value {
  position.node!.value
}

1. The startIndex is reasonably defined by the head of the linked list.
2. Collection defines the endIndex as the index right after the last accessible value, so you give it tail?.next.
3. index(after:) dictates how the index can be incremented. You simply give it an index of the immediate next node.
4. The subscript is used to map an Index to the value in the collection. Since you’ve created the custom index, you can easily achieve this in constant time by referring to the node’s value.

That wraps up the procedures for adopting Collection. Navigate back to the playground page and take it for a test drive:

example(of: "using collection") {
  var list = LinkedList<Int>()
  for i in 0...9 {
    list.append(i)
  }

  print("List: \(list)")
  print("First element: \(list[list.startIndex])")
  print("Array containing first 3 elements: \(Array(list.prefix(3)))")
  print("Array containing last 3 elements: \(Array(list.suffix(3)))")

  let sum = list.reduce(0, +)
  print("Sum of all values: \(sum)")
}

You should see the following output:

---Example of using collection---
List: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
First element: 0
Array containing first 3 elements: [0, 1, 2]
Array containing last 3 elements: [7, 8, 9]
Sum of all values: 45

Value semantics and copy-on-write

Another important quality of a Swift collection is that it has value semantics. This is implemented efficiently using copy-on-write, hereby referred to as COW. To illustrate the concept of value semantics, you’ll explore the behavior using arrays.

Write the following at the bottom of the playground page:

example(of: "array cow") {
  let array1 = [1, 2]
  var array2 = array1

  print("array1: \(array1)")
  print("array2: \(array2)")

  print("---After adding 3 to array 2---")
  array2.append(3)
  print("array1: \(array1)")
  print("array2: \(array2)")
}

You should see the following output:

---Example of array cow---
array1: [1, 2]
array2: [1, 2]
---After adding 3 to array 2---
array1: [1, 2]
array2: [1, 2, 3]

The elements of array1 are unchanged when array2 is modified. Underneath the hood, array2 makes a copy of the underlying storage when append is called:

Now, check whether or not your linked list has value semantics. Write the following at the bottom of the playground page:

example(of: "linked list cow") {
  var list1 = LinkedList<Int>()
  list1.append(1)
  list1.append(2)
  var list2 = list1
  print("List1: \(list1)")
  print("List2: \(list2)")

  print("After appending 3 to list2")
  list2.append(3)
  print("List1: \(list1)")
  print("List2: \(list2)")
}

You should see the following output:

---Example of linked list cow---
List1: 1 -> 2
List2: 1 -> 2
After appending 3 to list2
List1: 1 -> 2 -> 3
List2: 1 -> 2 -> 3

Unfortunately, your linked list does not have value semantics! This is because your underlying storage uses a reference type (Node). This is a serious problem, as LinkedList is a struct and should use value semantics. Implementing COW will fix this problem.

The strategy to achieve value semantics with COW is reasonably straightforward. Before mutating the contents of the linked list, you want to perform a copy of the underlying storage and update all references (head and tail) to the new copy.

In LinkedList.swift, add the following method to LinkedList:

private mutating func copyNodes() {
  guard var oldNode = head else {
    return
  }

  head = Node(value: oldNode.value)
  var newNode = head

  while let nextOldNode = oldNode.next {
    newNode!.next = Node(value: nextOldNode.value)
    newNode = newNode!.next

    oldNode = nextOldNode
  }

  tail = newNode
}

This method will replace the existing nodes of your linked list with newly allocated ones with the same value.

Now find all other methods in LinkedList marked with the mutating keyword and call copyNodes at the top of every method.

There are six methods in total:

• push

• append

• insert(after:)

• pop

• removeLast

• remove(after:)

After you’ve completed the retrofits, the last example function call should yield the following output:

---Example of linked list cow---
List1: 1 -> 2
List2: 1 -> 2
After appending 3 to list2
List1: 1 -> 2
List2: 1 -> 2 -> 3

Which is what you want! Well, other than introducing a O(n) overhead on every mutating call…

Optimizing COW

The O(n) overhead on every mutating call is unacceptable. Two strategies help alleviate this problem. The first is to avoid copying when the nodes only have one owner.

isKnownUniquelyReferenced

In the Swift standard library lives a function named isKnownUniquelyReferenced. This function can be used to determine whether or not an object has exactly one reference to it. Test this out in the linked list COW example.

In the last example function call, find the line where you wrote var list2 = list1 and update that to the following:

print("List1 uniquely referenced: \(isKnownUniquelyReferenced(&list1.head))")
var list2 = list1
print("List1 uniquely referenced: \(isKnownUniquelyReferenced(&list1.head))")

You should see two new lines in the console:

List1 uniquely referenced: true
List1 uniquely referenced: false

Using isKnownUniquelyReferenced, you can check whether or not the underlying node objects are shared! Since you’ve verified this behavior, remove the two print statements. Your path is clear. Add the following condition to the top of copyNodes:

guard !isKnownUniquelyReferenced(&head) else {
  return
}

You can be pleased that COW is still very much in effect:

---Example of linked list cow---
List1: 1 -> 2
List2: 1 -> 2
After appending 3 to list2
List1: 1 -> 2
List2: 1 -> 2 -> 3

With this change, your linked list performance will reclaim its previous performance with the benefits of COW.

A minor predicament

Add the following code inside your previous example code:

print("Removing middle node on list2")
if let node = list2.node(at: 0) {
  list2.remove(after: node)
}
print("List2: \(list2)")

You should see the following console output:

---Example of linked list cow---
List1: 1 -> 2
List2: 1 -> 2
After appending 3 to list2
List1: 1 -> 2
List2: 1 -> 2 -> 3  
Removing middle node on list2
List2: 1 -> 2 -> 3

The remove operation is no longer working. The reason for this lies in the CoW optimization we made. Because every mutation can trigger a copy of the nodes, the remove(after:) implementation is making a removal on the wrong set of nodes. To rectify that, you’ll write a specialized version of the copyNodes method. Head back into LinkedList.swift in your Sources directory and write the following just below the copyNodes method:

private mutating func copyNodes(returningCopyOf node: Node<Value>?) -> Node<Value>? {
  guard !isKnownUniquelyReferenced(&head) else {
    return nil
  }
  guard var oldNode = head else {
    return nil
  }

  head = Node(value: oldNode.value)
  var newNode = head
  var nodeCopy: Node<Value>?

  while let nextOldNode = oldNode.next {
    if oldNode === node {
      nodeCopy = newNode
    }
    newNode!.next = Node(value: nextOldNode.value)
    newNode = newNode!.next
    oldNode = nextOldNode
  }

  return nodeCopy
}

This method shares many similarities with the previous implementation. The main difference is that it will return the newly copied node based on the passed in parameter. Update the remove(after:) method to the following:

@discardableResult
public mutating func remove(after node: Node<Value>) -> Value? {
  guard let node = copyNodes(returningCopyOf: node) else { return nil }
  defer {
    if node.next === tail {
      tail = node
    }
    node.next = node.next?.next
  }
  return node.next?.value
}

You’re now using the method you just created and performing the removal on the newly copied node.

Sharing nodes

The second optimization is a partial sharing of nodes. As it turns out, there are certain scenarios where you can avoid a copy. A comprehensive evaluation of all the scenarios is beyond the scope of this book, but this will give you an idea about what’s involved.

Take a look at the following example (no need to write this down):

var list1 = LinkedList<Int>()
(1...3).forEach { list1.append($0) }
var list2 = list1

Now consider the consequence of doing a push operation on list2 with cow disabled:

list2.push(0)

Is list1 affected by push operation on list2? Not in this case! If you were to print the two lists, you’ll get the following output:

List1: 1 -> 2 -> 3
List2: 0 -> 1 -> 2 -> 3

The result of pushing 100 to list1 in this case is also safe:

list1.push(100)

If you were to print the two lists now, you’d get the following output:

List1: 100 -> 1 -> 2 -> 3
List2: 0 -> 1 -> 2 -> 3

The unidirectional nature of the linked list means that head-first insertions can ignore the “COW tax”!

Key points

• Linked lists are linear and unidirectional. As soon as you move a reference from one node to another, you can’t go back.
• Linked lists have a O(1) time complexity for head first insertions. Arrays have O(n) time complexity for head-first insertions.
• Conforming to Swift collection protocols such as Sequence and Collection automatically gives you access to many helpful methods.
• Copy-on-write behavior lets you achieve value semantics while maintaining good performance.