Основы алгоритмов и структур данных
2026-02-26 16:54 Diff
https://ru.hexlet.io/courses/basic-algorithms/lessons/double-linked-list/theory_unit

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

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

Другая задача, которую трудно решить с помощью односвязного списка — вставка перед заданным узлом. Предположим, у нас есть текст на русском языке, где каждый элемент — либо отдельное слово, либо знак препинания. В тексте могут быть ошибки: например, могут отсутствовать запятые и точки. Мы предполагаем, что если слово начинается с большой буквы, перед ним должна быть точка. Если в тексте есть союзы «но» и «а», перед ними должна стоять запятая.

Расссмотрим такой пример:

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

  • Поместить слова в односвязный список
  • Найти слово «но»
  • Попробовать вставить перед ним запятую

Здесь мы сталкиваемся с тем, что в узле нет ссылки на предыдущий элемент, только на следующий:

Односвязный список устроен так, что для вставки запятой между словами «наука» и «но» нужно модифицировать именно узел со словом «наука». Эти детали делают наш возможный алгоритм сложным и медленным.

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

Двусвязный список

В каждом узле двусвязного списка хранится две ссылки — на следующий и на предыдущий узел. Кроме того, в нем хранятся ссылки и на голову списка (первый элемент), и на его хвост (последний элемент):

Как и в случае с односвязным списком, нам приходится особым образом хранить ссылку на следующий узел для последнего узла. Там мы помещаем значение null — пустую ссылку, которая ни на что не указывает. На рисунке последний узел в списке — это D.

У первого узла не может быть предыдущего узла, поэтому и здесь мы записываем null вместо ссылки. На рисунке первый узел в списке — это A.

За счет изменения структуры, мы получаем две новые возможности:

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

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

Вставка узла в начало списка

Посмотрим, как выглядит вставка узла в начало списка:

Разберем этот фрагмент кода подробнее.

Двусвязный список, как и односвязный, требует определения двух классов:

Первый класс — DoublyLinkedListNode. Он описывает узел двусвязного списка и состоит из таких компонентов:

  • Значения — value
  • Ссылки на предыдущий узел — previous
  • Ссылки на следующий узел — next

Второй класс — DoublyLinkedList. Он представляет список целиком, вместе с его операциями-алгоритмами. Там находятся:

  • Ссылка на первый узел — head
  • Ссылка на последний узел — tail
  • Различные методы, например:
    • insertBegin(value) — вставка в начало
    • insertEnd(value) — вставка в конец
    • removeBegin() — удаление из начала

Новый список пуст, поэтому поля head и tail содержат значение null:

После вставки первого узла head и tail содержат его адрес. При этом поля previous и next у этого узла никуда не указывают, потому что он одновременно является первым и последним в списке — другими словами, у него нет ни предыдущего, ни следующего узла:

Теперь посмотрим на фрагмент кода:

Условие this.head == null выполняется для пустого списка. Нам достаточно создать узел с пустыми ссылками на предыдущий и следующий узлы, а затем присвоить его адрес полям this.head и this.tail.

При вставке каждого следующего узла в начало, head всегда будет указывать на новый узел. Значение tail при этом не изменится, потому что хвост списка остается прежним. Поле next новой головы списка будет указывать на прежнюю голову, а в поле previous старой головы вместо null должен появиться адрес новой головы:

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

Создавая узел, мы сразу записываем в поле next текущее значение this.head— текущую голову. Поле previous текущей головы должно ссылать на новый узел, за это отвечает такая строка:

Наконец, новый узел становится новой головой списка:

Вставка узла в конец списка

Перейдем к вставке узла в конец списка:

Такая вставка симметрична вставке в начало. Разница только в том, что здесь мы должны везде менять местами head и tail, а также previous и next.

Удаление узла

Перейдем к операциям удаления:

Метод удаления возвращает значение из удаленного узла. Если список пуст и удалять нечего, метод возвращает undefined. В остальных случаях мы сохраняем значение в переменную result:

Если this.head == this.tail, значит, в списке находится один последний узел — он является одновременно и головой, и хвостом. Чтобы его удалить, достаточно обнулить head и tail:

А теперь посмотрим обратный пример — избавимся от первого узла в списке. Сначала записываем в head ссылку на второй узел, а потом обнуляем у нее поле previous:

Перебор значений в прямом порядке

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

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

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

Итератор — это объект, который одинаковым образом перебирает элементы коллекции, независимо от структуры данных. Скажем, мы можем написать функцию суммирования элементов любой коллекции и вызвать ее для списка:

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

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

  • От начала к концу
  • От конца к началу

Поэтому двусвязный список должен иметь два итератора — прямой и обратный. Чтобы так сделать, можно возвращать итераторы из методов класса. Например, метод fore() может создавать и возвращать прямой итератор:

Использовать итератор можно так:

В JavaScript используется синтаксис function* и yield, который упрощает работу с итераторами. В нашем примере порядок действий такой:

  • Начинаем с первого узла, адрес которого хранится в поле head
  • Пробегаем по всем узлам списка
  • Передаем значения узлов в вызывающую функцию с помощью конструкции yield

Выводы

  • Односвязный список подходит не для всех задач — он предоставляет только последовательный доступ к последующим элементам
  • Чтобы справиться с этими трудностями, программисты используют такую структуру данных, как двусвязный список.
  • В каждом узле двусвязного списка хранится не только ссылка на следующий узел (как у односвязного), но и на предыдущий.
  • К плюсам двусвязного списка можно отнести возможность «пробегать» по списку как вперед, так и назад, а к минусам — сложный код и больший расход памяти.
  • Итераторы позволяют писать один код для работы с коллекциями разных типов. Мы можем реализовать итераторы для тех структур данных, которые мы разрабатываем.