Сегодня мы поговорим, что такое связный список, что делает его таким особенным, как он работает, чем он отличается от обычного массива (о котором я подробно писал в прошлой статье), и попутно мы увидим, как связные списки хороши для решения определенного класса задач.

Прежде чем мы рассмотрим, что такое связный список, давайте посмотрим, какую проблему он пытается решить. Как бы ни были хороши массивы, есть несколько вещей, которые они не могут сделать.

Во-первых, они медленные, когда дело доходит до вставки спереди, каждый раз, когда нам нужно сделать эту вставку, нам нужно скопировать все наверх, а это занимает линейное время, O(n).Во-вторых, массивы занимают место. Иногда очень много. Каждый раз, когда мы создаем массив, нам нужно указать его размер, и, если он очень большой, мы не используем все это пространство, это может быть расточительно.

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

Свя́зный спи́сок — базовая динамическая структура данных в информатике, состоящая из узлов, содержащих данные и ссылки («связки») на следующий и/или предыдущий узел списка. Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.

Эти узлы можно представить себе как вагоны в поезде. Первый узел в списке, называемый "голова"(head), — это место, где мы добавляем элементы в начало нашего списка. Последний узел в списке, "хвост"(tail), он всегда указывает на nil. А все остальное в поезде — это просто связующий вагон с указателем, указывающим на следующий вагон в поезде. В коде это выглядит следующим образом:

class Node {
    var data: Int
    var next: Node?
    
    init(_ data: Int, _ next: Node? = nil) {
        self.data = data
        self.next = next
    }
}

Теперь создаем класс LinkedList

class LinkList {
    private var head: Node?
    
    func addFront(_ data: Int) {
        let newNode = Node(data)
        newNode.next = head
        head = newNode
    }
    
    func getFirst() -> Int? {
        if head == nil {
            return nil
        }
        return head!.data
    }
        
    func addBack(_ data: Int) {
        let newNode = Node(data)
        
        if head == nil {
            head = newNode
            return
        }

        var node = head!
        while(node.next != nil) {
            node = node.next!
        }
        node.next = newNode
    }

    func getLast() -> Int? {
        if head == nil {
            return nil
        }

        var node = head!
        while(node.next != nil) {
            node = node.next!
        }
        return node.data
    }

    func insert(position: Int, data: Int) {
        if position == 0 {
            addFront(data)
            return
        }
            
        let newNode = Node(data)
        var currentNode = head

        for _ in 0..<position - 1{
            currentNode = currentNode?.next!
        }
        newNode.next = currentNode?.next
        currentNode?.next = newNode
    }
    
    func deleteFirst() {
        head = head?.next
    }
    
    func delete(at position: Int) {
        if position == 0 {
            self.deleteFirst()
            return
        }
        
        var nextNode = head
        var previousNode: Node?
        for _ in 0..<position {
            previousNode = nextNode
            nextNode = nextNode?.next
        }
        previousNode?.next = nextNode?.next
    }

    func deleteLast() {
        if head?.next == nil {
            head = nil
            return
        }

        var nextNode = head
        var previousNode: Node?
        while(nextNode?.next != nil) {
            previousNode = nextNode
            nextNode = nextNode?.next
        }
        previousNode?.next = nil
    }
    
    func delete(data: Int) {
        if head == nil { return }
        if head!.data == data {
            head = head?.next
        }
        
        let current = head
        while current?.next != nil {
            if current?.next?.data == data {
                current?.next = current?.next?.next
                return
            }
        }
    }

    var isEmpty: Bool {
        return head == nil
    }
    
    func clear() {
        head = nil
    }

    func printLinkedList() {
        if head == nil {
            print("Empty")
            return
        }
        
        var result = [Int]()
        var node = head
        result.append(node!.data)
        
        while node?.next != nil {
            result.append(node!.next!.data)
            node = node?.next
        }
        
        print(result)
    }
}


let linkedList = LinkList()

Пройдем по каждому методу и посмотри как он работает.

