List-Based Collections

Array

Contiguous area of memory consisting of equal-size elements indexed by contiguous integers.

Adding values

// create an empty array of integers
var numbers: [Int] = []
for i in 1...5 {
    numbers.append(i)
    print(numbers)
    // [1]
    // [1, 2]
    // [1, 2, 3]
    // [1, 2, 3, 4]
    // [1, 2, 3, 4, 5]
}
print(numbers)
// [1, 2, 3, 4, 5]

To insert an item into the array at a specified index, call the array’s insert(at:) method:

var numbers: [Int] = [1, 2, 3]
numbers.insert(0, at: 0) // numbers will be [0, 1, 2, 3]
numbers.insert(9, at: 1) // numbers will be [0, 9, 1, 2, 3]

You can also append another array using the += operator:

var numbers: [Int] = [1, 2, 3]
numbers += [4, 5, 6] // numbers will be [1, 2, 3, 4, 5, 6]
// or just one value
numbers += [7] // numbers will be [1, 2, 3, 4, 5, 6, 7]

Removing Values

var numbers: [Int] = [1, 2, 3]
numbers.remove(at: 0) // numbers will be [2, 3]

Multi Dimensional Array

// Create a two-dimensional array with nested brackets.
var points: [[Int]] = [[10, 20], [30, 40]]

// Access all individual elements.
print(points[0][0])
print(points[0][1])
print(points[1][0])
print(points[1][1])

// Append an item to one of the arrays
points[1].append(50)
print(points)

Linked List

A Linked List is a data structure that stores data in such a way that each node has data and pointers and is connected in a single line.

Types of Linked List:

• Singly Linked List
• Doubly Linked List
• Circular Linked List

Features:

• List data structures store data side by side and do not prevent storing duplicate data
• Dynamically allocate structure variables one at a time and link them as needed

public class Node {
    var value: String
    var next: Node?
    weak var previous: Node?

    init(value: String) {
        self.value = value
    }
}

public class LinkedList {
    fileprivate var head: Node?
    private var tail: Node?

    public var isEmpty: Bool {
        return head == nil
    }

    public var first: Node? {
        return head
    }

    public var last: Node? {
        return tail
    }

    public func append(value: String) {
        let newNode = Node(value: value)
        if let tailNode = tail {
            newNode.previous = tailNode
            tailNode.next = newNode
        } else {
            head = newNode
        }
        tail = newNode
    }

    public func nodeAt(index: Int) -> Node? {
        if index >= 0 {
            var node = head
            var i = index
            while node != nil {
                if i == 0 { return node }
                i -= 1
                node = node!.next
            }
        }
        return nil
    }

    public func remove(node: Node) -> String {
        let prev = node.previous
        let next = node.next

        if let prev = prev {
            prev.next = next
        } else {
            head = next
        }

        next?.previous = prev

        if next == nil {
            tail = prev
        }

        node.previous = nil
        node.next = nil
        return node.value
    }

    public func removeAll() {
        head = nil
        tail = nil
    }

    public var description: String {
        var text = "["
        var node = head
        while node != nil {
            text += "\(node!.value)"
            node = node!.next
            if node != nil { text += ", " }
        }
        return text + "]"
    }
}

Stack

• Last inserted data is first removed and processed
• Push and Pop in the same direction: behind the array
• LIFO: Last In First Out
• Application: Function, recursive call

struct Stack {
    fileprivate var array: [String] = []

    mutating func push(_ element: String) {
        array.append(element)
    }

    mutating func pop() -> String? {
        return array.popLast()
    }

    func peek() -> String? {
        return array.last
    }
}

Queue/Dequeue

• First inserted data is first removed and processed
• Insert and delete in different directions
• Enqueue: Behind array
• Dequeue: Before array
• FIFO: First In First Out

public struct Queue {
    fileprivate var list = LinkedList<Int>()

    public mutating func enqueue(_ element: Int) {
        list.append(value: element)
    }

    public mutating func dequeue() -> Int? {
        guard !list.isEmpty, let element = list.first else { return nil }
        list.remove(node: element)
        return element.value
    }

    public func peek() -> Int? {
        return list.first?.value
    }

    public func description() -> String {
        var result = "["
        var i = 0
        while (true) {
            let node = list.nodeAt(index: i)!
            result = result + String(node.value)
            if (node.next == nil) { break } else { result += "," }
            i += 1
        }
        return result + "]"
    }
}

Priority Queue

Insert (x): Insert new element x (Enqueue)

func insert(_ x: Int, _ n: Int) {
    data.append(x)
    var size = n + 1
    while (size > 1 && data[size/2] < data[size]) {
        let temp = data[size]
        data[size] = data[size/2]
        data[size/2] = temp
        size = size / 2
    }
}

Extract_Max(): Deletes and returns the element with the highest priority value (Dequeue)

func extractMax(_ n: Int) -> Int {
    var result = data[1]
    let temp = data[n]
    data[n] = data[1]
    data[1] = temp
    data.removeLast()
    maxHeapify(1, n - 1)
    return result
}