In this post I’ll show how to implement a Linked List in Swift. For this post there’s also a Playground version that works with Xcode 10 and above. If you prefer to read it you can find it here.
Linked lists are type of list with certain characteristics relating to the performance of insertion, deletion, and traversal.
They are valuable when maintaining lists where reference items don’t need to be looked up by index and the performance of insertion and
deletion is important. Linked list works by having each node in the list maintain a reference to the next node. Here we’ll implement
what’s called a doubly linked list where each node contains a list to the previous as well.
2016-07-17: Initial version in Swift 3
2018-11-11: Updated for Swift 4, fixed a few bugs in the implementation. Added tests
To start of we need to implement a node container that will hold our values and the reference to the next and previous values.
We’ll make it generic over the type T. Because Linked List are based on reference semantics we are going to use a class rather
than a struct. We adopt CustomStringConvertible for nicer output.
Note that the type of next and previous are NodeType? because it’s valid for a node to not have a next or previous node. The start
node will not have a previous node and the end node will never have a next node.
The List itself
Now let’s build the initial list structure. It will have two references, the start and end nodes, a count, a isEmpty method at first. Again
the start and end nodes are optional because a list can be empty, however one invariant is that a non empty list always has both a start
and end node. We are making the list a class rather than a struct for reasons that’ll become apparent when we talk about copy-on-write in the end.
This is the basic structure of our linked list. Of course we cannot do anything with it quite yet.
Let’s implement some operations so that we can actually use our linked list productively. We’ll start by implementing
the basics append, remove, node(at:), and value(at:). You might think that node(at:) and value(at:) does the same thing, but as we’ll
see returning the node allows us to then use the node when calling remove.
This is fairly straightforward. We first find the previous end node, make a new end node with the provided value and then update the next node
for the previous node and the previous node for the new end node. Note that this works both for the case when there was a previousNode and
when there wasn’t. There’s no need to check previousNode for nil instead we can use the ? operator.
Finding values and nodes by index
Now let’s implement node/value lookup. Let’s start with a private helper function that makes it simple to iterate over all nodes and optionally
stop when we find something interesting. This will have complexity O(n) since it needs to go through all nodes in the worst case.
Now that we have our iterate function we can start using it by implementing node(at:) and value(at:)
Let’s now add the ability to remove values and nodes from the linked list. Here we’ll see why node(at:) is important to support fast removals.
As you can see here remove(at:) is O(n) because it has to first find the node at the given index before removing it
while remove(node:) is only O(1) because the node is already given. An implementation of remove(value:) would also be
O(n) because it would have to find the correct node in a similar way as remove(at:)
Making the list swiftier
The swift runtime provides a set of protocols that we can adopt to make instances of LikendList behave more like any
of the other collections in swift.
protocol(was SequenceType in Swift 2) allows the list to be iterated over using the for..in construct and adds a bunch
of new methods to the type. Some of these are forEach, map, and filter.
All we have to do to get all this is implement the method makeIterator that returns an iterator conforming to the
IteratorProcotol. Let’s first create the iterator LinkedListIterator. A question to ask is wether the Iterator
should be an iterator of T or of Node<T>. I’m opting for Node<T> here.
And now we conform to Sequence by implementing makeIterator
And now we can do things like
It would be useful if LinkedList itself was equatable so we could compare instances of LinkedList<T> to other instances of LinkedList<T>. Let us implement the Equatable protocol for LinkedList. A LinkedList can only be Equatable if the values it contains are so we add this additional constraint.
It’s also possible to implement Collection for further benefits such as subscript support. However Collections generally feature
O(1) subscript behaviour and since our LinkedList is O(n) it might be confusing to do so. I’m opting to skip it
Now let’s write some test to ensure that we haven’t made any errors in the implementaiton.
Copy on Write
Most data structures in Swift are structs, but use a method called copy-on-write(COW) to reduce the amount of copying required by
only copying the data structure before writes. Let’s implement this for our LinkedList. The general idea is to create a struct that wraps
our LinkedList and delegates tasks to the underlying class. When mutating methods are invoked we’ll explicitly make a copy of the underlying
class and perform the actions on that copy. We also need to add a method to copy all the underlying data in our LinkedList.
For brevity I’m skipping over implementing Sequence for LinkedListCOW. As you can see from the implementation of
LinkedListCOW we simply delegate all read-only calls to the underlying LinkedList called storage. However
for mutating methods(remove(node:), remove(atIndex:), and append(value:)) we use the property mutableStorage
that first makes a copy for the storage for us if the storage is not uniquely referenced e.g if more than one object has
a reference to it. To illustrate this let’s implement CustomStringConvertible and print the storage’s position in memory.
As you can see here when we assign list1 to list2 we are performing a struct copy, but we are only copying the reference to the internal
storage which is a very cheap operation. As long as we don’t make any modifications to list2 both structs share the same underlying storage.
It’s only when we append to list2 that the copy occurs, hence copy-on-write.