# 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!

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 tail: Node<Value>?

public init() {}

public var isEmpty: Bool {
}
}

public var description: String {
return "Empty list"
}
}
}
``````

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) {
if tail == nil {
}
}
``````

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") {
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") {
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 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
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") {
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 {
if isEmpty {
tail = nil
}
}
}
``````

`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") {
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
return nil
}
// 2
guard head.next != nil else {
return pop()
}
// 3

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") {
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") {
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.

``````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 {
}
// 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") {
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") {
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
}

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

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

``````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>? {
return nil
}
guard var oldNode = head else {
return nil
}

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.

Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.