Hallo iedereen, Leo hier. The topic today is how to create Linked Lists with Sequence and IteratorProtocol in Swift.
This week I came up with a problem with Linked Lists. Although they are very simple to construct in Swift, you can power up them to use Swift sugar syntax for-in loop operation to help yourself use it. It’s always great to know that we have the features provided by `Arrays`, Dictionariesand `Sets`, this empowers us, developers, to write better code and to pick up exactly what we need to build our own reliable and usable data structures.
Swift comes with a lot of syntax sugars, the `for-in` loop is one example. When you use `for-in` Swift automatically maps to a while loop that calls the `makeIterator()` that generates an iterator for your type and finally calls `next()` on the iterator until it’s nil. One final thought is always before you conform to any protocols you always have to think about why and the drawbacks of conforming to them.
No more talking, let’s code! But first…
Painting of The Day
This painting is called “Landscape with Shepherds and Cows and at the Spring” made by Joseph Anton Koch. He lived from 27 July 1768 to 12 January 1839, he was an Austrian painter of Neoclassicism and later the German Romantic movement. He is perhaps the most significant neoclassical landscape painter.
Today I have no special reason to choose this painting, is just a beautiful landscape from a Neoclassicism Master.
The Problem – Linked Lists with Sequence and IteratorProtocol in Swift
You build your custom Linked List data structure and want to use `for-in` loop operation in it.
First, let’s create the base of our Linked List, we will use a Integer Linked List but you can also do a generic one too, just replace Int for T and use a generic parameter in the class declaration. A Linked List usually has two parts: the Linked List Node and the Linked List. The node is what will carry each part of the Linked List and the Linked List itself is a class with the root node reference.
Let’s write it down:
class LinkedListNode {
var value: Int
var next: LinkedListNode?
init(value: Int) {
self.value = value
}
}
class LinkedList {
var root: LinkedListNode?
}
It’s the most basic Linked List node, there’s not much to say. The next var will be pointing to the next node, if is nil that means the end of the list.
Now you need to create the Linked List and connect all nodes ( if you are actually building a real linked list this insert operation should be handled by the Linked List class, but for simplicity, we just add manually):
let list = LinkedList() let first = LinkedListNode(value: 1) let second = LinkedListNode(value: 2) let third = LinkedListNode(value: 3) list.root = first first.next = second second.next = third
Now we just need to iterate over it… But when you try to iterate over it you get this error:
He is literally telling us:
Hey man, it’s awesome you want to use the
for-inloop syntax but you have to give me something that conforms to Sequence Protocol.
Implementing the Sequence Protocol and Custom Iterator in Swift
The Sequence protocol has one requirement you have to provide an implementation to this:
To implement it just add:
class LinkedList: Sequence {
var root: LinkedListNode?
func makeIterator() -> LinkedListIterator {
return LinkedListIterator(start: root)
}
}
The makeIterator function just returns an object to conform
The problem is… Our LinkedListIterator doesn’t exist. To create it you should create an object that conforms to IteratorProtocol:
class LinkedListIterator: IteratorProtocol { // Mark 1
var current: LinkedListNode?
init(start: LinkedListNode?) {
current = start
}
func next() -> LinkedListNode? { // Mark 2
let actual = current
current = current?.next
return actual
}
}
Breaking it down:
1. On Mark 1 we create a class that conforms to Iterator protocol, this obligates us to provide an implementation of the next function.
2. The next function is where we return the next element of the sequence. Be sure to always retain the next value even if it’s a nil value.
You can also make the `next` function above a little more readable using defer:
func next() -> LinkedListNode? { // Mark 2
defer { current = current?.next }
return current
}
I’m not much akin to use defer because it has arbitrary behavior in the code. For example, if you have various defer clauses inside your function they will run in the reverse order they are explicit in the code. Kind misleading, isn’t it? Use whatever fits better for your codebase.
Now you can test your code using the `for-in` loop:
let list = LinkedList()
let first = LinkedListNode(value: 1)
let second = LinkedListNode(value: 2)
let third = LinkedListNode(value: 3)
list.root = first
first.next = second
second.next = third
for node in list {
dump(node.value)
}
Resulting in console print:
Infinite Loop
You can also make an infinite loop if you for some reason connect your last item in the list with the first:
third.next = first
So be careful when inserting items and connecting them inside your data structure.
And that’s all!
Next Steps on Algorithms
Now you know how to implement your own linked list with Swift’s sequence protocol, but how about only a tree problem involving showing only one side of the three? That is what you will solve in this article.
Working with string is essential for any algorithm solving studying, and is important to deal with repetitions and permutations, you can exercise your sliding windows pattern muscles with solving the longest substring without repeating character in Swift. There you will learn what is the dynamic sliding window pattern and how that can help you solve your problems involving Strings.
Summary – Linked Lists with Sequence and IteratorProtocol in Swift
Today we study how you can create your own data structures and empower them with the Swift Syntax. The example we gave was Linked Lists and you will be able to reproduce this with any other data structure. You can also create infinite loops if you are not careful enough!
That’s all my people, I hope you liked reading this article as much as I enjoyed writing it. If you want to support this blog you can Buy Me a Coffee or leave a comment saying hello. You can also sponsor posts and I’m open to freelance writing! You can reach me on LinkedIn or Twitter and send me an e-mail through the contact page.
Thanks for reading and… That’s all folks.
Credits:
