Photo by Kelly Sikkema on Unsplash

2. List-Based Collections

-

2. 1. Array

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

Adding values
You can add elements to the end of an array using the append method.

// create a 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
To remove an item from a specific index call the remove(at:) method.

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)

2. 2. Linked List

The definition of 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.
The types of Linked List are as follows
- Singly Linked List
- Doubly Linked List
- Circular Linked List

Features of Linked List The common characteristics of the basic list data structure are as follows.
- List data structures store data side by side. It does not prevent storing duplicate data.
- Basic Principles of Linked Lists Dynamically allocate structure variables one at a time and link them as needed.

public class Node {
    var value: String
    
    init(value: String) {
        self.value = value
    }
    
    var next: Node?
    weak var previous: Node?
}
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 + "]"
    }
}

2. 3. Stack

• The data that is inserted later is first subtracted 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
    }
}

2. 4. Queue/Dequeue

• First, the inserted data is first subtracted and processed.
• Insert and delete 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 + "]"
    }
}

2. 5. 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 Extract_Max(_ 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
}