
What, Where and How to use it
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 = data
self.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)
class SinglyLinkedList<T> {
internal var head: Node<T>?
internal var count: Int = 0
public init() {}
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.
class SinglyLinkedList<T> {
// existing code...
public func isEmpty() -> Bool {
return count == 0
}
public func size() -> Int {
// return a count of the number of items in the list
return count
}
// adds an element at the beginning of the list
public func add(element: T) {
let node = Node<T>(data: element)
node.next = head
head = node
count += 1
}
// removes and returns an element from the beginning of the list
public func remove() -> T? {
// Check if list is empty
if isEmpty() {
return nil
}
// get the data from the head
let item = self.head?.data
// move the head
self.head = self.head?.next
// decrease the count
count -= 1
return item
}
}
We have added four functions. empty()
andsize()
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:
public func peek() -> T? {
// if list is empty, return nil
if isEmpty() {
return nil
}
// otherwise return the data stored in head
return head?.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 integers
var singlyLinkedList = 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.
class DoublyNode {
// to store data
private(set) var data: Int
// Reference to the next node
var next: DoublyNode?
// Reference to the previous node
var prev: DoublyNode?
init(data: Int) {
self.data = data
self.next = nil
self.prev = nil
}
}
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.
class DoublyLinkedList {
var head: DoublyNode
fileprivate var count: Int = 0
init(first: DoublyNode) {
add(element: first)
}
public func isEmpty() -> Bool {
return count == 0
}
public func size() -> Int {
return count
}
// adds an element at the beginning of the lis
public func add(element: DoublyNode) {
let node = element
// if list is empty, assign to head
if isEmpty() {
self.head = node
self.head?.next = nil
self.head?.prev = nil
} else {
// head needs to be moved
let temporaryHead = 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 list
public func remove() -> DoublyNode? {
if isEmpty() {
return nil
}
// remove the head
let item = self.head
self.head = self.head?.next
self.head?.prev = nil
item?.prev = nil
item?.next = nil
count -= 1
return item
}
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 data
public func remove(_ element: Int) -> DoublyNode? {
if isEmpty() {
return nil
}
var temporaryNode = self.head
while temporaryNode != nil && temporaryNode?.data != element
{
temporaryNode = temporaryNode?.next
}
// found the element or nil
if temporaryNode == nil {
// we didn't find a node matching the data
return nil
}
// if the found node is head node, we move head
if temporaryNode?.data == self.head?.data {
return remove()
}
let previous = temporaryNode?.prev
let next = temporaryNode?.next
previous?.next = next
next?.prev = previous
count -= 1
temporaryNode?.prev = nil
temporaryNode?.next = nil
return temporaryNode
}
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.
extension DoublyLinkedList: CustomStringConvertible {
var description: String {
var string = ""
var node = head
while let n = node {
string += " (n.data) "
node = node?.next
}
return string
}
}
let doublyNode1 = DoublyNode(data: 1)
let doublyNode2 = DoublyNode(data: 2)
let doublyNode3 = DoublyNode(data: 3)
let doublyLinkedList = 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.