2. Коллекции на основе списков

2. 1. Массив

Непрерывная область памяти, состоящая из элементов одинакового размера, индексированных смежными целыми числами.

Добавление значений
Вы можете добавлять элементы в конец массива с помощью метода append.

// 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]

Чтобы вставить элемент в массив по указанному индексу, вызовите метод массива insert(at:).

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]

Вы также можете добавить другой массив, используя оператор +=.

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]

Удаление значений
Чтобы удалить элемент из определенного индекса, вызовите метод remove(at:).

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

Многомерный массив

// 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. Связанный список

Определение связанного списка — это структура данных, которая хранит данные таким образом, что каждый узел имеет данные и указатели и связан одной строкой.
Типы связанного списка следующие
— Односвязный Список
— Двойной связанный список
— Циклический связанный список

Особенности связанного списка Общие характеристики базовой структуры данных списка следующие.
- Структуры данных списка хранят данные рядом друг с другом. Это не предотвращает хранение повторяющихся данных.
- Основные принципы связанных списков Динамически выделяйте структурные переменные по одной и связывайте их по мере необходимости.

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. Стек

Данные, которые вставляются позже, сначала вычитаются и обрабатываются.
Нажмите и вытолкните в одном направлении: за массивом
LIFO: последний пришел первым ушел
Применение: Функция, рекурсивный вызов

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. Очередь/удаление из очереди

Во-первых, вставленные данные сначала вычитаются и обрабатываются.
Вставляйте и удаляйте разные направления.
Постановка в очередь: за массивом
Удаление из очереди: перед массивом
FIFO: первый пришел первый ушел

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. Приоритетная очередь

Вставить (x): Вставить новый элемент x (постановка в очередь)

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(): Удаляет и возвращает элемент с наивысшим значением приоритета (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
}

2. Коллекции на основе списков