addFront

Главная особенность каждого связного списка - это добавление элемента в начало списка. Мы создаем новый узел, указываем его на head, а затем берем указатель head и указываем его на новый узел. И когда мы это делаем, мы получаем новый узел, вставленный в начало нашего связанного списка. В коде это будет выглядеть следующим образом.

    func addFront(_ data: Int) {
        let newNode = Node(data)
        newNode.next = head
        head = newNode
    }

Эта способность добавлять спереди - постоянное время. O(1) И это то, чего не может сделать массив. Вы не можете добавить новый элемент в массив за постоянное время. Для этого требуется O(n). Метод отлично подходит когда вам нужно быстро добавить что-то на передний план. Следующее, что вы увидите во многих связанных списках - это метод Get First.

    func getFirst() -> Int? {
        if head == nil {
            return nil
        }
        return head!.data
    }

Так мы получим самый первый элемент нашего связного списка, потому что это фронт, который также является O(1). Очень, очень быстро. Далее давайте посмотрим, как мы можем добавить что-то в конец нашего списка с помощью функции Add Back.

addBack

Добавление в конец работает следующим образом. Допустим, мы хотим добавить узел в самый конец, сначала мы создадим наш новый узел. Мы можем сделать проверку в начале. Если бы head был равен nil, мы могли бы просто указать head на новый узел, и все было бы готово. Это был бы одноэлементный связный список. Но если в связанном списке есть другие элементы, то нам нужно пройтись по списку до конца. Мы узнаем, что в конце, когда следующая из самых последних записей будет равна nil. Так мы поймем, что находимся в хвосте. Указываем его следующую точку на новый узел. Теперь у нас есть новый узел, добавленный в хвост. В коде это выглядит следующим образом:

func addBack(_ data: Int) {
        let newNode = Node(data)
        
        if head == nil {
            head = newNode
            return
        }

        var node = head!
        while(node.next != nil) {
            node = node.next!
        }
        node.next = newNode
    }

Теперь обратите внимание, что всякий раз, когда вы видите этот цикл while в связанном списке, скорость операции будет O(n). Вы уже знаете что в массиве эта операция происходит быстрее.

Метод getLastможно разобрать по аналогии:

  func getLast() -> Int? {
        if head == nil {
            return nil
        }

        var node = head!
        while(node.next != nil) {
            node = node.next!
        }
        return node.data
    }

Insert

Как мы будем вставлять данные в определенную позицию нашего связного списка? Вставка - это как ходьба, только мы должны остановиться в том месте, куда хотим вставить узел, и манипулировать указателями, чтобы они указывали на наш новый узел. Нам не нужно делать никаких сдвигов или копирования. Нам просто идти по списку и манипулировать указателями. Как только мы это сделаем, наш новый узел окажется в нужном месте, прямо посередине. В коде это будет выглядеть следующим образом:

    func insert(position: Int, data: Int) {
        if position == 0 {
            addFront(data)
            return
        }
            
        let newNode = Node(data)
        var currentNode = head

        for _ in 0..<position - 1{
            currentNode = currentNode?.next!
        }
        newNode.next = currentNode?.next
        currentNode?.next = newNode
    }

deleteFirst

Когда речь идет об удалении элементов из связанного списка, все очень похоже. Вместо того чтобы вставлять элементы, мы собираемся их пропустить. Давайте рассмотрим метод deleteFirst. Чтобы удалить первый элемент или пропустить самую первую node в нашем связанном списке, все, что нам нужно сделать, это взять head и переназначить head на head.next. Это, по сути, приведет к тому, что head будет указывать на первый элемент, в данном случае на самый первый элемент 1, и пропустит его, заставив его указатель перейти к head.next. В данном случае на элемент два. Очень быстро, без хождения по списку, время O(1). В коде это буквально одна строка.

    func deleteFirst() {
        head = head?.next
    }

deleteLast

