Связный список

Содержание

Введение
Общие сведения
Добавление элементов списка
Удаление элементов списка

Введение

В данной статье рассмотрим структуру данных связный список(Linked List), реализуем его на языке Go(Golang) и оценим сложность операций используя O-большое.

Общие сведения

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

Изображение иллюстрирует общую структуру связного списка

head и tail на изображении выше указываются на первый и последний узел списка, prev и next указатели на предыдущий и следующий узлы. Ниже представлен код объявления связного списка:

12345678910111213141516171819

// Узел списка.
// value - полезные данные, добавляемые в список
// next  - указатель на следующий узел списка
// prev  - указатель на предыдущий узел списка
type LinkedListNode[T any] struct {
  value T
  next  *LinkedListNode[T]
  prev  *LinkedListNode[T]
}

// Связный список.
// size - длина списка
// head - первый узел списка
// tail - последний узел списка
type LinkedList[T any] struct {
  size uint
  head *LinkedListNode[T]
  tail *LinkedListNode[T]
}

LinkedListNode - узел списка, который хранит полезные данные в поле value, указатель на предыдущий узел prev и на следующий next.

LinkedList - связный список в котором поле head указывает на первый элемент списка, а tail на последний, по-умолчанию оба ссылаются на NULL. Поле size это длина списка, при вставке происходит инкремент его значения, а при удалении значение уменьшается на единицу.

Добавление элементов списка

Для добавления элемента в начало списка потребуется выполнить следующий шаги:

Создать новый узел значение которого будет равно указанному элементу.
Указатель next нового узла должен ссылаться на текущей первый узел.
Если список был пуст, то tail также должен ссылаться на новый узел, иначе указатель prev текущего первого узла должен ссылаться на новый узел.
Указатель head должен ссылаться на новый узел.

Изображение иллюстрирует добавление элемента в начало списка

Добавление элемента в начало списка реализуется следующий образом:

123456789101112

// Добавление элемента в начало списка.
// element - новый элемент для добавления
func (list *LinkedList[T]) InsertFirst(element T) {
  node := &LinkedListNode[T]{value: element, next: list.head}
  if list.head == nil {
    list.tail = node
  } else {
    list.head.prev = node
  }
  list.head = node
  list.size++
}

Добавление элемента в конец списка осуществляется схожим образом, но все манипуляции проходят с использованием указателя tail, чтобы добавить элемент в конец списка требуется выполнить следующие шаги:

Создать новый узел значение которого будет равно указанному элементу.
Указатель prev нового узла должен ссылаться на текущий последний узел.
Если список был пуст, то head также должен ссылаться на новый узел, иначе указатель next текущего последнего узла должен ссылаться на новый узел.
Указатель tail должен ссылаться на новый узел.

Изображение иллюстрирует добавление элемента в конец списка

Код реализующий добавление элемента в конец списка:

123456789101112

// Добавление элемента в конец списка.
// element - новый элемент для добавления
func (list *LinkedList[T]) InsertLast(element T) {
  node := &LinkedListNode[T]{value: element, prev: list.tail}
  if list.tail == nil {
    list.head = node
  } else {
    list.tail.next = node
  }
  list.tail = node
  list.size++
}

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

Чтобы удалить первый элемент списка потребуется отвязаться все ссылающиеся на этот узел указатели. Для этого необходимо выполнить следующие шаги:

Если список содержит только один узел достаточно присвоить указателям head и tail значение NULL. В ином случае указатель prev следующего после head узла должен ссылаться на NULL.
Указатель head должен ссылаться на следующий узел в списке.

Изображение иллюстрирует удаление первого элемента

Удаление первого элемента списка реализуется следующим образом:

1234567891011121314

// Удаление первого элемента списка.
func (list *LinkedList[T]) RemoveFirst() {
  if list.head != nil {
    next := list.head.next
    if next != nil {
      next.prev = nil
    } else {
      list.tail = nil
    }

    list.head = next
    list.size--
  }
}

Последний элемент списка удаляется аналогичным образом только с использованием указателя tail:

Если список содержит только один узел достаточно присвоить указателям tail и head значение NULL. В ином случае указатель next узла предшествующего tail должен ссылаться на NULL.
Указатель tail должен ссылаться на предыдущий узел в списке.

Изображение иллюстрирует удаление последнего элемента

Ниже приведена реализация удаления последнего элемента списка:

12345678910111213

// Удаление последнего элемента списка.
func (list *LinkedList[T]) RemoveLast() {
  if list.tail != nil {
    prev := list.tail.prev
    if prev != nil {
      prev.next = nil
    } else {
      list.head = nil
    }
    list.tail = prev
    list.size--
  }
}

Все описанные выше операции для работы со связным списком выполняются за константное время O(1). Указанные операции являются наиболее распространенными для данной структуры данных, и в целом определяют основные сценарии использования.

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

Весь исходный код примеров к данной статье вы можете найти на GitHub.