Linked Lists and LL Algorithms in Swift

Chain it up in Swift

Image for post
Image for post
Photo by Markus Spiske on Unsplash

This article is about the implementation of linked lists in Swift. The theory is covered in my own article.

Difficulty: Beginner | Easy | Normal | Challenging

Prerequisites:

  • Coding in Swift Playgrounds (guide HERE)
  • While loops in Swift (guide HERE)

Terminology

Class: An object that defines properties and methods in common

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

Implementing a Node in Swift -Integer

A choice has been made to implement a node that contains an Integer as the data payload. If you wish to see a node that is generic (that is, can carry any data) please see the second half of this article.

Since our Node class needs to reference itself, a class has been chosen to represent the Node type (although an enum is a value type that can reference itself, I have chosen not to use that type to represent a Node in this case)

This initialiser requires both a piece of data, and the next node in the linked list.

In terms of creating an instance of a Node, Swift helps us out just as if we are creating an instance of any class.

We are going to create three nodes that are linked as a linked list, containing three elements

Image for post
Image for post

interestingly here I’ve chosen to create the nodes in reverse order.

The reason for this is that each node is connected to the next — and doing them in normal order would mean linking a node to a node that does not yet exist.

How can you link to a node that doesn’t exist? You can’t.

So…

Swift doesn’t give us a good view of what we’ve created — so how can we be sure that we’ve correctly created these three nodes?

printing an element gives us the following output:

__lldb_expr_10.Node

yes, we get it. It’s a node.

When we conform to CustomStringConvertable we need to provide a description that Swift will provide when we print the element.

Which (when we print the head) gives the following output:

Data: 0 { Data: 1 { Data: 2 { null } } }

This is much nicer, as each node is described as part of the chain now.

Here we are going to use a while loop to traverse the linked list. We know when we have gone to the end of the linked list since the last element always points to nil!

This prints the following to the console:

0
1
2

But it might be worth exploring what happened here.

Image for post
Image for post

which leads us to the output to the console (as expected) as 0,1 and 2.

Remove a node from the head of the linked list

Remove an element (a node)from the linked list from the head is a relatively easy operation.

Image for post
Image for post

In Swift though, we need to make sure that head has a next element — and this is implemented through optionals in Swift.

Since the old headNode has no reference it can now be deallocated, so there is no dangling head node.

Remove a node from the middle of the linked list

This is slightly more tricky than removing a node from the head of a linked list.

Image for post
Image for post

We remove this second node and deal with the hanging node.

Reverse a linked list

The theory goes something like the following:

Image for post
Image for post

A linked list can be reversed through the following code in Swift.

To be noted here, is the creation of a empty node initially that will be the new tail of data:

Conclusion:

Linked lists are really important in programming, and this guide has shown you how linked lists can be implemented in the best programming language (Swift).

Reversing a singularly linked list is a little tricky, and with that we can easily introduce the concept of a doubly linked list to cope with that. But more on that topic on another day (i.e. follow me).

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