And here comes my second post in the series about linked lists in Swift. In the first post we have implemented the basics to make our linked list work. Now, let’s make our linked list a little bit more „Swifty“.
To start with it would be very nice if we could iterate over the elements of our linked list in the same manner as that’s common with the other sequence types in Swift, i.e. Arrays or Dictionaries. In fact, that’s not too difficult. First of all we need an iterator which conforms to the IteratorProtocol. It remembers where we are in the sequence and give its next element.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
public struct LinkedListIterator<T>: IteratorProtocol { // let's create an iterator for our linked list public typealias Element = Node<T> // the type of each node in the list private var currentNode: Element? // the current node in the iteration fileprivate init(startNode: Element?) { // let's initiate the iterator currentNode = startNode // just set the current node } public mutating func next() -> LinkedListIterator.Element? { // get the next element in the list let node = currentNode // take the current node currentNode = currentNode?.next // and remember the next one, so the current node may // be invalidated in the iteration return node // return the node (not only the object, i.e. node?.value) } } |
So, what’s the element of our sequence? I prefer to define the node to be the element rather than its value. This has the advantage that we can look at the neighbours of the element while we are iterating. Alternatively we could define the generic type T to be the element type of our iterator and return the value of the current node in „next“:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
public struct LinkedListIterator<T>: IteratorProtocol { // let's create an iterator for our linked list public typealias Element = T // the type of each node in the list private var currentNode: Node<T>? // the current node in the iteration fileprivate init(startNode: Node<T>?) { // let's initiate the iterator currentNode = startNode // just set the current node } public mutating func next() -> LinkedListIterator.Element? { // get the next element in the list let node = currentNode // take the current node currentNode = currentNode?.next // and remember the next one, so the current node may // be invalidated in the iteration return node?.value // return value of the node } } |
We have defined our iterator to be a struct as its recommended by Apple. Since our method „next“ is changing properties of its struct (a value type) we have to flag it being „mutating“.
Let’s stick to the first variant. The rest is quite simple. We make our linked list conform to the Sequence protocol and implement the makeIterator method:
|
1 2 3 4 5 6 7 8 |
public class LinkedList<T>: Sequence { // the linked list, finally, conforming to the sequence protocol public typealias Iterator = LinkedListIterator<T> // the type of our iterator public func makeIterator() -> LinkedList.Iterator { // let's create our iterator return LinkedListIterator(startNode: head) // initialise it with the head of our list } … |
That’s it. Now we can loop very elegantly over our linked list:
|
1 2 3 4 5 6 7 8 9 |
let myFirstList = LinkedList<String>() myFirstList.append(value: "First item") myFirstList.append(value: "Second item") myFirstList.append(value: "Third item") Swift.print("The list: \(myFirstList)") for item in myFirstList { Swift.print("\(item.value)") } |
With the result:
|
1 2 3 4 |
The list: [First item, Second item, Third item] First item Second item Third item |
Nice, isn’t it? Another useful feature would be the possibility to create a linked list from some other kind of sequence, e.g. an array. This is done by a special init:
|
1 2 3 4 5 6 7 8 9 |
public init() { // just needed to add further inits } public init<S: Sequence>(_ elements: S) where S.Iterator.Element == T { // create the list from an other sequence for element in elements { // iterate over all elements in the supplied sequence append(value: element) // and extend our list } } |
We have to create a (dummy) default init to add further ones. Our new init takes a sequence of generic types T, loops over all elements and appends each element to our list. Very straightforward. Let’s see if it works:
|
1 2 3 |
let stringArray = ["1. item", "2. item", "3. item"] let mySecondList = LinkedList<String>(stringArray) Swift.print("The second list: \(mySecondList)“) |
Yes, everything is fine:
|
1 |
The second list: [1. item, 2. item, 3. item] |
The last thing for today is subscripts. An element in an array can be accessed by a subscript and we want to have that in our linked list as well:
|
1 2 3 4 5 |
public subscript(index: Int) -> T { // allow the list to be subscripted let node = nodeAt(index: index) // get the node at the specified index assert(node != nil) // make sure, its not nil return node!.value // and return its value } |
This time I decided to return the value of the node and not the node itself. You may choose whatever you prefer. Let’s test that as well:
|
1 |
Swift.print("Element 1: \(mySecondList[1])") |
Yes, that’s also ok:
|
1 |
Element 1: 2. item |
That’s it for today. Here is the playground of our enhanced linked list.
The next posts of this series will cover the following objectives:
- Some more convenience methods
- Serialising
So stay tuned.