This is my third post about linked lists in Swift. In the previous post we’ve made our linked list a little bit more „Swifty“. Today I want to introduce some more convenient methods to make life easier.
One thing I was missing from the original developers is an easy way to insert a new node before or after a given one. This is one of the main reasons for me to use linked lists at all. Of course, you can remember the index in the list of the given node and insert a new node at or before this index but that is ugly and inefficient for long lists. The node itself knows its neighbours, so its easy to implement these methods.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
public func insert(value: T, afterNode node: Node<T>?) { // insert an object after a supplied node if node == nil { // we want to insert at the top of the list insert(value: value, atIndex: 0) // make the new node be index 0 } else { // not at the top of the list insert(value: value, prev: node, next: node!.next) // insert it between the supplied node and its follower } } public func insert(value: T, beforeNode node: Node<T>?) { // insert an object before a supplied node if node == nil { // we want to insert at the end of the list append(value: value) // just append the object } else { // not at the end of the list insert(value: value, prev: node!.previous, next: node) // insert it between the previous node and its follower } } |
We just have to check if we want to insert before the first node in the list or after the last one. We have implemented the necessary methods already. Now we can see the advantage of choosing the node as the iterator element since we can insert new nodes within a for-loop:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
let stringArray = ["1. item", "2. item", "3. item"] let mySecondList = LinkedList<String>(stringArray) Swift.print("The second list: \(mySecondList.description)") for item in mySecondList { Swift.print("Item: \(item.value)") if item.value == "2. item" { mySecondList.insert(value: "Item 1b", beforeNode: item) mySecondList.insert(value: "Item 2b", afterNode: item) } } Swift.print("The second list, modified: \(mySecondList.description)") |
In this example I have searched the list for the second item and inserted new nodes before and after that. The loop is not disturbed by these operations:
|
1 2 3 4 5 |
The second list: [1. item, 2. item, 3. item] Item: 1. item Item: 2. item Item: 3. item The second list, modified: [1. item, Item 1b, 2. item, Item 2b, 3. item] |
Nice, isn’t it?
The second thing I want to add is a method to return the index of a given node in the list:
|
1 2 3 4 5 6 7 8 9 10 |
public func indexOf(node n: Node<T>) -> Int? { // get the index of a supplied node in the list var i = 0 // start at the beginning var node = head // with the head of the list while node != nil { // and iterate over the whole list if node! === n { return i } // until we find the identical node: return its index i += 1 // increase the index node = node!.next // and take the next item } return nil // could not find the supplied node } |
We just loop over the whole list until we find the supplied node. Notice that we have to use the identity operator (===) here since we do not want to test against equality but against identity. If we do not find the node we return nil. Does it work?
|
1 2 3 4 5 |
for item in mySecondList { if item.value == "2. item" { Swift.print("Item: \(item.value) at index \(mySecondList.indexOf(node: item)!)") } } |
Yes, looks like:
|
1 |
Item: 2. item at index 2 |
My third idea for today is the possibility of removing a node from its list without referencing the list itself. At some point it may be necessary to remove a node without knowing explicitly in which list it is stored (i.e. if you have several lists of the same type). This makes it necessary to store the list in the node:
|
1 2 3 4 5 6 |
fileprivate weak var list: LinkedList<T>? // let's keep a pointer to the list as well init(value: T, list: LinkedList<T>) { // let's initialise our node self.value = value // that's the object we want to keep self.list = list // and remember our list as well } |
Also, we have to modify the insert methods of the linked list where we create the nodes:
|
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 |
public func append(value: T) { // append a new node at the end of the list let newNode = Node(value: value, list: self) // 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 } private func insert(value: T, prev: NodeType?, next: NodeType?) { // insert a new node between neighbours let newNode = Node(value: value, list: self) // 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 } |
And now we can implement our new method in the Node class:
|
1 2 3 4 5 6 7 |
public func removeFromList() -> T { // let's remove this node from the list if let l = list { // yes, we do know our list return l.remove(node: self) // let the list do it's job } else { // oh no, no list known (any more) return value // just return our object } } |
By preparing this post I stumbled over a problem here. Although everything looks easy and correct it crashes in the example playground:
error: Execution was interrupted, reason: EXC_BAD_ACCESS (code=2, address=0x7ffee70a6fa0).
This problem is present only in the playground (Xcode 9.2) and not in a real project. By debugging a little bit I pinned it down to the extension with the CustomStringConvertible protocol. Removing this protocol from our linked list lets the problem vanish:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
extension LinkedList { public var description: String { var text = "[" var node = head while node != nil { text += "\(node!.value)" node = node!.next if node != nil { text += ", " } } return text + "]" } } |
„Stranger and stranger“ as Alice would say. So, we have to use the description directly for the time being.
Update: With the release of Xcode 10.1 this problem disappeared. So, from now on it seems to be safe to make the LinkedList to be CustomStringConvertible and to print the list directly (without referencing the description).
Now we can test that as well:
|
1 2 3 4 5 6 7 |
for item in mySecondList { Swift.print("Item: \(item.value)") if item.value == "2. item" { item.removeFromList() } } Swift.print("The second list, further modified: \(mySecondList.description)") |
with the result:
|
1 2 3 4 5 6 |
Item: 1. item Item: Item 1b Item: 2. item Item: Item 2b Item: 3. item The second list, further modified: [1. item, Item 1b, Item 2b, 3. item] |
Again, we can modify the list without disturbing the loop.
The last thing for today is the implementation of an endless loop or a ring. Sometimes it’s necessary to start in the middle of the list and loop through it by continuing at the top when the bottom is reached (maybe even several times or endlessly). Our Node has a property which points to the next node in the list; we would need a (computed) property which points to the next node in the list or the first one if we reached the end. Here it is:
|
1 2 3 4 5 6 7 8 9 10 11 |
var nextOrFirst: NodeType? { // a computed property to make endless loops possible if next == nil { // we reached the end of the list if let l = list { // just to be safe return l.head // start again from the top } else { // must have unlinked the object return nil // can't do anything with it } } else { // not reached end yet return next // take the next node } } |
As you can see, for this we need the pointer to the list in the node again. Let’s test that as well:
|
1 2 3 4 5 |
var item = mySecondList.nodeAt(index: 2) for _ in 0 ..< mySecondList.count { Swift.print("\(item!.value)") item = item!.nextOrFirst } |
with the result:
|
1 2 3 4 |
Item 2b 3. item 1. item Item 1b |
You see, we looped over the end of list and continued at the top.
That’s it for today. Here is the playground of our enhanced linked list.
The next and last post of this series will cover the following objective:
- Serialising
So stay tuned.