Károly Nyisztor

Data Structures in Swift - Part 2

Károly Nyisztor

Sep 6, 2019
20 Min read
10,506 Views

Sep 6, 2019
20 Min read
10,506 Views

Swift

Data Structures You Should Know

This is the second part of a two-part series on data structures in Swift. In the first part, we delved into generics and built-in Swift collection types. Check it out in case you missed it.

In this tutorial, we’re going implement some of Swift's most popular data structures from scratch.

Swift provides some handy collection types. We can use the generic Array, Set, and Dictionary structures right away. However, we may need custom collection types in specific instances. In the upcoming chapters, we’ll take a closer look at stacks, queues, and linked lists and discuss when we could use these specialized structures.

The Stack

Properties

The stack behaves like an array, in that it stores the elements in a specific order. However, unlike arrays, we can’t insert, retrieve and delete items from a stack using random access. Instead, the stack provides fast, constant time control over the first element in the list: it permits pushing a new item onto the start of the stack, peeking at the first item in the stack, and popping the most accessible item off the stack.

The stack provides a Last-In-First-Out (LIFO) access. The most recently added item can be accessed first (peek or pop). Here’s LIFO in action!

description

Using Stacks

The stack is useful if we need to retrieve the elements in the order in which we added them. For example, a stack would be useful for modeling an ever-growing pile of dirty laundry. The piece of clothing that you last tossed onto the pile is the first one that you can pick up to clean. Here, we are unable to pick out specific clothing randomly from within the enormous pile of clothes. Instead, our only way of picking clothes is off the top. This produces the LIFO system described above. Similar use cases exist for representing recursive calls, modeling paperwork on someone's desk, or keeping track of server transactions.

Stack: Array Implementation?

We could fulfill these requirements using an Array:

1var numbers = [Int]()
2numbers.append(1)
3numbers.append(2)
4numbers.append(3)
5var last = numbers.last // peek - returns 3
6last = numbers.popLast() // pop - returns 3
7last = numbers.popLast() // pop - returns 2
8last = numbers.popLast() // pop - returns 1

swift

But, the array does not prevent us from (accidentally) accessing the elements in a different order:

1last = numbers[2]
2numbers.remove(at: 3)

swift

Thus, if we want strict LIFO behavior, we have to use a stack implementation that does not operate as an array.

Our Stack needs three methods:

push() - to append a new item

peek() - gets the last element without removing or modifying it

pop() - removes the last element and returns it

Optionally, we can add a removeAll() method to clear the stack of its values.

Stack: Protocol-Oriented Approach

There are different ways to implement these requirements. Let’s follow a protocol-oriented approach and declare a protocol first.

1protocol Stackable {
2    associatedtype Element
3    mutating func push(_ element: Element)
4    func peek() -> Element?
5    mutating func pop() -> Element?
6    mutating func removeAll()
7}

swift

The Stackable protocol defines all the requirements needed to define a stack.

We use an associatedtype called Element that acts as a placeholder. Types that adopt the Stackable protocol can provide the exact type.

Notice the use of the mutating identifier next to all methods that change the contents of the stack. We must mark methods that modify a structure as mutating. Class methods can always modify the class. Thus we don’t need to use the mutating keyword in classes.

We used the mutating keyword in the Stackable protocol to also allow structs adopt it.

Stack: Generic Implementation

Next, we implement a generic stack.

1struct Stack<T>: Stackable {
2    typealias Element = T
3
4    fileprivate var elements = [Element]()
5
6    mutating func push(_ element: Element) {
7        elements.append(element)
8    }
9
10    func peek() -> Element? {
11        return elements.last
12    }
13
14    mutating func pop() -> Element? {
15        return elements.popLast()
16    }
17
18    mutating func removeAll() {
19        elements.removeAll()
20    }
21}

swift

Using generics in the protocol declaration (Stack<T>), we can make our Stack work with any type.

1var stackInt = Stack<Int>()
2var stackString = Stack<String>()
3var stackDate = Stack<Date>()

swift

We can use the stack as follows:

