Tag: data structure

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.