Singly Linked Lists in Swift

Published in

Nerd For Tech

12 min readMar 14, 2022

A singly linked list is one of many data structures. A data structure is a collection of data, the relationships between them, and the functionality or methods that can be used to access them. The conventional data structures used extensively in Swift are arrays, sets and dictionaries. These data structures cover a majority of use cases. In some cases though, using other data structures is more efficient.

Why should you care?

Aside from expanding your data structure toolkit that you can deploy efficiently on an ad hoc basis, you can also increase the probability of being hired by major tech companies by learning about data structures. FAANG is known to base the majority of their interview questions on the theory and practical implementation of data structures.

As mentioned above, there are use cases in which it makes sense to prefer linked lists over arrays or other data structures. As you probably know, arrays index all elements contained in them. This characteristic cuts both ways — it comes with advantages and disadvantages.

One area in which arrays excel at is access. Accessing arrays is efficient because of the way they are structured. We don’t have to shift indices of the elements or traverse through the array in order to access the element we want. We simply do this:

On the other hand, inserting elements at the top of the array is inefficient.

The inefficiency stems from the need to re-index all of the elements. Using a linked list is a better choice here.

How do Linked Lists work?

There are three types of linked lists: Singly, doubly and circular. I will stick to singly linked lists in this article. A singly linked list consists of following properties:

A head (first node)
A tail (last node)

That is all. The circular elements are called nodes. A node consists of following properties:

A value
A reference to the next node

Let’s go through the code:

the use of generics enables building linked lists with any type we want
in the initializer, we assign a default value of nil to the next parameter, since there might not be a next node
isEmpty is a computed property that will be set to true if there is no head

The simplicity of this structure is elusive. Think about it — how do we access, for instance, the third value in the list? A linked list is, unlike an array, not indexed.

This is a bad way for constructing a linked list, obviously. We will create methods that will obviate manually instantiating nodes. The purpose here is to show that it was necessary to iterate through the nodes with the .next property in order to access the desired node.

push(_ value: T)

It is advised to try to implement the methods on your own at first.

we define a method called push that accepts a generic type and returns nothing
we instantiate a node with value (since we use generics, this can be a bool, a String etc.) and head (the next parameter is the reference to the next node)
if the tail is nil, we assign the head to the tail

Let’s go through the code step by step:

the first time we push a node to the list, the list doesn’t have neither a head nor a tail. So when we push(3), the node’s next property we instantiate is nil. We assign this node to the head.
the tail is still nil, so we assign the head to the tail. Now, both head and tail are 3. We can check this. Remove push(2) and push(1):

when we add push(2), the instantiated node has a value of 2 and its next property is the head we assigned earlier (which is 3). So our list looks like this right now 2 (head) -> 3 (tail)
since tail isn’t nil, the code block isn’t entered
notice how the push(_ value: T) method doesn’t change the tail once a tail is assigned via the first push

One thing is bothersome, though. It would be much more convenient if we printed our linked list so we could see what happens. The following variable is not mandatory, which is why I won’t explain it (also it might confuse you at this point). It is solely used for illustrative purposes:

Now we can see what happens with every call to push. Noice.

pop() -> T?

Removing node from the front of the list

we define a method called pop(), that doesn’t accept any parameters and returns a generic optional value
defer is used for executing code right before exiting the scope that the statement is contained in. This means, after return head, right before the scope is transferred outside, the code inside defer will be run

Sequence of events:
1. return head?.value
2. defer { // this code block is run }

when we pop() the first time, defer will be called but its code block won’t be executed yet
so we return.head (which is the node with value 1). This is the node that is being popped off the list
then the code block inside defer is run. The reason we use defer, is because we want to return the value of the previous head, before assigning a new node to it
the next property of the first node is 2, so head is 2 now
isEmpty is not nil (since head has a value) so this code block isn’t entered
self.print is called
the last time we pop(), we have to set head and tail to nil. Since 3 is the last value, its next property is nil (thus head is set to nil)
because head is nil, we enter the isEmpty code block and set tail to nil as well

append(_ value: T)

There are three things we have to do:

1. Create a reference to the node we are going to append
2. Assign a new tail
3. Consider the edge case of the list being empty

the first time we append, the list is empty. We instantiate a node with the value that was fed into the method
the instantiated node is being assigned to the next property of the tail. But since there is no tail, the optionally chained tail will produce nil
on line 5 a new tail is assigned (1).
head is nil, so the isEmpty code block is entered
head and tail are now the same
the second time we append, tail?.next gets set to the node we created (2).
This node is now the new tail

removeLast() -> Node<T>?

This one is different from the methods we used before. Remember that we have to iterate through the nodes to get the desired node. This was unnecessary up until now: When we used push(), we just had to assign a new head. There was no need to iterate through the list. Same goes for pop() and append(). All we had to do with append(), was to assign a new head and establish a connection between the previous head and the new head with the .next property. But how do we remove the last node? We have to assign the node prior to the node we are removing as the new tail. Since we are using a singly linked list, there is no pointer to the last node (as is the case with doubly linked lists). This means, the only way we can access the node prior to the one we will remove, is to iterate through the nodes beginning with the head.

Let’s go through the code:

if the list is empty, return nil
if there is just one node in the list, pop() it off
a while loop iterates through the list with the .next property
once the while loop finishes, set .next property to nil, assign new tail and return the node being removed

when we use removeLast() the first time, head is not nil, because we pushed three values before.
also, head.next is not nil
we create two variables: newTail and currentNode. As their names suggest, we use one to assign the new tail to and currentNode is the node that will be removed and returned by the function
newTail and currentNode get both set to the head node, which has a value of 1 (remember that we iterate from the beginning of the list)
the while loop will run as long as currentNode.next is not nil
during the first iteration of the loop, currentNode.next is 2, so the inner block of the loop is entered
think about what we want to achieve: Our goal is to have access to both 1) the node before the last one and 2) the last node. The first one will be the new tail and the last one will be returned. This can be achieved by implementing a lag between currentNode and newTail. So the logic within the while loop should set currentNode (what will be removed) to be one node post newTail (what will be the new tail, duh)
within the first iteration, newTail is set to 1 and currentNode to 2. First iteration completes
currentNode.next is 3, so we enter the while block
newTail is now 2
currentNode is now 3. Second iteration completes
currentNode.next is nil, so we break out of the loop
newTail.next is set to nil. By doing this, we remove the last node

