Связанные списки в Go

Добро пожаловать в мою новую серию: Введение в структуры данных в Go! Мы начнем эту серию со статьи о связанных списках. Если вы изучаете информатику, то наверняка сталкивались с ними на занятиях. Связанные списки не только являются частью учебной программы по информатике, но и очень популярной темой на собеседованиях по кодированию, поэтому желательно хорошо разбираться в этой теме. Давайте начнем!

Что такое связный список?

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

Мы входим в список, следуя указателю на первый узел, также известный как голова. Не запутайтесь — на приведенной выше диаграмме всего три узла. Первый элемент HEAD — это просто указатель на первый узел. Последний узел указывает на NULL, что означает конец списка.

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

Связанный список против массивов

Вы можете задаться вопросом: «Зачем нам вообще изучать эту структуру данных? Разве у нас нет массивов? Не изобретаем ли мы колесо заново?». В пользу массивов есть свои аргументы, но массивы и связанные списки структурно отличаются.

Массивы инициализируются до компиляции программы. Под них нужно выделить определенный блок памяти.

Массивы отлично подходят, когда нужно найти элементы. Каждый элемент в массиве имеет индекс, и мы можем быстро найти n-й элемент, обратившись к нему с помощью myArr[n].

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

Go slices реализованы именно таким образом. Проблема этого подхода заключается в том, что копирование больших объемов данных неэффективно, и у нас остается много пустого пространства.

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

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

Реализация Go

Давайте посмотрим, как можно создать связный список в Go.

type Node struct {
    data int
    next *Node
}

Вот как определяется узел. Каждый узел содержит данные и указатель на следующий узел. В этом руководстве мы будем хранить данные int, но вы можете легко поменять их на другие типы. Мы даже можем использовать interface{} для хранения данных любого типа.

type LinkedList struct {
    head *Node
    length int
}

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

package main

import (
    "fmt"
)

func main() {
    list := LinkedList{nil, 0}
}

Мы можем инициализировать наш связанный список таким образом. Начальная длина равна нулю, потому что в нашем списке еще нет узлов. Головка указывает на nil, потому что нет узлов, на которые можно было бы указать.

Теперь мы можем определить методы struct для вставки и удаления узлов.

Вставка

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

func (l *LinkedList) insertAtHead(data int) {
    temp1 := &Node{data, nil}

    if l.head == nil {
        l.head = temp1
    } else {
        temp2 := l.head
        l.head = temp1
        temp1.next = temp2
    }
    l.length += 1
}

Этот метод struct определяется с помощью указателя на наш объект LinkedList, поскольку нам нужно внести в него изменения.

Сначала мы создаем узел и сохраняем указатель на него как temp1. Этот узел хранит заданные нами данные и изначально указывает на nil.

Есть два случая, на которые мы должны обратить внимание. Первый случай — когда список пуст. В этом случае мы просто устанавливаем head, чтобы он указывал на только что созданный нами узел.

Второй случай — когда список не пуст. Это означает, что head уже указывает на какой-то узел. Нам нужно настроить его так, чтобы голова указывала на наш новый узел, а новый узел указывал на узел, на который раньше указывала голова.

• Сначала мы сохраним копию head как temp2.

• Затем мы устанавливаем head для указания на temp1.

• Наконец, мы устанавливаем temp1 на temp2.

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

В итоге мы увеличиваем длину на единицу.

Как насчет вставки узлов в хвосте (конце)?

func (l *LinkedList) insertAtTail(data int) {
    temp1 := &Node{data, nil}

    if l.head == nil {
        l.head = temp1
    } else {
        temp2 := l.head
        for temp2.next != nil {
            temp2 = temp2.next
        }
        temp2.next = temp1
    }
    l.length += 1
}

Это тоже довольно просто. Мы создаем новый узел и сохраняем указатель на него как temp1. Здесь мы также должны обработать случай, когда список пуст. Действия те же, что и выше.

Теперь самое интересное: чтобы вставить элемент в конец списка, нам нужно пройти весь список до последнего элемента. Без этого шага нет способа получить доступ к последнему элементу.

• Сначала мы создаем копию head как temp2.

