# Data Structures and Algorithms in Swift: Linked List

In part 1 of this series I have talked about Arrays. If you haven’t given it a read, I highly recommend taking a look at it **here**. In this part of the series I will be writing about another data structure that is very commonly used in problem solving: **Linked List**.

A Linked list data structure is composed of a data and a reference to the next item in that Linked List. Each item in a Linked List is called a Node. The Nodes are interconnected by the reference that they store in them. The Node class are self-referential in the sense that they have a reference to the next node in the sequence. Unlike Arrays, the Linked List data structure is not built into Swift. So, in this post I will write my own implementation of it to show some of its functionality. There are two types of Linked List:

# 1. Singly Linked List

# 2. Doubly Linked List

Let’s talk about Singly Linked List first, from hereon referred to as Linked List. The Node class in a Linked List consists of a data type and a reference to the next Node in the Linked List as shown below:

class Node<T> { internal var data: T internal var next: Node<T>?init(data: T) {self.data = dataself.next =nil}

}

Here, our Node class has a data type that is a generic. We are using generics to make our Node class more versatile so that we can store any data type. If you don’t know about generics don’t worry too much about it for now. Just imagine the `T`

as a type, such as `Int`

or `String`

. There are many variations of Linked List implementations. Here I will show the one where the linked list consist of a head node (other variations include Linked List having a reference to a Linked List, Linked List having both a head node and a tail node, etc). Here is a depiction of a list with two nodes.

The first node has a data (of type `T`

, assume `Int`

for simplicity) and a reference to the next node. This is the head node. The second node also has data, but the reference to the next node is null. Hence, it is not pointing to anything else. Here is our Linked List class (named is SinglyLinkedList to avoid confusion)

classSinglyLinkedList<T> {internallvarhead: Node<T>?internalvarcount: Int = 0publicinit() {}init(first: Node<T>) {self.head = first }}

Our `SinglyLinkedList`

class has a `head`

node, a `count`

private variable to keep count of the number of nodes and two initializers. So far, so good. But, we need more functions to be able to add/remove items from the list, to know about the size of the list, etc. Lets implement those now.

classSinglyLinkedList<T> { // existing code...public funcisEmpty() ->Bool {count == 0

return

}publicfuncsize() -> Int {

// return a count of the number of items in the list

returncount

} // adds an element at the beginning of the list

publicfuncadd(element: T) {letnode = Node<T>(data: element)

node.next = head

head = node

count += 1 }

// removes and returns an element from the beginning of the list

publicfuncremove() -> T? { // Check if list is empty

ifisEmpty() {

returnnil} // get the data from the head

letitem =self.head?.data// move the head.head =

selfself.head?.next // decrease the count

count -= 1returnitem

}}

We have added four functions. `empty()`

and`size()`

returns whether the list is empty and the count of the number of elements in the list respectively. `add`

adds an elements at the beginning of the list and `remove`

removes an element from the beginning of the list. Let’s add one more to complete this implementation. We should have a way to look at the first element of the list without deleting it. Here is the code for it:

publicfuncpeek() -> T? { // if list is empty, return nil

ifisEmpty() {

returnnil} // otherwise return the data stored in head

returnhead?.data

}

As you can see, our implementation of the Linked List is pretty straightforward. In a sense our implementation of this Linked List looks like a Stack (which I will discuss in a later post), which is a FIFO (First In First Out) structure. Since we are returning the data stored, instead of the Node, from the Linked List, we are essentially restricting how our list can be modified. Had we returned a Node, the List would then become traversable using the reference to that node (using the `next`

reference) and would then allow addition to and deletion from any part of the list. For now, we will stick with this implementation. Let’s try out our list.

// instantiate a singly linked list to store integersvarsinglyLinkedList = SinglyLinkedList<Int>()// add two elements to it

singlyLinkedList.add(element: 2)

singlyLinkedList.add(element: 3)// print the size and the head element// prints "Size is 2"

print("Size is \(singlyLinkedList.size())")// prints "Head is 3"

print("Head is \(singlyLinkedList.peek()!)")// remove the first element

singlyLinkedList.remove()// peek into the list again// prints "New Head is 2"

print("New Head is \(singlyLinkedList.peek()!)")

Great! Our Singly Linked List is working as expected. For our Singly Linked List, we will stay with this implementation. In your own implementation, you can feel free to return the node instead of the data, but be extra careful when you do so. Let’s move on to our Doubly Linked List data structure.

The Doubly Linked List is almost similar to the Singly Linked List, with the exception of having a reference to the previous node as well. As a result, there are mode codes to write and have the reference to the previous node will also allow us to delete an element from any position easily (this is achievable in Singly Linked list too, but we have to pay more attention while doing so). Having the reference to the previous node will also allow us to traverse through the list in reverse order (from back to front) as well. Let’s first look at the implementation of the node of a Doubly Linked List.

classDoublyNode {// to store data

private(set)vardata: Int

// Reference to the next node

varnext: DoublyNode?//Reference to the previous node

varprev: DoublyNode?init(data: Int) {

self.data = data

self.next =nil.prev =

selfnil}

}

We have named it DoublyNode to distinguish between the Node from our Singly Linked List Structure, but it looks pretty similar. The only new thing is the reference to the previous node. In the `init`

method we set both the `next`

and the `prev`

to `nil`

. Again, looks pretty simple so far, right? Let’s now look at how our DoublyLinkedList structure will look like.

