A linked list is a sequence of data items, just like an array. But where an array allocates a big block of memory to store the objects, the elements in a linked list are totally separate objects in memory and are connected through links:
+--------+ +--------+ +--------+ +--------+ | | | | | | | | | node 0 |--->| node 1 |--->| node 2 |--->| node 3 | | | | | | | | | +--------+ +--------+ +--------+ +--------+The elements of a linked list are referred to as nodes. The above picture shows a singly linked list, where each node only has a reference -- or a "pointer" -- to the next node. In a doubly linked list, shown below, nodes also have pointers to the previous node:
+--------+ +--------+ +--------+ +--------+ | |--->| |--->| |--->| | | node 0 | | node 1 | | node 2 | | node 3 | | | Node? { if index >= 0 { var node = head var i = index while node != nil { if i == 0 { return node } i -= 1 node = node!.next } } return nil }The loop looks a little different but it does the same thing: it starts at head and then keeps following the node.next pointers to step through the list. We're done when we've seen index nodes, i.e. when the counter has reached 0.
Try it out:
For fun we can implement a subscript method too:
public subscript[index: Int] -> T { let node = nodeAt[index] assert[node != nil] return node!.value }Now you can write the following:
It crashes on list[2] because there is no node at that index.
So far we've written code to add new nodes to the end of the list, but that's slow because you need to find the end of the list first. [It would be fast if we used a tail pointer.] For this reason, if the order of the items in the list doesn't matter, you should insert at the front of the list instead. That's always an O[1] operation.
Let's write a method that lets you insert a new node at any index in the list. First, we'll define a helper function:
private func nodesBeforeAndAfter[index: Int] -> [Node?, Node?] { assert[index >= 0] var i = index var next = head var prev: Node? while next != nil && i > 0 { i -= 1 prev = next next = next!.next } assert[i == 0] return [prev, next] }This returns a tuple containing the node currently at the specified index and the node that immediately precedes it, if any. The loop is very similar to nodeAtIndex[], except that here we also keep track of what the previous node is as we iterate through the list.
Let's look at an example. Suppose we have the following list:
head --> A --> B --> C --> D --> E --> nilWe want to find the nodes before and after index 3. As we start the loop, i = 3, next points at "A", and prev is nil.
head --> A --> B --> C --> D --> E --> nil nextWe decrement i, make prev point to "A", and move next to the next node, "B":
Again, we decrement i and update the pointers. Now prev points to "B", and next points to "C":
head --> A --> B --> C --> D --> E --> F --> nil prev nextAs you can see, prev always follows one behind next. We do this one more time and then i equals 0 and we exit the loop:
head --> A --> B --> C --> D --> E --> F --> nil prev nextThe assert[] after the loop checks whether there really were enough nodes in the list. If i > 0 at this point, then the specified index was too large.
Note: If any of the loops in this article don't make much sense to you, then draw a linked list on a piece of paper and step through the loop by hand, just like what we did here.
For this example, the function returns ["C", "D"] because "D" is the node at index 3 and "C" is the one right before that.
Now that we have this helper function, we can write the method for inserting nodes:
Some remarks about this method:
First, we need to find where to insert this node. After calling the helper method, prev points to the previous node and next is the node currently at the given index. We'll insert the new node in between these two. Note that prev can be nil [index is 0], next can be nil [index equals size of the list], or both can be nil if the list is empty.
Create the new node and connect the previous and next pointers. Because the local prev and next variables are optionals and may be nil, so we use optional chaining here.
If the new node is being inserted at the front of the list, we need to update the head pointer. [Note: If the list had a tail pointer, you'd also need to update that pointer here if next == nil, because that means the last element has changed.]
Try it out:
Also try adding new nodes to the front and back of the list, to verify that this works properly.
Note: The nodesBeforeAndAfter[] and insert[atIndex] functions can also be used with a singly linked list because we don't depend on the node's previous pointer to find the previous element.
What else do we need? Removing nodes, of course! First we'll do removeAll[], which is really simple:
public func removeAll[] { head = nil }If you had a tail pointer, you'd set it to nil here too.
Next we'll add some functions that let you remove individual nodes. If you already have a reference to the node, then using removeNode[] is the most optimal because you don't need to iterate through the list to find the node first.
public func remove[node: Node] -> T { let prev = node.previous let next = node.next if let prev = prev { prev.next = next } else { head = next } next?.previous = prev node.previous = nil node.next = nil return node.value }When we take this node out of the list, we break the links to the previous node and the next node. To make the list whole again we must connect the previous node to the next node.
Don't forget the head pointer! If this was the first node in the list then head needs to be updated to point to the next node. [Likewise for when you have a tail pointer and this was the last node]. Of course, if there are no more nodes left, head should become nil.
Try it out:
If you don't have a reference to the node, you can use removeLast[] or removeAt[]:
public func removeLast[] -> T { assert[!isEmpty] return remove[node: last!] } public func removeAt[_ index: Int] -> T { let node = nodeAt[index] assert[node != nil] return remove[node: node!] }All these removal functions also return the value from the removed element.
Note: For a singly linked list, removing the last node is slightly more complicated. You can't just use last to find the end of the list because you also need a reference to the second-to-last node. Instead, use the nodesBeforeAndAfter[] helper method. If the list has a tail pointer, then removeLast[] is really quick, but you do need to remember to make tail point to the previous node.
There's a few other fun things we can do with our LinkedList class. It's handy to have some sort of readable debug output:
extension LinkedList: CustomStringConvertible { public var description: String { var s = "[" var node = head while node != nil { s += "\[node!.value]" node = node!.next if node != nil { s += ", " } } return s + "]" } }This will print the list like so:
[Hello, Swift, World]How about reversing a list, so that the head becomes the tail and vice versa? There is a very fast algorithm for that:
public func reverse[] { var node = head while let currentNode = node { node = currentNode.next swap[¤tNode.next, ¤tNode.previous] head = currentNode } }This loops through the entire list and simply swaps the next and previous pointers of each node. It also moves the head pointer to the very last element. [If you had a tail pointer you'd also need to update it.] You end up with something like this:
You can use it like this:
And here's filter:
public func filter[predicate: T -> Bool] -> LinkedList { let result = LinkedList[] var node = head while node != nil { if predicate[node!.value] { result.append[node!.value] } node = node!.next } return result }And a silly example:
Exercise for the reader: These implementations of map[] and filter[] aren't very fast because they append[] the new node to the end of the new list. Recall that append is O[n] because it needs to scan through the entire list to find the last node. Can you make this faster? [Hint: keep track of the last node that you added.]
An alternative approach
The version of LinkedList you've seen so far uses nodes that are classes and therefore have reference semantics. Nothing wrong with that, but that does make them a bit more heavyweight than Swift's other collections such as Array and Dictionary.
It is possible to implement a linked list with value semantics using an enum. That would look somewhat like this:
enum ListNode { indirect case Node[T, next: ListNode] case End }The big difference with the class-based version is that any modification you make to this list will result in a new copy being created. Whether that's what you want or not depends on the application.
[I might fill out this section in more detail if there's a demand for it.]
Some things to keep in mind
Linked lists are flexible but many operations are O[n].
When performing operations on a linked list, you always need to be careful to update the relevant next and previous pointers, and possibly also the head and tail pointers. If you mess this up, your list will no longer be correct and your program will likely crash at some point. Be careful!
When processing lists, you can often use recursion: process the first element and then recursively call the function again on the rest of the list. Youre done when there is no next element. This is why linked lists are the foundation of functional programming languages such as LISP.
Written for Swift Algorithm Club by Matthijs Hollemans