Category: Algorithms and data structures

Linked list

Linked list is a data structure used to represent a sequence of data of a given type. It’s similar to an array but there are a few key differences between those 2 data structures. Both of them have their advantages and disadvantages.

Data structure Advantages Disadvantages
linked list – adding and removing items at any index has O(1) time complexity if we have a reference to an item at that index – adding and removing items at any index has O(n) complexity if we don’t have a reference to an item at that index

– accessing nth item has O(n) time complexity
array – accessing nth item has O(1) time complexity – adding and removing items at any index has O(n) complexity

Linked list items are called as nodes. A node may be defined as the following:

class Node<T> {
  let value: T
  var next: Node? 
  
  init(value: T) {
    self.value = value
  }  
}

and then the list itself:

class LinkedList<T> {

    private var head: Node<T>?

    var isEmpty: Bool {
        head == nil
    }

    var first: Node<T>? {
        head
    }

    func append(value: T) {
        let newNode = Node(value: value)
        if let lastNode = last() {
            lastNode.next = newNode
        } else {
            head = newNode
        }
    }

    private func last() -> Node<T>? {
        var currentNode = head
        while currentNode?.next != nil {
            currentNode = currentNode?.next
        }
        return currentNode
    }

    func remove(value: T) where T: Equatable {
        var currentNode = head
        var previousNode: Node<T>?

        while currentNode != nil {
            if currentNode?.value == value {
                if previousNode == nil {
                    head = currentNode?.next
                } else {
                    previousNode?.next = currentNode?.next
                }
                return
            }
            previousNode = currentNode
            currentNode = currentNode?.next
        }
    }

    func printValues() {
        var currentNode = head
        while currentNode != nil {
            print(currentNode!.value, terminator: " -> ")
            currentNode = currentNode?.next
        }
        print("nil")
    }
    
}

And now, once we defined Node and LinkedList, let’s try to use them:

let list = LinkedList<Int>()
list.append(value: 1)
list.append(value: 2)
list.append(value: 3)
list.append(value: 4)
list.append(value: 5)
list.printValues()
list.remove(value: 2)
list.remove(value: 4)
list.printValues()
print(list.first?.value as Any)
list.remove(value: 1)
list.remove(value: 3)
list.remove(value: 5)
print(list.isEmpty)

Here’s the output:

You can find all the code mentioned in this post here: https://github.com/DamianMarkowski/algorithms-and-data-structures/blob/master/Linked-list/Linked-list.playground/Contents.swift.

Dijkstra’s algorithm

What do the following apps and systems have in common

?

There is at least one such thing – there is a really high chance that all of them use Dijkstra’s algorithm to figure out the shortest distance between 2 locations on Earth, to track how fast and in what direction diseases spread around the world and how to efficiently distribute the phone calls throughout the network.

Speaking of that in a bit more technical way, an objective of Dijkstra’s algorithm is to find the shortest path between any 2 vertices in a graph.

Here’s a really good YouTube video explaining that algorithm in detail:

And here’s an implementation of that algorithm in Swift:

struct Edge {
    let destination: Int
    let weight: Int
}

struct Graph {
    let numberOfVertices: Int
    var adjacencyList: [[Edge]] = []

    init(numberOfVertices: Int) {
        self.numberOfVertices = numberOfVertices
        self.adjacencyList = Array(repeating: [], count: numberOfVertices)
    }

    mutating func addEdge(source: Int, destination: Int, weight: Int) {
        adjacencyList[source].append(Edge(destination: destination, weight: weight))
    }
}

func dijkstra(graph: Graph, source: Int) -> [Int] {
    var distances = Array(repeating: Int.max, count: graph.numberOfVertices)
    var priorityQueue = [(vertex: Int, distance: Int)]()
    distances[source] = 0
    priorityQueue.append((source, 0))

    while !priorityQueue.isEmpty {
        priorityQueue.sort { $0.distance < $1.distance }
        let current = priorityQueue.removeFirst()

        for edge in graph.adjacencyList[current.vertex] {
            let newDistance = current.distance + edge.weight
            if newDistance < distances[edge.destination] {
                distances[edge.destination] = newDistance
                priorityQueue.append((edge.destination, newDistance))
            }
        }
    }
    
    return distances
}

var graph = Graph(numberOfVertices: 5)

graph.addEdge(source: 0, destination: 1, weight: 6)
graph.addEdge(source: 0, destination: 3, weight: 1)
graph.addEdge(source: 1, destination: 0, weight: 6)
graph.addEdge(source: 1, destination: 3, weight: 2)
graph.addEdge(source: 1, destination: 2, weight: 5)
graph.addEdge(source: 1, destination: 4, weight: 2)
graph.addEdge(source: 2, destination: 1, weight: 5)
graph.addEdge(source: 2, destination: 4, weight: 5)
graph.addEdge(source: 3, destination: 0, weight: 1)
graph.addEdge(source: 3, destination: 1, weight: 2)
graph.addEdge(source: 3, destination: 4, weight: 1)
graph.addEdge(source: 4, destination: 1, weight: 2)
graph.addEdge(source: 4, destination: 2, weight: 5)
graph.addEdge(source: 4, destination: 3, weight: 1)

let distances = dijkstra(graph: graph, source: 0)

for (vertex, distance) in distances.enumerated() {
    print("Shortest distance from 0 to \(vertex) is \(distance)")
}

You can find that code in my GitHub repo here https://github.com/DamianMarkowski/algorithms-and-data-structures/blob/master/Dijkstras-algorithm/Dijkstras-algorithm.playground/Contents.swift as well.