classDoublyLinkedList {varhead: DoublyNode

fileprivatevarcount: Int = 0init(first: DoublyNode) {

add(element: first)

}publicfuncisEmpty() -> Bool {

returncount == 0

}publicfuncsize() -> Int {

returncount

} // adds an element at the beginning of the lis

publicfuncadd(element: DoublyNode) {

letnode = element // if list is empty, assign to head

ifisEmpty() {

self.head = node

self.head?.next =nil.head?.prev =

selfnil}

else{

// head needs to be moved

lettemporaryHead =self.head

self.head = node

node.next = temporaryHead

temporaryHead?.prev = node

self.head?.prev =nil}

count += 1

}}

We have the usual functions, function to check the size of the list and whether the list is empty or not, exactly like the SinglyLinkedList. We also have the `add`

method that adds an element at the beginning of the list. Notice how we have taken advantage of the `add`

method in the `init`

to avoid mistake and code duplication. Let’s go through the `add`

method line by line. First, we assign the passed element to a temporary variable. Next, we check whether the list is empty or not. If the list is empty, we simply assign the new node to the head node and set the previous and next node of head to be `nil`

. If, however, the list is not empty, then we need to move the head since the new element will be the new head of the list. First, we keep a temporary reference to the head node. Next, we assign the new node to be the head node. We then assign the next node of our new head node to that of our old head node. The previous node of the new head node is set to be `nil`

and the previous node of our old head node is set to our new head node. In either cases (list being empty or not), we increase the number of element in the list by 1. Hence, we increase the `count`

by 1. The challenges with DoublyLinkedList is that we have to make sure all the references are updated properly. Otherwise we will end up with buggy states in our list.

We are done with the add method, but, how will the `remove`

method look like? Let’s have a look at it.

// removes an element from the beginning of the listpublicfuncremove() -> DoublyNode? {

ifisEmpty() {

returnnil} // remove the head

letitem =self.headself.head =self.head?.next

self.head?.prev =nilitem?.prev =nilitem?.next =

nil

count -= 1returnitem

}

If the list is empty, we return `nil`

and we are done. Easy. What if it is not? Again, with my implementation, we are removing from the front of the linked list. If the list is not empty, then we remove the head and move the reference to the head to the next node. First, we store the head node in a temporary node called `item`

. Next, we move our head to the next element. We also update the previous node of our new head to be `nil`

. Done, we have moved our head. Next, we set the `next`

and `prev`

node of that temporary node (which was our old head now) to `nil`

. This is to make sure when we return the node, the user cannot modify our list using the returned node. We could have easily returned the data like we did in our SinglyLinkedList implementation, but here I just wanted to show how we can also return a node. Next, we decrease the count of element by 1. Finally, we return the removed node. This completes our `remove`

method. I will show one more method, which allows us to remove an element from any position. Here is how it looks like.

// removes the node containing element as datapublicfuncremove(_element: Int) -> DoublyNode? {

ifisEmpty() {

returnnil}

vartemporaryNode =self.head

whiletemporaryNode !=nil&& temporaryNode?.data != element

{

temporaryNode = temporaryNode?.next

} // found the element or nil

iftemporaryNode ==nil{

// we didn't find a node matching the data

returnnil} // if the found node is head node, we move head

iftemporaryNode?.data ==self.head?.data {

returnremove()

}letprevious = temporaryNode?.prev

letnext = temporaryNode?.next previous?.next = next

next?.prev = previous count -= 1 temporaryNode?.prev =niltemporaryNode?.next =

nilreturntemporaryNode}

It almost looks like remove. The only difference is that we try to find the data and only remove it if it exists and update the references. Otherwise, we return `nil`

. Also, note how we handle the case of `head`

differently. If the matching element is the head node, then we use our existing `remove`

method to handle that case. Let’s test our DoublyLinkedList and see if it works as expected.

extensionDoublyLinkedList: CustomStringConvertible {

vardescription: String {

varstring = ""

varnode = headwhileletn = node {

string += " \(n.data) "

node = node?.next

}

returnstring

}

}doublyNode1 = DoublyNode(data: 1)

letletdoublyNode2 = DoublyNode(data: 2)letdoublyNode3 = DoublyNode(data: 3)letdoublyLinkedList = DoublyLinkedList(first: doublyNode1)print("List = \(doublyLinkedList)")

// "List = 1 \n"doublyLinkedList.add(element: doublyNode2)doublyLinkedList.add(element: doublyNode3)

print(doublyLinkedList.size())

// 3

print(doublyLinkedList)

// "3 2 1 \n"doublyLinkedList.remove()

print(doublyLinkedList.size()) // 2

print(doublyLinkedList) // "2 1 \n"doublyLinkedList.remove(3) // doesn't exist

print(doublyLinkedList) // "2 1 \n"doublyLinkedList.remove(1)

print(doublyLinkedList) // "2 \n"doublyLinkedList.remove(2)

print(doublyLinkedList) // "\n"

Perfect! Our DoublyLinkedList data structure works as expected. Currently, our DoublyLinkedList only works for `Int`

. You can modify it to accept any type by using generics like our SinglyLinkedList structure. I leave it up to you to as an exercise to add the `add(element: Int, at: Int)`

method, that adds an element at the position specified by the `at`

parameter. Hopefully you will be able to do it easily. For reference, look at the `remove(element: Int)`

method.

This concludes our LinkedList data structure. Hopefully, I was able to help you understand this data structure a bit better. Using these data structures, later we will implement our next data structures (like Stack, Queue, Tree, etc). Until then, keep coding.