Структура данных - связный список
Связный список (Linked List) — это линейная структура данных, состоящая из нескольких узлов, последовательно соединённых с помощью указателей.
В отличие от массивов, элементы связного списка не обязательно должны храниться в памяти непрерывно.
Основные понятия связного списка и структуры узла
Каждый узел связного списка содержит две части:Поле данных (data)Хранит фактические данные;Поле указателя (next)Указывает на следующий узел.
На рисунке выше показан реальный вид связного списка в памяти. Каждый узел с помощьюmallocнезависимо выделяется в куче, поэтому они могут быть не непрерывными в памяти. Узлы соединяются черезnextуказатели, а указатель next последнего узла указывает на NULL, обозначая конец связного списка.
В языке C узлы связного списка определяются с помощью структуры:
Пример
#include <stdlib.h> /* malloc, free */
/* Структура узла связного списка
data: поле данных, хранит целочисленные данные
next: поле-указатель, указывает на следующий узел того же типа */
struct Node {
int data;
struct Node* next;
};
/* Создать новый узел
Параметр value: значение данных узла
Возвращаемое значение: указатель на новый узел, возвращает NULL, если выделение памяти не удалось */
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Не удалось выделить память\n");
return NULL;
}
newNode->data = value; /* Установить данные */
newNode->next = NULL; /* Инициализировать поле next нового узла значением NULL */
return newNode;
}
struct Node* nextявляется самоссылающейся структурой, то есть структура содержит указатель на структуру того же типа. Это ключевая техника для построения всех связных структур данных (связных списков, деревьев, графов).
Базовые операции односвязного списка
Создание связного списка и обход
Пример
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
/* Обойти и вывести все узлы связного списка
Начать с головного узла и переходить от узла к узлу по указателям next до NULL */
void traverse(struct Node* head) {
struct Node* current = head; /* Начать с головного узла */
printf("Содержимое связного списка: ");
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next; /* Перейти к следующему узлу */
}
printf("NULL\n");
}
/* Создать связный список, содержащий n узлов (1, 2, 3, ..., n) */
struct Node* createList(int n) {
if (n <= 0) return NULL;
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->next = NULL;
struct Node* tail = head; /* tail всегда указывает на последний узел */
for (int i = 2; i <= n; i++) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = i;
newNode->next = NULL;
tail->next = newNode; /* Подключить новый узел к концу связного списка */
tail = newNode; /* Обновить указатель tail */
}
return head;
}
int main() {
struct Node* head = createList(5);
traverse(head);
/* Вывод: содержимое связного списка: 1 -> 2 -> 3 -> 4 -> 5 -> NULL */
return 0;
}
Операция вставки
На рисунке выше показан полный процесс изменения указателей при вставке и удалении в связном списке. Понимание порядка изменения указателей критически важно: если порядок неверен, это приведёт к разрыву связного списка или к утечкам памяти.
Пример
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
/* Вставить новый узел в начало связного списка (вставка в голову)
Временная сложность: O(1)
Возвращаемое значение: указатель на новый головной узел */
struct Node* insertAtHead(struct Node* head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = head; /* Новый узел указывает на исходный головной узел */
return newNode; /* Новый узел становится новым головным узлом */
}
/* Вставить новый узел в конец связного списка (вставка в хвост)
Временная сложность: O(n), требуется обход до хвоста */
struct Node* insertAtTail(struct Node* head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if (head == NULL) {
return newNode; /* Пустой связанный список, новый узел становится головным узлом */
}
struct Node* current = head;
while (current->next != NULL) {
current = current->next; /* Пройти до последнего узла */
}
current->next = newNode; /* Хвостовой узел указывает на новый узел */
return head;
}
/* Вставить новый узел после указанной позиции
Временная сложность: O(n), сначала требуется найти prevNode */
void insertAfter(struct Node* prevNode, int value) {
if (prevNode == NULL) {
printf("Узел-предшественник не может быть null\n");
return;
}
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
/* Важно: сначала новый узел должен указывать на своего преемника, затем предшественник должен указывать на новый узел */
newNode->next = prevNode->next;
prevNode->next = newNode;
}
void printList(struct Node* head) {
struct Node* cur = head;
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
int main() {
struct Node* head = NULL;
head = insertAtHead(head, 30); /* Связный список: 30 */
head = insertAtHead(head, 20); /* Связный список: 20 -> 30 */
head = insertAtHead(head, 10); /* Связный список: 10 -> 20 -> 30 */
printf("После вставки в голову: "); printList(head); /* Вывод: 10 20 30 */
head = insertAtTail(head, 40); /* Связный список: 10 -> 20 -> 30 -> 40 */
printf("После вставки в хвост: "); printList(head); /* Вывод: 10 20 30 40 */
insertAfter(head->next, 25); /* Вставить 25 после 20 */
printf("После вставки в середину: "); printList(head);
/* Вывод: 10 20 25 30 40 */
return 0;
}
Операция удаления
Пример
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
/* Удалить головной узел связного списка
Временная сложность: O(1)
Возвращаемое значение: указатель на новый головной узел */
struct Node* deleteHead(struct Node* head) {
if (head == NULL) return NULL;
struct Node* temp = head; /* Сохранить старый головной узел */
head = head->next; /* Переместить указатель head на следующий узел */
free(temp); /* Освободить память старого головного узла */
return head;
}
/* Удалить первый узел в связном списке со значением target
Временная сложность: O(n), требуется обойти список, чтобы найти целевой узел */
struct Node* deleteByValue(struct Node* head, int target) {
if (head == NULL) return NULL;
/* Особый случай: целевое значение находится в головном узле */
if (head->data == target) {
struct Node* temp = head;
head = head->next;
free(temp);
return head;
}
/* Пройти, чтобы найти узел-предшественник целевого узла */
struct Node* current = head;
while (current->next != NULL && current->next->data != target) {
current = current->next;
}
/* Найти целевой узел и удалить его */
if (current->next != NULL) {
struct Node* temp = current->next;
current->next = current->next->next; /* Пропустить целевой узел */
free(temp); /* Освободить память целевого узла */
}
return head;
}
void printList(struct Node* head) {
struct Node* cur = head;
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
int main() {
/* Построить связный список: 10 -> 20 -> 30 -> 40 */
struct Node* head = NULL;
int vals[] = {10, 20, 30, 40};
for (int i = 3; i >= 0; i--) {
struct Node* n = (struct Node*)malloc(sizeof(struct Node));
n->data = vals[i];
n->next = head;
head = n;
}
printf("Исходный связный список: "); printList(head); /* Вывод: 10 20 30 40 */
head = deleteHead(head);
printf("После удаления головного узла: "); printList(head); /* Вывод: 20 30 40 */
head = deleteByValue(head, 30);
printf("После удаления 30: "); printList(head); /* Вывод: 20 40 */
return 0;
}
В операции удаления в связном списке,
free()очень важно. Если вы только изменяете указатели, не освобождая память удаляемого узла, это приведет к утечке памяти. В языке C каждыйmallocдолжен иметь соответствующийfree。
Сравнение связного списка и массива
| Критерий сравнения | Массив | Связный список |
|---|---|---|
| Расположение в памяти | Непрерывное хранение | Разбросанное хранение, связанное указателями |
| Произвольный доступ | O(1) | O(n) |
| Вставка/удаление в голове | O(n) | O(1) |
| Вставка/удаление в хвосте | O(1) | O(1) (с указателем на хвост) / O(n) (без указателя на хвост) |
| Вставка/удаление в середине | O(n) | O(1)(известная позиция) |
| Накладные расходы памяти | Только данные | Данные + указатель (8 дополнительных байтов на узел (64-битная архитектура)) |
| Кэш-дружественность | Высокая(пространственная локальность) | Низкая(узлы разбросаны) |
| Ёмкость | Фиксированный (статический массив) | Динамический рост |
Понимание этого компромисса — один из ключевых навыков при выборе структуры данных.
Если размер данных известен до времени выполнения и не меняется часто, а также требуется частый произвольный доступ, массив — лучший выбор.
Если размер данных часто меняется, а его масштаб не определён, динамические структуры, такие как связанные списки, более гибкие.
Другие расширения