По сути, здесь мы можем использовать предыдущий и следующий узлы, чтобы понять, где мы находимся в нашем цикле. А затем, если мы каким-то образом отслеживаем предыдущий узел в конце, мы можем назначить этот предыдущий узел не для указания на следующий узел. Мы можем пропустить его и указать на nil. Поэтому, по сути, нам нужно выполнить цикл до конца, захватить этот последний узел, а затем присвоить его nill.

    func deleteLast() {
        if head?.next == nil {
            head = nil
            return
        }

        var nextNode = head
        var previousNode: Node?
        while(nextNode?.next != nil) {
            previousNode = nextNode
            nextNode = nextNode?.next
        }
        previousNode?.next = nil
    }

Delete at position

Мы просто переходим к тому месту, где хотим выполнить удаление, а затем пропускаем его, просто переназначая следующий указатель предыдущего узла. . Обратите внимание, что это линейная задача, имеет время выполнения O(n), и в коде она будет выглядеть следующим образом.

func delete(data: Int) {
        if head == nil { return }
        if head!.data == data {
            head = head?.next
        }
        
        let current = head
        while current?.next != nil {
            if current?.next?.data == data {
                current?.next = current?.next?.next
                return
            }
        }
    }

Итак, прежде чем мы завершим нашу работу и рассмотрим, как связанные списки используются в реальном мире, рассмотрим эти два метода isEmpty и clear.

    var isEmpty: Bool {
        return head == nil
    }

Если head равен nil, то мы знаем, что у нас пустой связный список. Супер простое вычисление O(1).

    func clear() {
        head = nil
    }

Как очистить связный список? Простой способ очистить связный список - это просто взять его head и установить ее равной nil. Здесь у нас может быть сколько угодно элементов связного списка, но если просто присвоить head = nil, то все они исчезнут.

Применение

Связанные списки используются повсеместно в реальном мире. Например связанные списки используются в фреймворке UIKit компании Apple. UIKit с использованием Responder Chain. Для тех из вас, кто не знаком с responder chain, это то, что обеспечивает работу практически всех элементов управления iOS на вашем телефоне. Когда вы создаете приложение, с окном и представлениями, за кулисами есть механизм, который запускает события через эту цепочку ответчиков, и это, по сути, связанный список. Если вам когда-либо приходилось работать с клавиатурой в iOS и вам приходилось отказываться от first responder, то это, по сути, означает, что это вью должно, сделать себя первым, кто будет реагировать в случае прикосновения к экрану. И этот механизм цепочки ответчиков сам по себе является связным списком. Подробнее про Responder Chain.

Отличие от массива

Хорошо, прежде чем мы закончим, давайте просто быстро сравним и поговорим о различиях между связанными списками и массивами. В чем разница?

Во-первых, связанные списки очень быстры, когда мы выполняем операции на фронте. Так что вставка спереди, удаление спереди, получение элемента спереди - все это O(1), очень быстрое преимущество связанных списков. Другое преимущество связных списков - нам не нужно заранее определять их размер. Они могут динамически расти по мере необходимости. Просто путем добавления к задней части. Они могут вырасти до любого размера и всегда будут именно того размера, который нужен. Никакой напрасной траты памяти.

 Недостатки связного списка - отсутствие случайного доступа.Вот где массив действительно выигрывает. Возможность использовать индекс и переходить к любому элементу массива за время O(1) очень быстра. Именно поэтому массивы так популярны. Также get и set в связанном списке выполняются за O(n). Если у вас есть цикл или цикл while, в котором нам нужно пройтись по связному списку, знайте, что эта операция будет O(n).

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

Заключение

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

Все, что находится впереди, O(1), добавить впереди, получить первым, удалить первым, если кто-то спросит вас, в чем преимущество связного списка?

Он действительно хорош в операциях на фронте, O(1).

Каждый раз, когда вам нужно пройтись по чему-либо в любой структуре данных, это O(n).

В связаном списке addLast/getLast/deleteLast - все эти операции будут O(n).

Всегда правильный размер, и как мы уже говорили, нет случайного доступа.