Визуализация
Сценарий: Вставка в голову
Легенда цветов
Как работает связный список
Идея структуры: В отличие от массива, элементы списка не обязаны лежать в памяти друг за другом. Каждый элемент (узел) хранит свои данные и указатель на следующий узел. Список начинается с указателя head, а последний элемент указывает на null.
Зачем вообще хранить адрес. Массив занимает один непрерывный кусок памяти: зная адрес начала и номер элемента, адрес любой ячейки считают арифметикой. Цена этого удобства - кусок нужной длины должен найтись целиком, а при его исчерпании массив переезжает на новое место. Список отказывается от непрерывности: каждый узел лежит там, где нашлось место, и сам несет адрес следующего. Поэтому список растет, пока свободна хоть одна ячейка, и не двигает соседей при вставке.
Отсутствие индексов. Мы не можем обратиться к пятому элементу напрямую. Чтобы найти элемент, нам всегда приходится начинать с головы (head) и переходить по ссылкам next.
Быстрая вставка и удаление. Главное преимущество списка - если мы уже дошли до нужного места, вставка или удаление занимают константное время O(1). Нам не нужно сдвигать все последующие элементы, как в массиве, достаточно лишь изменить пару ссылок (перецепить указатели).
Массив или список. Это две противоположные сделки. Динамический массив дает мгновенный доступ по индексу, но платит сдвигом элементов при вставке в середину и перевыделением памяти при росте. Список берет обратное: вставка и удаление стоят пары перецепок, а вот добраться до нужного места можно только пешком от головы.
Синонимы названия: Односвязный список, singly linked list.
Сложность
Сложность - это оценка того, как быстро растет потребление ресурса при росте числа элементов n. Ресурса у структуры два, поэтому и оценки две: по времени и по памяти. Обе записывают через O-нотацию - у нас есть отдельная анимация о том, как читать такие записи.
По времени
| Операция | Сложность | Комментарий |
|---|---|---|
| Доступ по индексу (поиск) | O(n) | Нужно пройти по ссылкам от начала списка до нужного элемента. |
| Вставка / удаление в начале (head) | O(1) | Простая перецепка указателя head на новый узел. |
| Вставка / удаление в середине | O(1) | * Само действие перецепки ссылок. Но чтобы дойти до нужного узла, потребуется O(n). |
| Вставка / удаление в конце | O(n) | Если мы не храним ссылку tail, нужно пройти весь список до конца. |
По памяти
| Характеристика | Оценка | Комментарий |
|---|---|---|
| Затраты по памяти | O(n) | Каждый элемент хранится в отдельном узле. Дополнительные накладные расходы идут на хранение самого указателя next. |
Свойства
| Свойство | Значение | Комментарий |
|---|---|---|
| Организация памяти | Несвязная | Узлы разбросаны по оперативной памяти и связываются между собой указателями next. |
| Доступ по индексу | O(n) | Произвольный доступ отсутствует; для поиска n-го элемента требуется последовательный обход от head. |
| Динамический размер | O(1) вставка | Список растет и уменьшается без затратных операций реаллокации и копирования памяти. |
Примеры реализации: Связный список (Linked List)
Код на C (с указателями)
#include <stdio.h>
#include <stdlib.h>
// Структура узла односвязного списка
struct Node {
int data; // Данные, хранящиеся в узле
struct Node* next; // Указатель на следующий узел
};
// Функция вставки элемента в начало списка (O(1))
void insertAtBeginning(struct Node** head_ref, int new_data) {
// 1. Выделяем память под новый узел в куче
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
// 2. Записываем данные в новый узел
new_node->data = new_data;
// 3. Новый узел теперь указывает на текущую голову списка
new_node->next = (*head_ref);
// 4. Сдвигаем голову списка на созданный узел
(*head_ref) = new_node;
}
// Поиск элемента в списке по значению (O(n))
struct Node* searchNode(struct Node* head, int target) {
struct Node* current = head; // Начинаем с головы
// Идем по списку, пока не дойдем до конца (NULL)
while (current != NULL) {
if (current->data == target) {
return current; // Элемент найден, возвращаем указатель на него
}
current = current->next; // Переходим к следующему узлу
}
return NULL; // Элемент не найден
}
// Удаление первого узла, хранящего заданное значение (O(n))
void deleteNode(struct Node** head_ref, int key) {
struct Node *temp = *head_ref, *prev = NULL;
// Если удаляемый узел - сама голова
if (temp != NULL && temp->data == key) {
*head_ref = temp->next; // Сдвигаем голову на второй элемент
free(temp); // Освобождаем память
return;
}
// Ищем узел с нужным ключом, запоминая предыдущий узел (prev)
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
// Если ключ не найден
if (temp == NULL) return;
// Исключаем узел из цепочки
prev->next = temp->next;
// Освобождаем память удаленного узла
free(temp);
}Код на Python
# В Python память очищается автоматически сборщиком мусора,
# поэтому нам не нужно явно вызывать free() при удалении узлов.
# Класс, представляющий отдельный узел списка
class Node:
def __init__(self, data):
self.data = data # Хранимое значение
self.next = None # Ссылка на следующий узел, по умолчанию None
# Класс самого односвязного списка
class LinkedList:
def __init__(self):
# Изначально список пуст, голова никуда не указывает
self.head = None
# Вставка элемента в начало списка - O(1)
def insert_at_beginning(self, data):
new_node = Node(data) # 1. Создаем узел
new_node.next = self.head # 2. Привязываем к нему текущую цепочку
self.head = new_node # 3. Объявляем его новой головой
# Поиск значения в списке - O(n)
def search(self, target):
current = self.head
# Перебираем узлы, пока они не закончатся
while current is not None:
if current.data == target:
return current # Нашли нужный узел
current = current.next # Шагаем дальше
return None # Ничего не нашли
# Удаление первого вхождения значения - O(n)
def delete_node(self, target):
current = self.head
# Случай 1: Удалять нужно саму голову
if current is not None and current.data == target:
self.head = current.next # Просто сдвигаем голову
return # Сборщик мусора сам удалит старую голову
# Случай 2: Ищем элемент в середине/конце
prev = None
while current is not None and current.data != target:
prev = current
current = current.next
# Если дошли до конца и ничего не нашли
if current is None:
return
# Отвязываем найденный узел, соединяя предыдущий со следующим
prev.next = current.nextКод на JavaScript
// Класс для отдельного узла
class Node {
constructor(data) {
this.data = data; // Хранимые данные
this.next = null; // Ссылка на следующий объект Node
}
}
// Класс связного списка, управляющий узлами
class LinkedList {
constructor() {
this.head = null; // Точка входа в список
}
// Вставка в начало - O(1)
insertAtBeginning(data) {
const newNode = new Node(data); // Выделение памяти под объект
newNode.next = this.head; // Цепляем текущий список к новому узлу
this.head = newNode; // Делаем новый узел головой
}
// Поиск узла по значению - O(n)
search(target) {
let current = this.head; // Начинаем с головы
while (current !== null) {
if (current.data === target) {
return current; // Успех
}
current = current.next; // Прыгаем по ссылке дальше
}
return null; // Провал
}
// Удаление узла по значению - O(n)
deleteNode(target) {
let current = this.head;
// Базовый случай: удаление головы
if (current !== null && current.data === target) {
this.head = current.next; // Переназначаем голову
// В JS сборщик мусора автоматически очистит старый current
return;
}
// Поиск узла, который нужно удалить
let prev = null;
while (current !== null && current.data !== target) {
prev = current;
current = current.next;
}
// Если элемента нет в списке
if (current === null) return;
// Перецепляем ссылку в обход удаляемого узла
prev.next = current.next;
}
}Хотите разобрать тему глубже? В нашем бесплатном курсе есть урок про линейный список на динамических объектах - с подробной теорией, задачами и проверочными вопросами.