1stackInt.push(1)
2print("push() ->", stackInt)
3// Output: push() -> [1]
4
5stackInt.push(2)
6print("push() ->", stackInt)
7// Output: push() -> [1, 2]
8
9stackInt.push(3)
10print("push() ->", stackInt)
11// Output: push() -> [1, 2, 3]
12
13print("peek() ->", stackInt.peek() ?? "Stack is empty")
14// Output: peek() -> 3
15
16print("peek() ->", stackInt.peek() ?? "Stack is empty")
17// Output: peek() -> 3
18
19print("peek() ->", stackInt.peek() ?? "Stack is empty")
20// Output: peek() -> 3
21
22print("pop() ->", stackInt.pop() ?? "Stack is empty")
23// Output: pop() -> 3
24
25print("pop() ->", stackInt.pop() ?? "Stack is empty")
26// Output: pop() -> 2
27
28print("pop() ->", stackInt.pop() ?? "Stack is empty")
29// Output: pop() -> 1
30
31stackInt.pop()
32print(stackInt)  // Output:[]

swift

For better readability, we can add a custom description through a type extension. The CustomStringConvertible protocol defines the description computed property. By implementing it, we can add a custom description to our type. For our Stack type, we simply log the contents of the internal elements array.

1extension Stack: CustomStringConvertible {
2    var description: String {won'
3        return "\(elements)"
4    }
5}

swift

Queues

Queues: Properties

Unlike the stack, the queue is open at both ends. The queue provides First-In-First-Out (FIFO) access. New elements are added to the bottom of the queue. We can retrieve elements from the top of the queue.

Here’s an illustration of the queue in action:

description

We would use the queue to put things in line. Consider it when modeling lines for restaurants: people who are in line first get tables first. Similarly, we could model water coming out of a tube using a queue, snce water that goes through one end of the tube first leaves the other end first. Our queue needs to be able to:

Enqueue -- add items to the end of the queue

Dequeue -- pull the next items off the front of the queue

Peek -- check the next item in the queue

We will also add a removeAll method to our implementation.

Queues: Implementation

The Enqueuable protocol defines the requirements for a basic queue:

1protocol Enqueuable {
2    associatedtype Element
3    mutating func enqueue(_ element: Element)
4    func peek() -> Element?
5    mutating func dequeue() -> Element?
6    mutating func removeAll()
7}

swift

The enqueue(:) method adds an item to the bottom of the queue, whereas the dequeue() method removes and returns the element from the top. peek() simply returns the top element without removing it.

We could implement the Enqueuable protocol as follows:

1struct Queue<T>: Enqueuable {
2    typealias Element = T
3
4    fileprivate var elements = [Element]()
5
6    mutating func enqueue(_ element: Element) {
7        elements.append(element)
8    }
9
10    func peek() -> Element? {
11        return elements.first
12    }
13
14    mutating func dequeue() -> Element? {
15        guard elements.isEmpty == false else {
16            return nil
17        }
18        return elements.removeFirst()
19    }
20
21    mutating func removeAll() {
22        elements.removeAll()
23    }
24}
25
26extension Queue: CustomStringConvertible {
27    var description: String {
28        return "\(elements)"
29    }
30}

swift

We now have a generic Queue -- denoted by Queue<T> in the protocol declaration. We can use it with any type:

1var queueInt = Queue<Int>()
2var queueString = Queue<String>()
3var queueData = Queue<Data>()
4
5queueInt.enqueue(1)
6print("enqueue() ->", queueInt)
7// Output: enqueue() -> [1]
8
9queueInt.enqueue(2)
10print("enqueue() ->", queueInt)
11// Output: enqueue() -> [2]
12
13queueInt.enqueue(3)
14print("enqueue() ->", queueInt)
15// Output: enqueue() -> [3]
16
17print("peek() ->", queueInt.peek() ?? "Stack is empty")
18// Output: peek() -> 1
19
20print("peek() ->", queueInt.peek() ?? "Stack is empty")
21// Output: peek() -> 1
22
23print("peek() ->", queueInt.peek() ?? "Stack is empty")
24// Output: peek() -> 1
25
26print("dequeue() ->", queueInt.dequeue() ?? "Stack is empty")
27// Output: dequeue() -> 1
28
29print("dequeue() ->", queueInt.dequeue() ?? "Stack is empty")
30// Output: dequeue() -> 2
31
32print("dequeue() ->", queueInt.dequeue() ?? "Stack is empty")
33// Output: dequeue() -> 3
34
35queueInt.dequeue()
36print(queueInt)
37// Output: []

swift

Linked Lists

Linked lists are collections of data made of nodes that store a value and a pointer to the next node in the chain. Unlike arrays, linked lists do not allocate fixed amounts of memory in advance to store items. Instead, the items in a linked list are separate instances. Each block in the linked list is usually called node and gets added when needed.

