Rivalry2

HTML Diff

0 added 51 removed

Original 2026-01-01

Modified 2026-02-26

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

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

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

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

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

6 <ul><li>Поместить слова в односвязный список</li>

7 <li>Найти слово "но"</li>

8 <li>Попробовать вставить перед ним запятую</li>

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

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

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

12 <h2>Двусвязный список</h2>

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

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

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

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

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

18 <li>Вставка узла перед заданным узлом становится такой же простой операцией, как и вставка после</li>

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

20 <h2>Вставка узла в начало списка</h2>

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

22 - Javascript

23 - Python

24 - PHP

25 - Java

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

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

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

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

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

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

29 <ul><li>Значения - value</li>

25 <ul><li>Значения - value</li>

30 <li>Ссылки на предыдущий узел - previous</li>

26 <li>Ссылки на предыдущий узел - previous</li>

31 <li>Ссылки на следующий узел - next</li>

27 <li>Ссылки на следующий узел - next</li>

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

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

33 <ul><li>Ссылка на первый узел - head</li>

29 <ul><li>Ссылка на первый узел - head</li>

34 <li>Ссылка на последний узел - tail</li>

30 <li>Ссылка на последний узел - tail</li>

35 <li>Различные методы, например:<ul><li>insertBegin(value) - вставка в начало</li>

31 <li>Различные методы, например:<ul><li>insertBegin(value) - вставка в начало</li>

36 <li>insertEnd(value) - вставка в конец</li>

32 <li>insertEnd(value) - вставка в конец</li>

37 <li>removeBegin() - удаление из начала</li>

33 <li>removeBegin() - удаление из начала</li>

38 </ul></li>

34 </ul></li>

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

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

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

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

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

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

42 - Javascript

43 - Python

44 - PHP

45 - Java

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

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

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

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

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

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

49 - Javascript

50 - Python

51 - PHP

52 - Java

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

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

54 - Javascript

55 - Python

56 - PHP

57 - Java

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

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

59 - Javascript

60 - Python

61 - PHP

62 - Java

63 <h2>Вставка узла в конец списка</h2>

43 <h2>Вставка узла в конец списка</h2>

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

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

65 - Javascript

66 - Python

67 - PHP

68 - Java

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

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

70 <h2>Удаление узла</h2>

46 <h2>Удаление узла</h2>

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

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

72 - Javascript

73 - Python

74 - PHP

75 - Java

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

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

77 - Javascript

78 - Python

79 - PHP

80 - Java

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

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

82 - Javascript

83 - Python

84 - PHP

85 - Java

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

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

87 - Javascript

88 - Python

89 - PHP

90 - Java

91 <h2>Перебор значений в прямом порядке</h2>

51 <h2>Перебор значений в прямом порядке</h2>

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

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

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

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

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

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

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

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

96 - Javascript

97 - Python

98 - PHP

99 - Java

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

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

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

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

102 <ul><li>От начала к концу</li>

58 <ul><li>От начала к концу</li>

103 <li>От конца к началу</li>

59 <li>От конца к началу</li>

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

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

105 - Javascript

106 - Python

107 - PHP

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

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

109 - Javascript

110 - Python

111 - PHP

112 - Java

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

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

114 <ul><li>Начинаем с первого узла, адрес которого хранится в поле head</li>

63 <ul><li>Начинаем с первого узла, адрес которого хранится в поле head</li>

115 <li>Пробегаем по всем узлам списка</li>

64 <li>Пробегаем по всем узлам списка</li>

116 <li>Передаем значения узлов в вызывающую функцию с помощью конструкции yield</li>

65 <li>Передаем значения узлов в вызывающую функцию с помощью конструкции yield</li>

117 </ul><h2>Выводы</h2>

66 </ul><h2>Выводы</h2>

118 <ul><li>Односвязный список подходит не для всех задач - он предоставляет только последовательный доступ к последующим элементам</li>

67 <ul><li>Односвязный список подходит не для всех задач - он предоставляет только последовательный доступ к последующим элементам</li>

119 <li>Чтобы справиться с этими трудностями, программисты используют такую структуру данных, как двусвязный список.</li>

68 <li>Чтобы справиться с этими трудностями, программисты используют такую структуру данных, как двусвязный список.</li>

120 <li>В каждом узле двусвязного списка хранится не только ссылка на следующий узел (как у односвязного), но и на предыдущий.</li>

69 <li>В каждом узле двусвязного списка хранится не только ссылка на следующий узел (как у односвязного), но и на предыдущий.</li>

121 <li>К плюсам двусвязного списка можно отнести возможность "пробегать" по списку как вперед, так и назад, а к минусам - сложный код и больший расход памяти.</li>

70 <li>К плюсам двусвязного списка можно отнести возможность "пробегать" по списку как вперед, так и назад, а к минусам - сложный код и больший расход памяти.</li>

122 <li>Итераторы позволяют писать один код для работы с коллекциями разных типов. Мы можем реализовать итераторы для тех структур данных, которые мы разрабатываем.</li>

71 <li>Итераторы позволяют писать один код для работы с коллекциями разных типов. Мы можем реализовать итераторы для тех структур данных, которые мы разрабатываем.</li>

123 </ul>

72 </ul>