• Мы выполняем итерации по списку, устанавливая temp2 как temp2.next. Это продолжается до тех пор, пока temp2.next не станет nil, что означает, что temp2 указывает на последний узел.

• Проще говоря, пусть последний узел указывает на тот же узел, на который указывает temp1.

Вот диаграмма, которая объясняет, как все это работает. Мы будем использовать много диаграмм, потому что они могут значительно помочь нашему пониманию.

Наконец, давайте посмотрим, как можно вставить данные в произвольное место.

func (l *LinkedList) insert(n, data int) {
    if n == 0 {
        l.insertAtHead(data)
    } else if n == l.length-1 {
        l.insertAtTail(data)
    } else {
        temp1 := &Node{data, nil}
        temp2 := l.head

        for i := 0; i < n-1; i++ {
            temp2 = temp2.next
        }
        temp1.next = temp2.next
        temp2.next = temp1
        l.length += 1
    }
}

Логика здесь довольно похожа на две вышеупомянутые функции.

• Когда мы хотим вставить данные в начало или конец списка, мы можем вызвать insertAtHead() или insertAtTail().

• Чтобы вставить данные в n-ую позицию, нам нужно пройти по списку и достичь *n-1*-ой позиции.

• Когда мы достигнем n-1-й позиции, мы установим temp1.next, указатель на наш новый узел, чтобы он указывал на n+1-ю позицию. Затем мы устанавливаем temp2, чтобы он указывал на наш новый узел.

Теперь вы знаете, как это делается. 🙂

Удаление элементов

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

func (l *LinkedList) deleteAtHead() {
    temp := l.head
    l.head = temp.next

    l.length -= 1
}

Так удаляется первый элемент в списке. Нам просто нужно изменить head так, чтобы он указывал на второй узел. Вы можете подумать, что первый узел останется в памяти, если мы явно не очистим его, но это не так. Встроенный в Go сборщик мусора очистит его за нас.

func (l *LinkedList) deleteAtTail() {
    temp1 := l.head
    var temp2 *Node
    for temp1.next != nil {
        temp2 = temp1
        temp1 = temp1.next
    }
    temp2.next = nil

    l.length -= 1
}

Так удаляется последний элемент в списке. Логика знакома:

• Мы выполняем итерацию по списку, пока не достигнем последнего узла. Однако на этот раз мы отслеживаем узел, расположенный непосредственно перед temp1.

• Мы установим temp2 на nil вместо temp1. Последний узел будет очищен сборщиком мусора.

func (l *LinkedList) delete(n int) {
    if n == 0 {
        l.deleteAtHead()
    } else if n == l.length-1 {
        l.deleteAtTail()
    } else {
        temp1 := l.head
        for i := 0; i < n-1; i++ {
            temp1 = temp1.next
        }
        temp2 := temp1.next
        temp1.next = temp2.next
        l.length -= 1
    }
}

Наконец, давайте рассмотрим, как удалить элемент в произвольной позиции.

• При удалении первого или последнего элемента мы можем использовать deleteAtHead() и deleteAtTail().

• Логика очень похожа на deleteAtTail(). Мы проходим по списку, пока не достигнем n-1-го узла. Мы устанавливаем temp2 для указания на n-й узел.

• Мы устанавливаем temp1.next в temp2.next, что эффективно удаляет связь между n-1-м и n-м элементами.

Поздравляем! Теперь мы знаем, как создать связный список, вставить узел и удалить узел. Давайте сделаем еще один шаг вперед.

Реверсирование связанного списка

Полезно иметь возможность развернуть наш список. Давайте посмотрим, как это можно сделать.

func (l *LinkedList) Reverse() {
    var curr, prev, next *Node
    curr = l.head
    prev = nil

    for curr != nil {
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    }
    l.head = prev
}

Быстрее посмотреть на диаграмму, чем объяснять шаги простыми словами.

Заключение

Связанный список — это полезная структура данных, которую легко реализовать. Для новичков связанные списки могут оказаться сложной задачей, поскольку в них впервые широко используются указатели. Я надеюсь, что это руководство помогло вам понять, как работает связанный список. Желаю вам удачи в учебе!

Вы также можете прочитать этот пост на Medium и на моем личном сайте.