Iterate through a Linked List in Swift

There’s an IteratorProtocol?

Image for post
Image for post
Photo by Emma Matthews Digital Content Production on Unsplash

This article is about an implementation of Linked Lists in Swift, where you can iterate through the list. The theory of Linked Lists is covered in my own article, as are Linked Lists in Swift. This article is about doing better.

Difficulty: Beginner | Easy | Normal | Challenging

Prerequisites:

  • Coding in Swift Playgrounds (guide HERE)

This article uses Linked Lists as motivation for implementing the IteratorProtocol. It does help to have some understanding of Linked Lists, but this is not completely necessary.

My implementation makes use of the defer keyword in Swift.

Terminology

Class: An object that defines properties and methods in common

Iterator: In Swift, a protocol that allows you to loop through a sequence. That is, the protocol supplies values one at a time

IteratorProtocol: A protocol that provides the values of a sequence one at a time

Protocol: A blueprint on methods, properties and requirements to suit a piece of functionality

Sequence: A Protocol that provides sequenced, iterative access to elements of the sequence

Data structure: A way of formatting data

Head: The first (or parent, or root) node

Linked List: A linear collection of data elements, made up of a head node with zero or more connected nodes. The order of this list is given by pointers from each node to the next

Node: The basic unit of a data structure

Null Pointer: A pointer that does not point to anywhere

Pointer: An object that stores a memory address

Tail: The linked list, after the head

The Motivation

Reading out from a Linked List is always quite tricky, and requires some skill, perhaps implementing CustomStringConvertible.

As ever, there is a better way. Step in Sequence.

A sequence can be iterated over, and provides great functions like contains(_ :) that users of an API expect.

Any Loop in Swift can be iterated (often using for…in).

A simple example

let numbers: [Int] = [1,2,3]
for num in numbers {
print (num)
}

This is known as the iterator design pattern (or at least this is implemented in the background for you).

A custom type can conform to Sequence by implementing makeIterator() (a factory method that returns the specific iterator for the type) into the type. Trust me, although a sequence is simply a list of elements it enables you to perform useful operations that you will want to use…trust me!

The Linked List Example

Since Array conforms to the Collection protocol so already implemenents iterators.

This means minimal examples making arrays conform to sequence and their elements to IteratorProtocol are rather superfluous.

Instead, let us use a Linked List as our example.

The Basic Linked List

I’ve implemented a Linked List many times, but seldom with the LinkedList class expressed below that holds the head of the Linked List.

The problem that I wish to solve is to iterate over the nodes.

for element in list {
print(element.item)
}

The Swift compiler helps out, by telling us that we’re missing something. In this case, we are missing out conformance to the Sequence protocol.

Image for post
Image for post

So we are going to…

The LinkedList class will conform to the Sequence protocol.

To do so, we need to implement a makeIterator() method that returns an iterator.

Now the AnyIterator struct is the item we are looking for, and because we are returning a Node there is no particular problem in Swift.

So the makeIterator() method is hit just once, returning our AnyIterator which will return the next() element.

Let us look at the makeIterator() in detail:

which can be called through the following:

So we ask the Linked List to create an iterator, and it provides us with next() each time, until there is no extra element in the Linked List.

Instead of the while loop we can just use a for…in loop

This particular implementation bears repeatability, that is we can iterate over the elements of LinkedList twice and the elements are read out of the LinkedList twice!

We can, instead, take another approach. We can make our LinkedList class conform to both Sequence and IteratorProtocol, which is perhaps easier to understand since we just implement the next() function.

The code? Pretty easy since we return our head node, and then once the closure is out of scope move onto the next node in the list.

This is all fine, and works as before in that we can print out the elements in the list. But what if we filter(_:) after?

But…but there is an element with 1 in our Linked list.

Yes: but

Conforming to the sequence protocol does not guarantee that iterating over the elements is non-destructive

We aren’t guarenteed repeated access when iterating over our elements.

This bears repeating, in it’s own heading

The Sequence Protocol: Repeated Access

Conforming to the sequence protocol does not guarantee that iterating over the elements is non-destructive.

In order to guarentee this we should conform to the collection protocol.

Conclusion:

Iteration over a sequence can be finite or infinite (imagine a circular queue). In any case, conforming to sequence seems like a pretty good deal, you get the for…in pattern as well as lots of fun functions like contains and filter.

However, we need to be mindful if our iteration is destructive or not. We don’t get any guarantees from Swift so need to make sure that we understand the code that we are writing and understand the benefits of the different approaches using Sequence and IteratorProtocol

Further study:

Apple have documentation on Sequence. I would recommend this article about Linked Lists in Swift (Ok, I wrote it — but still…).

The Twitter contact:

Any questions? You can get in touch with me HERE

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store