Введение в связанные списки

Знакомимся со структурой связных списков вместе с Арианой на примере её песни «‎Thank U, Next». Если вы её ещё не слышали, то посмотрите клип, прежде, чем читать дальше.

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

Для начала определим несколько терминов, чтобы в дальнейшем не возникло недопонимания:

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

В статье мы будем использовать следующий список:

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

Thought I’d end up with Sean
But he wasn’t a match
Wrote some songs about Ricky
Now I listen and laugh
Even almost got married
And for Pete, I’m so thankful
Wish I could say, “Thank you” to Malcolm
‘Cause he was an angel

Последний узел — сама Ариана:

Plus, I met someone else
We havin’ better discussions
I know they say I move on too fast
But this one gon’ last
‘Cause her name is Ari
And I’m so good with that (so good with that)

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

Простейший способ создать односвязный список — поочерёдно создать и связать узлы:

			class Node {
    constructor(data, next=null) {
        this.data = data
        this.next = next
    }
}

let ari = new Node('Ari')
let malcolm = new Node('Malcolm', ari)
let pete = new Node('Pete', malcolm)
let ricky = new Node('Ricky', pete)
let sean = new Node('Sean', ricky)
		

Пример аналогичного кода на Python.

Если мы выведем на экран содержимое узла Sean, мы увидим, что он содержит имя в качестве данных, а также ссылку на следующий узел — Ricky. С помощью атрибута next мы можем перебрать все узлы по порядку.

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

Связные списки обладают определёнными преимуществами по сравнению с массивами (их основной альтернативой в мире линейных структур данных). Массивы обычно хранятся в едином блоке памяти, что позволяет использовать для индексации быструю формулу start_of_array_in_memory + space_allocated_for_each_array_item * index_of_item_we_want. Это очень эффективно, когда вам нужно получить объект с определённым индексом. Однако при удалении или добавлении элементов эффективность алгоритма падает, ведь придётся перемещать все данные в другой блок памяти. Нет никакой гарантии, что для нового объекта найдётся место в памяти перед началом или в конце массива. Для вставки объекта в середину массива или удаления его оттуда работает та же логика — придётся перемещать большие объёмы данных, чтобы получить свободное место или заполнить пробел.

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

Поиск по связному списку, добавление объекта в середину и удаление такой записи гораздо менее эффективны. Нам пришлось бы пройти от головного узла весь путь к тому, который нам нужен.

Ещё один недостаток связных списков заключается в том, что они требуют чуть больше памяти, так как помимо данных хранят ещё и указатели.

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

			class LinkedList {
  constructor() {
    // головной атрибут содержит указатель на первый узел нашего связного списка
    this.head = null
    this.length = 0
  }

  insert(data) {
    // Вставка в начало связного списка
    // головной элемент становится вторым
    this.head = new Node(data, this.head) 
    this.length++
  }

  remove_value(value) {
    // удаляет любое значение данных из связного списка

    // нам нужно сохранить указатель из удаляемого узла,
    // чтобы, удалив значение, мы могли просто изменить указатель!
    let prevNode = null
    let currentNode = this.head

    while (currentNode) {
      if (currentNode.data === value) {
        if (prevNode) {
          // Устанавливаем значение next предыдущего узла
равным значению next того узла,
          // который мы удаляем, таким образом исключая
его из последовательности
          prevNode.next = currentNode.next
        } else {
          this.head = currentNode.next
        }
        currentNode = null
        this.length--
        return true
      }
      // переходим к следующим узлам
      prevNode = currentNode
      currentNode = currentNode.next
    }
  }
}

let thankUNext = new LinkedList()
thankUNext.insert('Ari')
thankUNext.insert('Malcolm')
thankUNext.insert('Pete')
thankUNext.insert('Ricky')
thankUNext.insert('Sean')

thankUNext.remove_value('Ricky')
		

Вот как будет выглядеть удаление Ricky из нашего связного списка, если Ариана перестанет быть ему так чертовски благодарна:

Все объекты красного цвета удаляются.

Два других полезных метода — search и iterate:

			iterate() {
  let node = this.head
  while (node) {
    console.log(node.data)
    node = node.next
  }
}

search(data) {
  let idx = 0
  let node = this.head
  while (node) {
    if (node.data === data) return idx
    node = node.next
    idx += 1
  }
  return -1
}
		

Итак, мы знаем, что хранение перечня бывших Арианы в связном списке — хорошее применение этой структуры данных. Ведь мы всегда перечисляем их в одном порядке, напевая «‎thank u, next»! Ещё они хорошо подходят, например, для формирования очереди задач. Так, принтеры печатают по одной странице, но мы хотим добавлять дополнительные задачи и не отправлять документы на печать по одной странице. Когда мы создаём список задач, мы всегда будем добавлять новые объекты в конец очереди и потом печатать первый объект в списке. Похожим образом работает кнопка браузера «‎Назад» или функция «‎Undo» редактора. Для реализации этих возможностей ПО обычно используют структуры данных стек или очередь, основанные на связанных списках.