Holy Swift

Holy Swift

Linked Lists with Sequence and IteratorProtocol in Swift

Linked Lists with Sequence and IteratorProtocol in Swift

Subscribe to my newsletter and never miss my upcoming articles

Hallo iedereen, Leo hier.

This week I came up with a problem about 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 using it. It's always great to know that we have the features provided by Arrays, Dictionaries and Sets, this empower us developer to write better code and to pickup 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 generate a 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 why and the drawbacks conforming to it.

No more talking, let's code! But first....

The Painting

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

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 have 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 do it:

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 no much to say. The next var will be pointing to the next node, if is nil that means that 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 handle 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:

Screenshot 2021-09-08 at 08.32.16.png

He is literally telling us:

Hey man, it's awesome you want to use the for-in loop syntax but you have to give me something that conforms to Sequence Protocol.

The Sequence protocol has one requirement you have to provide a implementation to this:

Screenshot 2021-09-08 at 08.50.33.png

To implement it just add:

class LinkedList: Sequence {
    var root: LinkedListNode?

    func makeIterator() -> LinkedListIterator {
        return LinkedListIterator(start: root)
    }
}

The makeIterator function just return an object to conform

The problem is... The our LinkedListIterator doesn't exist. To create it you should create a 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 a implementation of 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 behaviour in the code. For example, if you have various defer clauses inside your function they will run in reverse order they are explicit in the code. Kind misleading, isn't ? Use whatever fits better for you 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:

Screenshot 2021-09-09 at 07.51.47.png

Infinite Loop

You can also make a 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!

Summary

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 as I enjoyed write this article. If you want to support this blog you can Buy Me a Coffee or just leave a comment saying hello. You can also sponsor posts! Just reach me in LinkedIn or Twitter for details.

Thanks for the reading and... That's all folks.

credits: image

Interested in reading more such articles from Leonardo Maia Pugliese?

Support the author by donating an amount of your choice.

 
Share this