A node is the individual part of a larger data structure.

You will encounter the node when considering other data structures like trees or graphs.

As mentioned before, each node in a linked list has a link to the next item. This type of node lets us create a singly-linked list, where each node holds a link to the next node.

This node structure means that we do not have constant time access to the elements in the middle of the linked list. However, this converts resizing and accessing the next node into constant time operations.

An example of a linked list would be a locomotive train. Each of the cars in the train are nodes: they each store something and have a link to the next car in the train. The train continues until one of the nodes (the caboose) points to nothing, marking the end of the list.

SLL

If a node has references for both the next and the previous node, we can build a doubly-linked list. This would be equivalent to each car in the train knowing the car before it and the car after it.

DLL

A node also needs to hold the data we want to store. So basically, for a double linked list we need a type which has a property for storing data and two properties which represent links to the previous and the next nodes.

Linked List Implementation

Let's create a protocol which defines these requirements. I'm going to call it Linkable.

The protocol should not restrict the node's data type. Thus, we'll use a placeholder type using the associatedtype keyword.

Each node can link to the previous and the next node. So, we need two read-write properties. Let's call them simply next and previous. These should be optional properties, since they both can be nil:

nil ends

Finally, we add an initializer and we're almost done with the Linkable protocol. Here's what we've got so far:

1protocol Linkable {
2    associatedtype D
3    var value: D { get }
4    var next: Self? { get set }
5    var previous: Self? { get set }
6
7    init(value: D)
8}

swift

There is still an issue that we need to address. To surface the problem, let's see what happens if we try to adopt the protocol in a value type.