prior 1 -> 2 -> 3
now   1 -> 2

tail is set to 2
currentNode (3) is returned

node(at index: Int) -> Node<T>?

This method returns a node at a given index.

guard statement protects the method from negative indices
just as we iterated from the beginning of the list with the removeLast() method, we have to do the same here. This is why head is stored in current, which will be used in the while loop
ask yourself how you would return the 736th node in a hypothetical giant linked list (or any node except the first and last one). Again, there are no indices to make use of. This can be done by incrementing a variable every time we pass a node in the list. We do this with current?.next (same way as removeLast())
the break out condition of the while loop ensures quitting the loop once the desired index is reached

linkedList.node(at: 1)

guard statement is passed
head is 1 and is stored in the variable current
counter starts with 0
the while condition is true so its code block is run (current?.next has a value and 0 < 1)
in order to traverse the list, we do the same as we did before with removeLast(): we store the next node of current, which is 2, in current
counter is 1, first iteration completes
current?.next is 3 and the counter is equal to the index (both 1), so the while condition is false and we break out of the loop
current is returned, which is the node with the value 2. For good measure we print the value of the node before we return

delete(at index: Int) -> Node<T>?

We employ the same strategy just like with removeLast() (there are some differences that I will elaborate soon):

with current.next we can iterate through the list
by counting at which node we currently are, we can quit the while loop when we arrived at the desired node
we implement a lag in the while code block
if the last or the first nodes are deleted, we simply return removeLast() and pop()

What happens when we delete node at index 1?

guard statement and if condition are skipped
current is 1
while condition is true, so code block is entered
previous is set to 1
current is set to 2
counter is incremented to 1
first iteration completes
on the second run the while condition is false because counter is equal to index (both 1), so the while loop breaks out
we check whether there is a next node. If not, it means that the aim is to remove the last node of the list, which is why we can use our removeLast() method
else, if there is no next node, we do previous?.next = current?.next

Prior to previous?.next = current?.next, our list looked like this:
1           ->           2           ->      3
previous   .next       current       .nextNow, it looks like this:
1           ->           3

In plain english, what we are saying is: “Hey previous node (which is 1). Are you there? If you are, please set your next property (which is 2 and of type Node<T>?) to the current node’s (if it exists) next (which is 3) property.” This is how we go from 1 -> 2 -> 3 to 1 -> 3.

insert(at index: Int, value: T)

Inserting node at given index with given value

We can employ a lot of things we have learned here. With one distinction — I want to show that you don’t have to stick to while loops.

Let’s work through the code:

guard is skipped
instantiate a new node with the value that was fed into the function
if is skipped (index is 1)
previous is 1
current is 1
for loop is entered because 0..<1
previous is 1
current is 3( because current?.next is 3, the list looks like this 1 -> 3 prior to us using insert())
first iteration completes
for loop condition is false, loop breaks out
previous?.next is 3, which is set to the next property of newNode (which was nil before). The new node is 2, so now newNode.next gives us 2 -> 3
if the next property of newNode was nil, we would enter the code block and use our append() method
on line 18, the next property of previous is set to 2. The previous node has a value of 1. This means, previous?.next = newNode gives us 1 -> 2
the end result is 1 -> 2 -> 3

reverse()

Congrats for coming this far through the blog, you nerd. Now lets slay the final boss — reversing a singly linked list!

Some caveats:

this time, we use 3 instead of 2 variables: previous, current and next. Why? Suppose we want to reverse 1 -> 2 -> 3. Let’s call them previousNode, currentNode and nextNode. The end product should be 3 -> 2 -> 1. Look at the second node, 2. Prior to reversing, previous node’s (1) next property was pointing at 2 and current node’s (2) next property was pointing at 3. Post reversing, next node’s (3) next property is pointing at 2 and current node’s (2) next property is pointing at 1. So in order to reverse a linked list, we have to mutate the next properties of the nodes while iterating through them.
tail becomes head and head becomes tail

Let’s go through the code: (with 1 -> 2 -> 3 as an example)

on line 3 we set the tail with the value of head
we create 3 variables: previousNode, currentNode, nextNode
previousNode is nil, currentNode is 1, and nextNode is 2
the while condition is true, since nextNode is not nil, so we enter the code block
previous is nil, so line 8 produces 1 -> nil
previousNode is now 1
currentNode is now 2
nextNode is now 3
as it becomes apparent, we are shifting our variables one node up through the list
first iteration completes
while condition is still true, because nextNode is not nil (it is 3)
since previousNode is 1 and currentNode is 2, line 8 will produce 2 -> 1
previousNode is now 2
currentNode is now 3
nextNode is now nil
second iteration completes
while condition is false, because nextNode is nil
line 13 produces 3 -> 2
we assign a new head
end result is 3 -> 2 -> 1

I hope I could help you. If you have any questions, just hit me up on twitter: ozgunyx