Двусвязный список
Последнее обновление
Двусвязный список - это связный список, в котором каждый узел хранит два указателя: next (на следующий узел) и prev (на предыдущий). Эта дополнительная обратная ссылка позволяет обходить список в обоих направлениях и удалять узел за O(1), когда у вас уже есть ссылка на него, потому что вы можете сразу добраться до его предшественника, а не идти от головы. Нажмите воспроизведение выше, чтобы увидеть, как узлы связываются и перепривязываются в обе стороны.
Цена - один дополнительный указатель на узел и больше учёта: каждая вставка и удаление должны обновлять и next, и prev у соседей. Это структура, лежащая в основе многих деков и LRU-кэшей, где важно быстрое удаление с обоих концов.
Временная сложность
| Операция | Сложность | Примечания |
|---|---|---|
| Вставка в голову/хвост | O(1) | С указателями на голову и хвост |
| Удаление известного узла | O(1) | Прямой доступ к prev, без обхода |
| Поиск | O(n) | Всё ещё линейный проход |
| Доступ по индексу | O(n) | Нет произвольного доступа |
Односвязный и двусвязный список
| Аспект | Односвязный | Двусвязный |
|---|---|---|
| Указателей на узел | 1 (next) | 2 (next + prev) |
| Обход назад | Нет | Да |
| Удаление известного узла | O(n) (найти prev) | O(1) |
| Накладные расходы памяти | Ниже | Выше |
Разобранный пример
Построение [10, 20, 30] добавлением в конец, затем удаление узла 20:
| Шаг | Структура | Действие |
|---|---|---|
| Начало | null | Пустой список: head и tail оба равны null |
| Добавить 10 | 10 | Первый узел; head и tail указывают на него, prev = next = null |
| Добавить 20 | 10 <-> 20 | Устанавливаем 10.next = 20 и 20.prev = 10; tail = 20 |
| Добавить 30 | 10 <-> 20 <-> 30 | Устанавливаем 20.next = 30 и 30.prev = 20; tail = 30 |
| Удалить 20 | 10 <-> 30 | Используя 20.prev и 20.next: устанавливаем 10.next = 30 и 30.prev = 10 за O(1) |
Когда использовать двусвязный список
| Используйте, когда | Избегайте, когда |
|---|---|
| Нужно обходить или вставлять в обоих направлениях | Вы двигаетесь только вперёд: односвязный список легче |
Удаляете произвольные узлы, ссылку на которые уже держите (O(1)) | В основном индексируете по позиции: используйте массив для доступа O(1) |
| Реализуете дек, LRU-кэш или историю отмены действий | Память ограничена: дополнительный указатель prev удваивает накладные расходы на связи |
| Вставки и удаления часто происходят с обоих концов | Данные малы и редко меняются: копирование массивов дешевле |
Код Doubly Linked List
Чистая, готовая к запуску реализация Doubly Linked List на Python, JavaScript, Java, C++, C. Выберите язык, скопируйте код или откройте его уже загруженным в плейграунде Coddy.
Код Doubly Linked List на Python
Python
1class Node:2 def __init__(self, value):3 self.value = value4 self.prev = None5 self.next = None6
7
8class DoublyLinkedList:9 def __init__(self):10 self.head = None11 self.tail = None12
13 def append(self, value):14 node = Node(value)15 if self.tail is None:16 self.head = self.tail = node17 return18 # Wire both directions: old tail <-> new node19 node.prev = self.tail20 self.tail.next = node21 self.tail = node22
23 def prepend(self, value):24 node = Node(value)25 if self.head is None:26 self.head = self.tail = node27 return28 node.next = self.head29 self.head.prev = node30 self.head = node31
32 def forward(self):33 values, current = [], self.head34 while current:35 values.append(current.value)36 current = current.next37 return values38
39 def backward(self):40 values, current = [], self.tail41 while current:42 values.append(current.value)43 current = current.prev44 return values45
46
47lst = DoublyLinkedList()48for value in [2, 3, 4]:49 lst.append(value)50lst.prepend(1)51
52print("Forward: ", lst.forward())53print("Backward:", lst.backward())Код Doubly Linked List на JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.prev = null;5 this.next = null;6 }7}8
9class DoublyLinkedList {10 constructor() {11 this.head = null;12 this.tail = null;13 }14
15 // Tail pointer makes append O(1)16 append(value) {17 const node = new Node(value);18 if (!this.tail) {19 this.head = node;20 this.tail = node;21 return;22 }23 node.prev = this.tail;24 this.tail.next = node;25 this.tail = node;26 }27
28 forward() {29 const out = [];30 for (let n = this.head; n; n = n.next) out.push(n.value);31 return out;32 }33
34 backward() {35 const out = [];36 for (let n = this.tail; n; n = n.prev) out.push(n.value);37 return out;38 }39}40
41const list = new DoublyLinkedList();42for (const value of [10, 20, 30, 40]) list.append(value);43console.log("Forward: ", list.forward().join(" <-> "));44console.log("Backward:", list.backward().join(" <-> "));Код Doubly Linked List на Java
Java
1public class Main {2 static class Node {3 int value;4 Node prev, next;5 Node(int value) { this.value = value; }6 }7
8 static Node head, tail;9
10 static void append(int value) {11 Node node = new Node(value);12 if (head == null) { head = tail = node; return; }13 node.prev = tail;14 tail.next = node;15 tail = node;16 }17
18 // Unlink in O(1) once found: fix both neighbor pointers19 static void delete(int value) {20 for (Node cur = head; cur != null; cur = cur.next) {21 if (cur.value != value) continue;22 if (cur.prev != null) cur.prev.next = cur.next; else head = cur.next;23 if (cur.next != null) cur.next.prev = cur.prev; else tail = cur.prev;24 return;25 }26 }27
28 public static void main(String[] args) {29 append(1);30 append(2);31 append(3);32 append(4);33
34 StringBuilder forward = new StringBuilder("Forward:");35 for (Node cur = head; cur != null; cur = cur.next) forward.append(" ").append(cur.value);36 System.out.println(forward);37
38 StringBuilder backward = new StringBuilder("Backward:");39 for (Node cur = tail; cur != null; cur = cur.prev) backward.append(" ").append(cur.value);40 System.out.println(backward);41
42 delete(3);43 StringBuilder after = new StringBuilder("After delete 3:");44 for (Node cur = head; cur != null; cur = cur.next) after.append(" ").append(cur.value);45 System.out.println(after);46 }47}Код Doubly Linked List на C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* prev = nullptr;6 Node* next = nullptr;7 explicit Node(int v) : value(v) {}8};9
10struct DoublyLinkedList {11 Node* head = nullptr;12 Node* tail = nullptr;13
14 void append(int value) {15 Node* node = new Node(value);16 if (tail == nullptr) {17 head = tail = node;18 return;19 }20 node->prev = tail; // link both directions21 tail->next = node;22 tail = node;23 }24
25 void prepend(int value) {26 Node* node = new Node(value);27 if (head == nullptr) {28 head = tail = node;29 return;30 }31 node->next = head;32 head->prev = node;33 head = node;34 }35
36 void printForward() const {37 for (Node* cur = head; cur != nullptr; cur = cur->next) {38 std::cout << cur->value << " <-> ";39 }40 std::cout << "null\n";41 }42
43 void printBackward() const {44 for (Node* cur = tail; cur != nullptr; cur = cur->prev) {45 std::cout << cur->value << " <-> ";46 }47 std::cout << "null\n";48 }49};50
51int main() {52 DoublyLinkedList list;53 for (int value : {10, 20, 30}) list.append(value);54 list.prepend(5);55 std::cout << "Forward: ";56 list.printForward();57 std::cout << "Backward: ";58 list.printBackward();59 return 0;60}Код Doubly Linked List на C
C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5 int value;6 struct Node* prev;7 struct Node* next;8} Node;9
10Node* head = NULL;11Node* tail = NULL;12
13Node* newNode(int value) {14 Node* n = calloc(1, sizeof(Node));15 n->value = value;16 return n;17}18
19void append(int value) {20 Node* node = newNode(value);21 if (tail == NULL) {22 head = tail = node;23 return;24 }25 node->prev = tail; // link both directions26 tail->next = node;27 tail = node;28}29
30void prepend(int value) {31 Node* node = newNode(value);32 if (head == NULL) {33 head = tail = node;34 return;35 }36 node->next = head;37 head->prev = node;38 head = node;39}40
41void printForward(void) {42 for (Node* cur = head; cur != NULL; cur = cur->next) {43 printf("%d <-> ", cur->value);44 }45 printf("NULL\n");46}47
48void printBackward(void) {49 for (Node* cur = tail; cur != NULL; cur = cur->prev) {50 printf("%d <-> ", cur->value);51 }52 printf("NULL\n");53}54
55int main(void) {56 int values[] = {10, 20, 30};57 for (int i = 0; i < 3; i++) append(values[i]);58 prepend(5);59 printf("Forward: ");60 printForward();61 printf("Backward: ");62 printBackward();63 return 0;64}Часто задаваемые вопросы о двусвязных списках
В чём разница между односвязным и двусвязным списком?
В односвязном списке у каждого узла один указатель (
next), поэтому двигаться можно только вперёд. Двусвязный список добавляет указатель prev, что позволяет обходить назад и удалять узел, ссылку на который вы держите, за O(1) - ценой дополнительного указателя на узел и обновления двух связей при каждом изменении.Когда двусвязный список оправдывает дополнительную память?
Когда нужен обход назад или удаление за
O(1) произвольных узлов, которые вы уже ссылаетесь - классические случаи это деки (двусторонние очереди) и LRU-кэши, где элементы часто перемещаются и вытесняются с обоих концов.Почему двусвязный список может удалить узел за O(1)?
Чтобы удалить узел, нужно соединить его предшественника с преемником. В односвязном списке пришлось бы идти от головы, чтобы найти предшественника (
O(n)); в двусвязном списке указатель prev узла даёт предшественника напрямую, поэтому переподключение выполняется за O(1).Двусвязный список или массив: что выбрать?
Используйте массив, когда нужен доступ по индексу за
O(1) и дружественная к кэшу итерация, а вставки происходят в основном в конце. Используйте двусвязный список, когда часто вставляете или удаляете в середине или на обоих концах при наличии ссылки на узел, так как это O(1) против сдвига O(n) у массива. Массивы выигрывают в памяти и локальности; список выигрывает в структурных изменениях.Что такое узел-страж (sentinel) в двусвязном списке?
Узел-страж (или фиктивный узел) - это заполнитель, стоящий перед головой и/или после хвоста, чтобы список никогда не был по-настоящему пустым. Он устраняет проверки на
null для head, tail и граничных вставок/удалений, позволяя каждой операции идти по одному и тому же пути переподключения. Многие продакшн-реализации LRU-кэшей используют два стража, чтобы не обрабатывать концы как особые случаи.Какая самая частая ошибка при удалении из двусвязного списка?
Забыть обновить
head или tail при удалении первого или последнего узла, что оставляет висячий указатель на освобождённый узел. Всегда проверяйте, равен ли node.prev значению null (обновите head) или node.next значению null (обновите tail) перед переподключением соседей.Связанные ресурсы
Больше визуализаций
