12. Двусвязный список
9 апреля 2026 г.
Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty
Определение
Двусвязный список - это структура данных, в которой каждый элемент содержит указатели на предыдущий и следующий элементы списка. Это позволяет эффективно добавлять и удалять элементы из любого места списка, а также обходить список в обоих направлениях.
Преимущества
- Позволяет перемещаться по списку в обоих направлениях
- Упрощает вставку и удаление элементов в любом месте списка
- Подходит для реализации стеков, очередей, деков и других структур данных
Недостатки
- Занимает больше памяти, чем односвязный список, из-за дополнительных ссылок
- Требует больше операций с указателями при модификации списка
- Не поддерживает произвольный доступ к элементам по индексу
Реализация двусвязного списка
Для начала работы со списком нужно определить узел, который будет содержать данные и указатели на следующий и предыдущий узлы.
Структура узла имеет данный вид
узел ├─данные ├─предыдущий узел └─следующий узел
Реализация на Python
Аннотация: Node - Структура узла data - данные, хранящиеся в элементе prev - указатель на предыдущий элемент next - указатель на следующий элемент
class Node: def __init__(self, data=None): self.data = data self.next = None self.prev = None
Реализация на С++
Аннотация: Node - Структура узла data - данные, хранящиеся в элементе prev - указатель на предыдущий элемент next - указатель на следующий элемент
struct Node { int data; Node* prev; Node* next: };
Структура двусвязного списка
Для ускорения работы с двусвязным списком можно хранить "голову" и "хвост" списка:
двусвязный список ├─голова ├─хвост └─размер(список)
Реализация на Python
Аннотация: doubly_linked_list - конструктор head - указатель на начало tail - указатель на конец size - размер списка
class doubly_linked_list: def __init__(self): self.head = None self.tail = None self.size = 0
Реализация на C++
Аннотация: doubly_linked_list - конструктор head - указатель на начало tail - указатель на конец size - размер списка temp - временный указатель
class doubly_linked_list { private: Node* head; Node* tail; int size public: doubly_linked_list () { head = nullptr; tail = nullptr; size = 0; } ~doubly_linked_list () { Node* temp = head; while (temp != nullptr) { Node* next = temp->next; delete temp; temp = next; } head = nullptr; tail = nullptr; } };
Добавление узла в конец списка
Новый узел всегда добавляется после последнего узла двусвязного списка. Например, если данный ДСС имеет вид:
Затем мы добавляем элемент 30 в конец и ДСС становится:
Алгоритм добавления узла в конец списка
новый <- узел(данные) если хвост == NULL хвост <- новый голова <- новый иначе предыдущий(новый) <- хвост следующий(хвост) <- новый хвост <- новый размер(список) <- размер(список) + 1
Реализация на Python
Аннотация: push_back - Метод добавления элемента в конец prev - указатель на предыдущий элемент next - указатель на следующий элемент head - указатель на начало tail - указатель на конец size - размер списка temp - временный указатель new_node - новый узел
def push_back(self, data): new_node = Node(data) if self.tail is None: self.head = self.tail = new_node else: new_node.prev = self.tail self.tail.next = new_node self.tail = new_node self.size += 1
Реализация на C++
Аннотация: push_back - Метод добавления элемента в конец prev - указатель на предыдущий элемент next - указатель на следующий элемент head - указатель на начало tail - указатель на конец size - размер списка temp - временный указатель new_node - новый узел
void push_back(int data) { Node* new_node = new Node(data); if (tail == nullptr) { head = new_node; tail = new_node; } else { new_node->prev = tail; tail->next = new_node; tail = new_node; } size++; }
Визуализация метода:
Сложность метода
Сложность данного метода равна O(1), если хранить узел в конце списка. Это означает, что время выполнения метода не зависит от размера списка и всегда одинаково.
Добавление узла в начало списка
Новый узел всегда добавляется перед головой двусвязного списка. Добавленный узел становится головой ДСС. Например, если ДСС имеет вид 1⇆0⇆2
и мы добавляем элемент 5 спереди, то ДСС становится 1⇆0⇆1⇆5.
новый <- узел(данные) если голова == NULL хвост <- новый голова <- новый иначе следующий(новый) <- голова предыдущий(голова) <- новый голова <- новый размер(список) <- размер(список) + 1
Реализация на Python
Аннотация: push_front - метод добавления элемента в начало prev - указатель на предыдущий элемент next - указатель на следующий элемент head - указатель на начало tail - указатель на конец size - размер списка temp - временный указатель new_node - новый узел
def push_front(self, data): new_node = Node(data) if self.head is None: self.head = self.tail = new_node else: new_node.next = self.head self.head.prev = new_node self.head = new_node self.size += 1
Реализация на С++
Аннотация: push_front - метод добавления элемента в начало prev - указатель на предыдущий элемент next - указатель на следующий элемент head - указатель на начало tail - указатель на конец size - размер списка temp - временный указатель new_node - новый узел
void push_front(int data) { Node* new_node = new Node(data); if (head == nullptr) { head = new_node; tail = new_node; } else { new_node->next = head; head->prev = new_node; head = new_node; } size++; }
Визуализация метода
Сложность метода
Сложность метода push_front такая же, как и у push_back, то есть равна O(1)
Удаление узла из конца списка
Метод pop_back в двусвязном списке удаляет последний элемент из списка.
Алгоритм его выполнения выглядит следующим образом:
Псевдокод
если хвост == NULL ничего если голова == хвост голова <- NULL хвост <- NULL иначе хвост = предыдущий(хвост) следующий(хвост) <- NULL размер(список) <- размер(список) - 1
Реализация на Python
Аннотация: pop_back - метод удаления элемента с конца prev - указатель на предыдущий элемент next - указатель на следующий элемент head - указатель на начало tail - указатель на конец size - размер списка temp - временный указатель new_node - новый узел
def pop_back(self): if self.tail is None: return if self.head == self.tail: self.head = self.tail = None else: self.tail = self.tail.prev self.tail.next = None self.size -= 1
Реализация на С++
Аннотация: pop_back - метод удаления элемента с конца prev - указатель на предыдущий элемент next - указатель на следующий элемент head - указатель на начало tail - указатель на конец size - размер списка temp - временный указатель new_node - новый узел
void pop_back() { if (tail == nullptr) { return; } if (head == tail) { head = nullptr; tail = nullptr; } else { tail = tail->prev; tail->next = nullptr; } size--; }
Визуализация метода
Сложность метода
Сложность этого метода - O(1), как у push_back и push_front, т.к. нам достаточно знать только данные головы или хвоста.
Удаление узла из начала списка
Метод pop_front в двусвязном списке удаляет первый элемент из списка и, так же как и pop_back, не принимает и не возвращает никаких данных, и имеет схожий алгоритм выполнения:
Псевдокод
если голова == NULL ничего если голова == хвост голова <- NULL хвост <- NULL иначе голова <- следующий(голова) предыдыдующий(голова) <- NULL размер(список) <- размер(список) - 1
Реализация на Python
Аннотация: pop_front - метод удаления элемента из начала prev - указатель на предыдущий элемент next - указатель на следующий элемент head - указатель на начало tail - указатель на конец size - размер списка temp - временный указатель new_node - новый узел
def pop_front(self): if self.head is None: return if self.head == self.tail: self.head = self.tail = None else: self.head = self.head.next self.head.prev = None self.size -= 1
Реализация на С++
Аннотация: pop_front - метод удаления элемента из начала prev - указатель на предыдущий элемент next - указатель на следующий элемент head - указатель на начало tail - указатель на конец size - размер списка temp - временный указатель new_node - новый узел
void pop_front() { if (head == nullptr) { return; } if (head == tail) { head = nullptr; tail = nullptr; } else { head = head->next; head->prev = nullptr; } size--; }
Визуализация метода
Сложность метода
Сложность у данного метода такая же как и у pop_back, push_back и push_front - O(1)
Поиск узла в списке по его значению
Чтобы найти узел в списке по его значению, нужно сравнить значение каждого узла списка с искомым. Если такой узел найден, то возвращаем указатель на него, иначе возвращаем NULL.
Пример алгоритма поиска узла
текущий <- голова пока текущий != NULL если данные(текущий) == данные(искомый) вернуть текущий текущий <- следующий(текущий) вернуть NULL
Реализация на Python
Аннотация find - функция поиска элемента current - текущий элемент head - указатель на начало data - значение элемента next - указатель на следующий элемент
def find(self, data): current = self.head while current is not None: if current.data == data: return current current = current.next return None
Реализация на C++
Аннотация find - функция поиска элемента current - текущий элемент head - указатель на начало data - значение элемента next - указатель на следующий элемент
Node* find(int data) { Node* current = head; while (current != nullptr) { if (current->data == data) { return current; } current = current->next; } return nullptr; }
Визуализация метода
@font-face {
font-family: "Virgil";
src: url("https://excalidraw.com/Virgil.woff2");
}
@font-face {
font-family: "Cascadia";
src: url("https://excalidraw.com/Cascadia.woff2");
}
Сложность метода
Сложность этого метода равна O, где n - это количество узлов в списке, так как в худшем случае придется пройтись по всему списку. В лучшем случае сложность будет равна O, если искомый узел будет в начале списка. Во всех остальных случаях сложность будет O, где k - это позиция искомого узла.
Псевдокод
Класс Узел(данные, предыдущий элемент <- пустота, следующий элемент <- пустота)
данные
предыдущий элемент
следующий элемент
Класс ДвунаправленныйСписок()
голова = пустота
хвост = пустота
размер = 0
Метод Конструктор()
голова = пустота
хвост = пустота
размер = 0
Метод Деструктор()
временный = голова
пока временный != пустота
следующий = временный.следующий элемент
удалить временный
временный = следующий
голова = пустота
хвост = пустота
Метод ДобавитьВКонец(данные)
новый узел = новый Узел(данные)
если хвост = пустота
голова = новый узел
хвост = новый узел
иначе
новый узел.предыдущий элемент = хвост
хвост.следующий элемент = новый узел
хвост = новый узел
размер += 1
Метод ДобавитьВНачало(данные)
новый узел = новый Узел(данные)
если голова = пустота
голова = новый узел
хвост = новый узел
иначе
новый узел.следующий элемент = голова
голова.предыдущий элемент = новый узел
голова = новый узел
размер += 1
Метод УдалитьИзКонца()
если хвост = пустота
вернуть
если голова = хвост
голова = пустота
хвост = пустота
иначе
хвост = хвост.предыдущий элемент
хвост.следующий элемент = пустота
размер -= 1
Метод УдалитьИзНачала()
если голова = пустота
вернуть
если голова = хвост
голова = пустота
хвост = пустота
иначе
голова = голова.следующий элемент
голова.предыдущий элемент = пустота
размер -= 1
Метод Найти(данные)
текущий = голова
пока текущий != пустота
если текущий.данные = данные
вернуть текущий
текущий = текущий.следующий элемент
вернуть пустота
Программа Основная()
список = новый ДвунаправленныйСписок()
список.ДобавитьВКонец(10)
список.ДобавитьВКонец(20)
список.ДобавитьВНачало(5)
список.Печать()
узел = список.Найти(10)
если узел != пустота
вывести "Найдено: " + узел.данные
иначе
вывести "Не найдено"
Реализация на Python
Аннотация: Node - Класс узла data - данные, хранящиеся в элементе prev - указатель на предыдущий элемент next - указатель на следующий элемент head - указатель на начало tail - указатель на конец size - размер списка doubly_linked_list - конструктор temp - временный указатель new_node - новый узел
class Node: def __init__(self, data=None): self.data = data self.next = None self.prev = None class doubly_linked_list: def __init__(self): self.head = None self.tail = None self.size = 0 def push_back(self, data): new_node = Node(data) if self.tail is None: self.head = self.tail = new_node else: new_node.prev = self.tail self.tail.next = new_node self.tail = new_node self.size += 1 def push_front(self, data): new_node = Node(data) if self.head is None: self.head = self.tail = new_node else: new_node.next = self.head self.head.prev = new_node self.head = new_node self.size += 1 def pop_back(self): if self.tail is None: return if self.head == self.tail: self.head = self.tail = None else: self.tail = self.tail.prev self.tail.next = None self.size -= 1 def pop_front(self): if self.head is None: return if self.head == self.tail: self.head = self.tail = None else: self.head = self.head.next self.head.prev = None self.size -= 1 def find(self, data): current = self.head while current is not None: if current.data == data: return current current = current.next return None def main(): dll = doubly_linked_list() dll.push_front(10) dll.push_front(20) dll.push_back(5) dll.print() node = dll.find(10) if node != None: print(f"Найден узел: {node.data}") else: print("Узел не найден")
Олимпиадная реализация на C++
Для решения олимпиадных задач лучше всего просто импортировать list командой #include<list>.
Аннотация my_list - двусявязный список
#include <iostream> #include <list> int main() { std::list<int> my_list = { 12, 5, 10, 9 }; for (int x : my_list) { std::cout << x << '\n'; } }
Продуктовая реализация на C++
Аннотация: Node - Структура узла data - данные, хранящиеся в элементе prev - указатель на предыдущий элемент next - указатель на следующий элемент head - указатель на начало tail - указатель на конец size - размер списка doubly_linked_list - конструктор temp - временный указатель new_node - новый узел
struct Node { int data; Node* prev; Node* next: }; class doubly_linked_list { private: Node* head; Node* tail; int size public: doubly_linked_list () { head = nullptr; tail = nullptr; size = 0; } ~doubly_linked_list () { Node* temp = head; while (temp != nullptr) { Node* next = temp->next; delete temp; temp = next; } head = nullptr; tail = nullptr; } }; void push_back(int data) { Node* new_node = new Node(data); if (tail == nullptr) { head = new_node; tail = new_node; } else { new_node->prev = tail; tail->next = new_node; tail = new_node; } size++; } void push_front(int data) { Node* new_node = new Node(data); if (head == nullptr) { head = new_node; tail = new_node; } else { new_node->next = head; head->prev = new_node; head = new_node; } size++; } void pop_back() { if (tail == nullptr) { return; } if (head == tail) { head = nullptr; tail = nullptr; } else { tail = tail->prev; tail->next = nullptr; } size--; } void pop_front() { if (head == nullptr) { return; } if (head == tail) { head = nullptr; tail = nullptr; } else { head = head->next; head->prev = nullptr; } size--; } Node* find(int data) { Node* current = head; while (current != nullptr) { if (current->data == data) { return current; } current = current->next; } return nullptr; } int main() { doubly_linked_list dll; dll.push_back(10); dll.push_back(20); dll.push_front(5); dll.print(); Node* node = dll.find(10); if (node != nullptr) { cout << "Found: " << node->data << endl; } else { cout << "Not found" << endl; } return 0; }
Заключение
Двусвязные списки являются важной структурой данных, которая обладает рядом преимуществ по сравнению с другими типами связных списков. Позволяя обходить узлы в обоих направлениях, двусвязные списки обеспечивают эффективный и гибкий доступ к данным. Однако, как и любая структура данных, двусвязные списки имеют свой набор недостатков, которые необходимо учитывать при их внедрении в программу. В целом, двусвязные списки остаются удобным инструментом для разработчиков, стремящихся оптимизировать хранение и поиск данных.