Связный список
Последнее обновление
Связный список хранит последовательность как цепочку узлов, где каждый узел содержит значение и указатель на следующий узел. В отличие от массива, узлы не расположены в памяти непрерывно - вы следуете по указателям next, чтобы обойти список. Нажмите воспроизведение выше, чтобы увидеть, как узлы связываются в начале и в конце, как значение ищется обходом цепочки и как узел удаляется путём перенаправления указателя.
Вставка или удаление в начале - это O(1), потому что вы просто переустанавливаете голову. Достижение позиции в середине или конце - это O(n), потому что сначала нужно дойти туда. Этот компромисс -дешёвые концы, отсутствие произвольного доступа- и отличает связный список от массива.
Временная сложность
| Операция | Сложность | Примечания |
|---|---|---|
| Вставка в начало | O(1) | Переустановить голову |
| Вставка в конец | O(n) | Сначала дойти до конца (O(1) с указателем на хвост) |
| Поиск | O(n) | Следовать по указателям next |
| Удаление головы | O(1) | Переустановить голову за неё |
| Доступ по индексу | O(n) | Нет произвольного доступа |
Связный список против массива
| Аспект | Связный список | Массив |
|---|---|---|
| Память | Разбросанные узлы + указатели | Непрерывный блок |
| Произвольный доступ | O(n) | O(1) |
| Вставка/удаление в начале | O(1) | O(n) (сдвиг) |
| Дружественность к кэшу | Плохая | Хорошая |
Разобранный пример
Построение списка [10, 20], добавление 5 в начало, затем удаление 20:
| Шаг | Структура | Действие |
|---|---|---|
| Начало | head -> null | Пустой список |
| Вставка в начало 10 | head -> 10 -> null | Переустановить голову на новый узел, чей next - прежняя голова (null) |
| Вставка в конец 20 | head -> 10 -> 20 -> null | Дойти до узла 10, установить его next на новый узел 20 |
| Вставка в начало 5 | head -> 5 -> 10 -> 20 -> null | Новый узел 5 указывает на прежнюю голову 10; голова теперь указывает на 5 |
| Удаление 20 | head -> 5 -> 10 -> null | Дойти до 10, изменить его next с 20 на null; узел 20 отсоединён |
Когда использовать связный список
| Используйте, когда | Избегайте, когда |
|---|---|
| Вы вставляете или удаляете на концах (или в узле, который держите) гораздо чаще, чем индексируете | Вам нужен быстрый произвольный доступ по позиции (индексация O(1)) |
| Размер сильно меняется и вы не хотите затрат на изменение размера/копирование | Вы проходите плотные циклы, где локальность кэша определяет производительность |
| Вы строите очередь, стек или список смежности | Память ограничена: каждый узел платит дополнительный указатель на элемент |
| Вам нужны стабильные ссылки на узлы, которые переживают вставки в других местах | Вы в основном читаете и редко изменяете, поэтому массив проще и быстрее |
Код Linked List
Чистая, готовая к запуску реализация Linked List на Python, JavaScript, Java, C++, C. Выберите язык, скопируйте код или откройте его уже загруженным в плейграунде Coddy.
Код Linked List на Python
Python
1class Node:2 def __init__(self, value):3 self.value = value4 self.next = None5
6
7class LinkedList:8 def __init__(self):9 self.head = None10
11 def append(self, value):12 node = Node(value)13 if self.head is None:14 self.head = node15 return16 current = self.head17 while current.next:18 current = current.next19 current.next = node20
21 def find(self, value):22 current = self.head23 while current:24 if current.value == value:25 return True26 current = current.next27 return False28
29 def delete(self, value):30 # Re-link the previous node around the match31 current, prev = self.head, None32 while current:33 if current.value == value:34 if prev is None:35 self.head = current.next36 else:37 prev.next = current.next38 return True39 prev, current = current, current.next40 return False41
42 def __str__(self):43 values, current = [], self.head44 while current:45 values.append(str(current.value))46 current = current.next47 return " -> ".join(values) + " -> None"48
49
50lst = LinkedList()51for value in [3, 7, 1, 9]:52 lst.append(value)53
54print("List: ", lst)55print("find(7): ", lst.find(7))56lst.delete(1)57print("After delete(1):", lst)Код Linked List на JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.next = null;5 }6}7
8class LinkedList {9 constructor() {10 this.head = null;11 }12
13 append(value) {14 const node = new Node(value);15 if (!this.head) {16 this.head = node;17 return;18 }19 let current = this.head;20 while (current.next) current = current.next;21 current.next = node;22 }23
24 find(value) {25 for (let n = this.head; n; n = n.next) {26 if (n.value === value) return n;27 }28 return null;29 }30
31 delete(value) {32 if (!this.head) return false;33 if (this.head.value === value) {34 this.head = this.head.next;35 return true;36 }37 // Walk to the node just before the one to remove38 for (let n = this.head; n.next; n = n.next) {39 if (n.next.value === value) {40 n.next = n.next.next;41 return true;42 }43 }44 return false;45 }46
47 toArray() {48 const out = [];49 for (let n = this.head; n; n = n.next) out.push(n.value);50 return out;51 }52}53
54const list = new LinkedList();55for (const value of [10, 20, 30, 40]) list.append(value);56console.log("List:", list.toArray().join(" -> "));57console.log("find(30):", list.find(30) !== null);58list.delete(20);59console.log("After delete(20):", list.toArray().join(" -> "));Код Linked List на Java
Java
1public class Main {2 static class Node {3 int value;4 Node next;5 Node(int value) { this.value = value; }6 }7
8 static Node head;9
10 static void append(int value) {11 Node node = new Node(value);12 if (head == null) { head = node; return; }13 Node cur = head;14 while (cur.next != null) cur = cur.next;15 cur.next = node;16 }17
18 static boolean find(int value) {19 for (Node cur = head; cur != null; cur = cur.next) {20 if (cur.value == value) return true;21 }22 return false;23 }24
25 // Unlink the first node holding value26 static void delete(int value) {27 if (head == null) return;28 if (head.value == value) { head = head.next; return; }29 Node cur = head;30 while (cur.next != null && cur.next.value != value) cur = cur.next;31 if (cur.next != null) cur.next = cur.next.next;32 }33
34 static void print() {35 StringBuilder sb = new StringBuilder();36 for (Node cur = head; cur != null; cur = cur.next) {37 sb.append(cur.value).append(" -> ");38 }39 System.out.println(sb.append("null"));40 }41
42 public static void main(String[] args) {43 append(3); append(7); append(1); append(9);44 print();45 System.out.println("find 7: " + find(7));46 delete(7);47 print();48 System.out.println("find 7: " + find(7));49 }50}Код Linked List на C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* next = nullptr;6 explicit Node(int v) : value(v) {}7};8
9struct LinkedList {10 Node* head = nullptr;11
12 void append(int value) {13 Node* node = new Node(value);14 if (head == nullptr) {15 head = node;16 return;17 }18 Node* cur = head;19 while (cur->next != nullptr) cur = cur->next;20 cur->next = node;21 }22
23 bool find(int value) const {24 for (Node* cur = head; cur != nullptr; cur = cur->next) {25 if (cur->value == value) return true;26 }27 return false;28 }29
30 void remove(int value) {31 if (head == nullptr) return;32 if (head->value == value) { // removing the head is a special case33 Node* old = head;34 head = head->next;35 delete old;36 return;37 }38 for (Node* cur = head; cur->next != nullptr; cur = cur->next) {39 if (cur->next->value == value) {40 Node* old = cur->next;41 cur->next = old->next;42 delete old;43 return;44 }45 }46 }47
48 void print() const {49 for (Node* cur = head; cur != nullptr; cur = cur->next) {50 std::cout << cur->value << " -> ";51 }52 std::cout << "null\n";53 }54};55
56int main() {57 LinkedList list;58 for (int value : {10, 20, 30, 40}) list.append(value);59 list.print();60 std::cout << std::boolalpha << "find(30): " << list.find(30) << "\n";61 list.remove(20);62 list.remove(10);63 list.print();64 return 0;65}Код Linked List на C
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct Node {6 int value;7 struct Node* next;8} Node;9
10Node* head = NULL;11
12void append(int value) {13 Node* node = malloc(sizeof(Node));14 node->value = value;15 node->next = NULL;16 if (head == NULL) {17 head = node;18 return;19 }20 Node* cur = head;21 while (cur->next != NULL) cur = cur->next;22 cur->next = node;23}24
25bool find(int value) {26 for (Node* cur = head; cur != NULL; cur = cur->next) {27 if (cur->value == value) return true;28 }29 return false;30}31
32void deleteValue(int value) {33 if (head == NULL) return;34 if (head->value == value) { // removing the head is a special case35 Node* old = head;36 head = head->next;37 free(old);38 return;39 }40 for (Node* cur = head; cur->next != NULL; cur = cur->next) {41 if (cur->next->value == value) {42 Node* old = cur->next;43 cur->next = old->next;44 free(old);45 return;46 }47 }48}49
50void printList(void) {51 for (Node* cur = head; cur != NULL; cur = cur->next) {52 printf("%d -> ", cur->value);53 }54 printf("NULL\n");55}56
57int main(void) {58 int values[] = {10, 20, 30, 40};59 for (int i = 0; i < 4; i++) append(values[i]);60 printList();61 printf("find(30): %s\n", find(30) ? "true" : "false");62 deleteValue(20);63 deleteValue(10);64 printList();65 return 0;66}Часто задаваемые вопросы о связных списках
В чём разница между связным списком и массивом?
Массив хранит элементы в одном непрерывном блоке, что даёт произвольный доступ
O(1), но вставки/удаления O(n), которые сдвигают элементы. Связный список хранит узлы где угодно в памяти, соединённые указателями, что даёт вставки/удаления O(1) в известной позиции, но доступ O(n), так как нужно обходить цепочку.Когда следует использовать связный список?
Связные списки хороши, когда вы часто вставляете или удаляете на концах (или в узле, ссылку на который уже держите) и редко нуждаетесь в произвольном доступе - например, очереди, стеки, списки смежности и LRU-кэши. Если вам нужен быстрый индексированный доступ, массив или динамический массив обычно лучше.
Какова временная сложность связного списка?
Вставка или удаление в голове -
O(1). Поиск или достижение хвоста без указателя на хвост - O(n), потому что вы следуете по указателям next один за другим. Произвольного доступа O(1) нет: индексация в связном списке - это O(n).В чём разница между односвязным и двусвязным списком?
Односвязный список хранит только указатель
next на узел, поэтому вы можете идти в одном направлении, а удаление узла требует ссылки на его предшественника. Двусвязный список добавляет указатель prev, что позволяет обход назад и удаление O(1) удерживаемого узла ценой дополнительного указателя на узел и большей возни при каждой вставке и удалении.Почему вставка в конец O(n), если вставка в начало O(1)?
Вставка в начало лишь перенаправляет указатель
head, что является постоянной работой. Достижение конца означает следование по указателям next от головы до самого конца, что составляет O(n). Отдельный указатель tail делает вставку в конец тоже O(1), поэтому реальные списки часто отслеживают оба конца.Имеют ли связные списки вставку O(1) везде?
Нет - это распространённое заблуждение. Сама вставка -
O(1) только тогда, когда вы уже держите указатель на узел, после которого вставляете. Поиск этой позиции по значению или индексу всё равно стоит O(n), потому что нужно обойти цепочку, чтобы добраться туда.Связанные ресурсы
Больше визуализаций
