This is the first post of my upcoming series devoted to linked lists. I like this data structure very much because of its elegance and efficiency in situations where you have to insert and remove objects quite often and randomly. Unfortunately there is no standard data type „Linked List“ in Swift, so we have to build one by ourself. That’s not too difficult and there are quite a few example implementations in the web (e.g. from Chris Pilcher or Hugo Tunius). I’ll take these as a starting point and add some of my own thinkings and optimisations.
Let’s start with the nodes. We want to store objects of arbitrary type. It is convenient to wrap these objects in our own data type which also holds the references to the previous and next objects in the list. There is one important word in the sentence above: „reference“. We need to hold a reference to the neighbouring objects, not the objects themselves. So we have to use a class for the wrapper and not a struct. In Swift structs are value types and putting the neighbours of the same type in a struct would cause a disastrous recursion, so the compiler forbids that. But enough of the preamble, let’s look at the code:
|
1 2 3 4 5 6 7 8 9 10 |
public class Node<T> { typealias NodeType = Node<T> // just to shorten definitions var value: T // that's the object we want to keep in the list var next: NodeType? // since this is a class, that's the pointer to the next node weak var previous: NodeType? // and thats the one the previous node init(value: T) { // let's initialise our node self.value = value // remember its value } } |
That doesn’t look too complicated, does it? Since we want to store objects of arbitrary type we have to use generics. The pointers to the previous and next objects in the list may be nil so we make them optionals. And removing one node should not lead to a dead lock of referencing so we have to make one of these pointers weak. The init is also very simple, we just store the supplied object (or a reference to it if its type is a class).
OK, let’s turn to the linked list itself. Here is the mere trivial part:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
public class LinkedList<T> { // the linked list, finally typealias NodeType = Node<T> // the type of our nodes fileprivate var head: NodeType? // the first element of our list private var tail: NodeType? // and the last one; both may be nil public fileprivate(set) var count: Int = 0 // the number of elements in the list at any given time public var isEmpty: Bool { // convenience property to test for emptiness return head == nil // if the head is nil the list is empty } public var first: Node<T>? { // get the head of the list return head } public var last: Node<T>? { // and its tail return tail } … } |
We keep references to the first and the last node of the list; since the list may be empty they have to be optionals. And we allow ourself a counter to the number of nodes in the list. That is not strictly necessary but it speeds up some operations. Finally we have some computed properties.
And now the more interesting methods:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
… public func append(value: T) { // append a new node at the end of the list let newNode = Node(value: value) // create the node with the object if let tailNode = tail { // we do have an end (list is not empty) newNode.previous = tailNode // remember that node in our new one tailNode.next = newNode // and make the new node the new tail } else { // the list is empty head = newNode // make our new node the head of the list } tail = newNode // our new node is the (new) end of the list count += 1 // and increase our counter } public func nodeAt(index: Int) -> Node<T>? { // get the node at the specified index if index >= 0 { // make sure the index is positive var node = head // start at the head of the list var i = index // the count down while node != nil { // iterate over the list if i == 0 { return node } // until we finished the countdown and return the node i -= 1 // countdown node = node!.next // and take the next item } } return nil // index is out of range } public func removeAll() { // empty the list head = nil // clear its head tail = nil // and its tail count = 0 // and reset the counter } public func remove(node: Node<T>) -> T { // remove a node from the list let prev = node.previous // first get its neighbours let next = node.next if let prev = prev { // we are not at the top of the list prev.next = next // make the previous node point to our following one } else { // we are at the top of the list head = next // make our follower the new head of the list } next?.previous = prev // and make our follower point to our previous node if next == nil { // we are at the end of the list and do not have a follower tail = prev // make the previous node the new tail of the list } node.previous = nil // and clear the pointers in our node node.next = nil count -= 1 // decrease the counter return node.value // and return our object } private func nodesBeforeAndAfter(index: Int) -> (NodeType?, NodeType?) { // get the nodes before and after an index assert(index >= 0) // make sure the index is positive (+ 0) var i = index // let's countdown var next = head // start at the top of the list var prev: NodeType? // in the beginning the previous node is nil while next != nil && i > 0 { // iterate over the list i -= 1 // and count down prev = next // the previous node becomes the current one next = next!.next // and the current one the next } assert(i == 0) // make sure we hit the specified index return (prev, next) // and return the previous and the current node } private func insert(value: T, prev: NodeType?, next: NodeType?) { // insert a new node between neighbours let newNode = Node(value: value) // create the new node from the object newNode.previous = prev // let's point to the old neighbours newNode.next = next prev?.next = newNode // and from the neighbours to our new node next?.previous = newNode if prev == nil { // we inserted at the top of the list head = newNode // the head will be our new node } if next == nil { // we inserted at the end of the list tail = newNode // the tail will be our new node } count += 1 // and increase the counter } public func insert(value: T, atIndex index: Int) { // insert an object at a specified index let (prev, next) = nodesBeforeAndAfter(index: index) // get the neighbours at the index insert(value: value, prev: prev, next: next) // and insert it in between } } |
These methods are quite straightforward and should be easy to understand. Some words about the remove method: Since we do not want to keep references of possibly later deleted nodes we have to clear the pointers to the previous and next nodes of the unlinked node. And, for convenience we give the original object back to the caller if we remove/unlink a node. For the insertion of nodes we use a private helper method to get the adjacent nodes of a given index; maybe we can use that for other purposes later as well.
And that’s it. We have implemented the main functionality of a linked list. Just let us add a description property to print out the linked list prettily:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
extension LinkedList: CustomStringConvertible { public var description: String { var text = "[" var node = head while node != nil { text += "\(node!.value)" node = node!.next if node != nil { text += ", " } } return text + "]" } } |
Now its time to make some tests:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
let myFirstList = LinkedList<String>() myFirstList.append(value: "First item") myFirstList.append(value: "Second item") myFirstList.append(value: "Third item") Swift.print("The list: \(myFirstList)") Swift.print("count: \(myFirstList.count)") myFirstList.insert(value: "New second item", atIndex: 1) Swift.print("The list: \(myFirstList)") Swift.print("count: \(myFirstList.count)") Swift.print("Remove new third item: \(myFirstList.remove(node: myFirstList.nodeAt(index: 2)!))") Swift.print("The list: \(myFirstList)") Swift.print("count: \(myFirstList.count)") |
with the result:
|
1 2 3 4 5 6 7 |
The list: [First item, Second item, Third item] count: 3 The list: [First item, New second item, Second item, Third item] count: 4 Remove new third item: Second item The list: [First item, New second item, Third item] count: 3 |
You see it works as expected. Here is the playground of our achievements so far.
The next posts of this series will cover the following objectives:
- More Swifty features (i.e. iterators and index)
- Some more convenience methods
- Serialising
So stay tuned.