Структура данных — Двусвязный список
Двусвязный список (Doubly Linked List) — это расширение односвязного списка. Помимо указания на следующий узел, каждый узел также хранит указатель на предыдущий узел, образуя таким образом цепную структуру, доступную в обоих направлениях.
Структура и характеристики двусвязного списка
struct Node { int data; struct Node* prev; struct Node* next; };
prev указывает на предыдущий узел | data хранит данные | next указывает на следующий узел
Основные преимущества: можно напрямую удалить любой узел (не нужно сохранять предшественника), и поддерживается двунаправленный обход
Как показано на рисунке выше, каждый узел двусвязного списка имеетprevиnextдва указателя.
В языке C определение узла двусвязного списка выглядит следующим образом:
Пример
int data; /* Поле данных */
struct Node* prev; /* Указатель на предшественника: указывает на предыдущий узел */
struct Node* next; /* Указатель на последователя: указывает на следующий узел */
};
По сравнению с односвязным списком, самое большое преимущество двусвязного списка заключается в том, что из любого узла можно напрямую получить доступ к его предшественнику и последователю, а это означает, что при операции удаления больше не нужно сохранять дополнительную ссылку на узел-предшественник.
В односвязном списке, чтобы удалить заданный узел, необходимо знать его предшествующий узел, чтобы выполнить корректировку указателей. В двусвязном списке, поскольку каждый узел сам хранит указатель prev, операцию удаления можно выполнить напрямую.
Базовые операции
Операция вставки
Вставка в двусвязный список требует изменения указателей prev/next нового узла, а также указателей его предыдущего и следующего узлов, что включает всего четыре изменения указателей.
Пример
#include <stdlib.h>
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
/* Создать новый узел */
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
/* Вставить узел в начало Шаги: next нового узла указывает на исходный головной узел, а prev исходного головного узла указывает на новый узел */
/* Новый узел становится новым головным узлом */
struct Node* insertAtHead(struct Node* head, int value) {
struct Node* newNode = createNode(value);
if (head != NULL) {
newNode->next = head;
head->prev = newNode;
}
return newNode; /* Вставить новый узел после указанного узла Нужно оперировать 4 указателями: 1-2: prev и next нового узла 3: prev следующего узла (если он существует) 4: next предыдущего узла */
}
/* next нового узла указывает на исходный следующий узел */
/* prev нового узла указывает на предыдущий узел */
/* prev исходного следующего узла указывает на новый узел */
/* У предшественника next указывает на новый узел */
Операция удаления
void insertAfter(struct Node* prevNode, int value) {
if (prevNode == NULL) return;
struct Node* newNode = createNode(value);
newNode->next = prevNode->next; Пример
newNode->prev = prevNode; /* Удалить заданный узел (не нужно знать узел-предшественник; это главное преимущество двусвязного списка) Шаги: соединить предыдущий и следующий узлы друг с другом, пропустить текущий узел, а затем освободить текущий узел */
if (prevNode->next != NULL) {
prevNode->next->prev = newNode; /* Если головной узел удалён, обновить указатель головы */
}
prevNode->next = newNode; /* Сделать так, чтобы next узла-предшественника указывал на узел-последователь */
}
Операция удаления
Пример
Двусвязный список поддерживает два метода обхода: прямой и обратный.
void deleteNode(struct Node** headRef, struct Node* del) {
if (*headRef == NULL || del == NULL) return;
Пример
if (*headRef == del) {
*headRef = del->next;
}
/* Прямой обход: начать с головы, идти в направлении next */
if (del->prev != NULL) {
del->prev->next = del->next;
}
"Прямой обход: "
if (del->next != NULL) {
del->next->prev = del->prev;
}
free(del); /* Обратный обход: начать с хвоста, идти в направлении prev Сначала нужно найти хвостовой узел */
}
Операция обхода (двунаправленная)
/* От хвоста вернуться к голове в направлении prev */
Пример
/* Обход в прямом направлении: начать с head, вдоль направления next */
void traverse(struct Node* head) {
printf(Прямой обход:);
struct Node* cur = head;
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
/* Обратный обход: от хвоста, вдоль направления prev
Сначала нужно найти хвостовой узел */
void traverseBackward(struct Node* head) {
if (head == NULL) return;
/* Сначала перейти к последнему узлу (т. е. к хвосту) */
struct Node* cur = head;
while (cur->next != NULL) {
cur = cur->next;
}
/* Вернуться от хвоста к голове вдоль направления prev */
printf("Обратный обход: ");
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->prev;
}
printf("\n");
}
int main() {
struct Node* head = NULL;
/* Построить связный список: 10 <-> 20 <-> 30 */
head = insertAtHead(head, 30);
head = insertAtHead(head, 20);
head = insertAtHead(head, 10);
traverseForward(head); /* Вывод: прямой обход: 10 20 30 */
traverseBackward(head); /* Вывод: обратный обход: 30 20 10 */
return 0;
}
Двусвязный список против односвязного списка
| Критерий сравнения | Односвязный список | Двусвязный список |
|---|---|---|
| Структура узла | data + next | data + prev + next |
| Дополнительная память на узел | 8 байт (64-битная система) | 16 байт (64-битная система) |
| Прямой обход | Поддерживается | Поддерживается |
| Обратный обход | Не поддерживается | Поддерживается |
| Удалить узел | Нужно знать предшествующий узел | Предшественник не нужен, можно удалить напрямую |
| Операция вставки | Скорректировать 1–2 указателя | Скорректировать 4 указателя |