So, we declare the StringNode structure and make it conform to the Linkable` protocol. Xcode will generate the following code to satisfy the protocol requirements:

1struct StringNode: Linkable {
2    var value: String
3    var next: StringNode?
4    var previous: StringNode?
5
6    init(value: String) {
7        self.value = value
8    }
9}

swift

Unfortunately, this code won't compile: "Value type 'StringNode' cannot have a stored property that recursively contains it." The reason for this strange compiler error is not obvious, so let's try to clarify it a bit.

Structs and Memory Allocation

The error has to do with memory allocation. Value types keep their data directly in their storage location. Whereas with reference types, the data exists somewhere else and the storage location only stores a reference to it.

And here's what that means for us: StringNode is a value type (a struct). As such, it must store its data in its storage location. Thus, the compiler must know the exact size of the struct is before allocating the required amount of memory. To figure out the size of the struct, the compiler must know the size of the struct's properties, too.

A StringNode instance could contain two values of the same type. And each of these properties could also contain two values of StringNode type, and so on. Because of this recursion, there is no way to calculate the StringNode's memory requirements.

Thus, the compiler won't let us create a structure that recursively contains another instance of the same type.

The Workaround

We need to enforce reference type semantics for our node types. We change the Linkable protocol to a class-only protocol by inheriting from AnyObject. (AnyObject is a protocol that can only be adopted by classes.)

1protocol Linkable: AnyObject {
2    associatedtype D
3    var value: D { get }
4    var next: Self? { get set }
5    var previous: Self? { get set }
6
7    init(value: D)
8}

swift

We're going to unleash the power of generics to create a Node class that can hold arbitrary types:

1final fileprivate class Node<T>: Linkable {
2    private var storage: T
3
4    var next: Node<T>?
5    var previous: Node<T>?
6
7    var value: T {
8        return storage
9    }
10
11    init(value: T) {
12        storage = value
13    }
14}

swift

The Node class file is private because clients should not interact with it directly. It’s final to prevent subclassing. This ensures that abstraction is not breached.

DLL Implementation

Alright, now it's time to switch gears and start implementing our Double Linked List. As usual, we'll first come up with a protocol.

1protocol LinkedListProtocol {
2    associatedtype T
3    func append(value: T)
4    subscript(index: Int) -> T? { get set }
5    var first: T? { get }
6    var last: T? { get }
7}

swift

The append() method lets us add new values to the linked list. The LinkedList protocol defines a subscript to set and retrieve values by index.

For a double linked list, it is useful to have a reference to the first and the last value in the list. So, we introduce the first and last gettable property requirements.

Next, we'll implement a conforming generic type. LinkedList allows creating a linked lists out of any type. The head and the tail properties are used as internal storage for the first and last properties.

1final class LinkedList<T>: LinkedListProtocol {
2    fileprivate var head: Node<T>?
3    fileprivate var tail: Node<T>?
4
5    var first: T? {
6        return head?.value
7    }
8
9    var last: T? {
10        return tail?.value
11    }
12    …
13}

swift

The append() method first creates a new node with the provided value. We append the new node to the list. If the list is empty, this will be the very first node and the head and the tail will point to it.

1func append(value: T) {
2    // create new node
3    let node = Node(value: value)
4    // if tail is nil, the list is empty
5    if let last = tail {
6        node.previous = last
7        last.next = node
8        tail = node // set tail
9    } else {
10        head = node // first node, both head and tail point to it
11        tail = node
12    }
13}

swift

Next, we implement the index subscript.

1subscript(index: Int) -> T? {
2    get {
3        let node = self.node(at: index)
4        return node?.value
5    }
6    set {
7        guard index >= 0 else {
8            return
9        }
10        if let value = newValue {
11            // newValue non-nil -> insert
12            let node = Node(value: value)
13            self.insert(node: node, at: index)
14        } else {
15            // newValue nil -> remove
16            self.remove(at: index)
17        }
18    }
19}
20
21// Returns the node at given index
22private func node(at index: Int) -> Node<T>? {
23    // check for valid index and non-empty list
24    guard index >= 0,
25        head != nil else {
26            return nil
27    }
28
29    var node = head
30    var i = 0
31    while node != nil {
32        if i == index {
33            return node
34        }
35        i += 1
36        node = node?.next
37    }
38    return nil
39}

swift

The getter calls the private helper method node(at:), which traverses the list of nodes by following the subsequent next pointers.

The getter either returns a valid value or nil (if the index is invalid or in case of validation issues.)

The setter serves two purposes: if we assign a valid value, it will insert a new node at the given index. If we assign nil, it will delete the node.

For insertion, we rely on the insert(node: at:) helper method. Which in turn uses the node(at:) method to find the node at the given index.

1private func insert(node: Node<T>, at index: Int) {
2    if index == 0,
3        tail == nil {
4        head = node
5        tail = node
6    } else {
7        guard let nodeAtIndex = self.node(at: index) else {
8            print("Index out of bounds.")
9            return
10        }
11
12        if nodeAtIndex.previous == nil {
13            head = node
14        }
15
16        // set previous and next links
17        // set new node's previous link
18        node.previous = nodeAtIndex.previous
19        nodeAtIndex.previous?.next = node
20
21        // set new node's next link
22        node.next = nodeAtIndex
23        nodeAtIndex.previous = node
24    }
25}

swift

We're going to insert the new node between the node at the given index and the previous one. We must also take care of edge cases like empty list or inserting at the front of the linked list.

To remove a value from the linked list, we must assign nil to the node at the given index. The remove(at:) helper method performs the logic required to unlink the selected node and deallocate it. Also, we must update the head and tail pointers when the node is removed from the beginning or the end of the list.

1private func remove(at index: Int) {
2    var nodeAtIndex = self.node(at: index)
3    guard nodeAtIndex != nil else {
4        print("Index out of bounds.")
5        return
6    }
7
8    let previousNode = nodeAtIndex?.previous
9    let nextNode = nodeAtIndex?.next
10
11    // head?
12    if previousNode == nil {
13        head = nextNode
14    }
15
16    // tail?
17    if nodeAtIndex?.next == nil {
18        tail = previousNode
19    }
20
21    // set previous and next links
22    // we unlink nodeAtIndex from its neighbours
23    previousNode?.next = nextNode
24    nextNode?.previous = previousNode
25
26    // finally, delete the node
27    nodeAtIndex = nil
28}

swift

Now, we have a working Doubly-Linked List implementation. We can append, insert, retrieve and delete values from it.

Conclusion

We could add further features like e.g. the ability to iterate over its elements. But I'll leave this as an exercise to the reader!

Hint: make the LinkedList class conform to the Sequence and the IteratorProtocol protocols and implement the next() method. The next() method returns an optional T? instance.

Internally, the method must keep track of the current node, which is initially set to the head node. Subsequent calls to the next() method set the current node to the next node in the linked list. Once you have these in place, you can use a for - in loop to traverse the linked list.

Stay tuned! I'm going to talk about the Iterator pattern and the other behavioral design patterns in my upcoming Pluralsight course. In the meantime, head over to my Swift courses on Pluralsight

I hope you found this guide informative or engaging. Thanks for reading!

LEARN MORE