76
правок
Изменения
Нет описания правки
Связный список - структура данных, состоящая из узлов, содержащих помимо собственных данных ссылки на следующий или предыдущий узел списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]].Вставка и удаление в списке работают за O(1).
__TOC__
==Односвязный список ==
Простейшай реализациясписка. В узлах хранятся данные и указатель на следующий элемент в списке.
[[Файл:Single linked list-1-.png|center|400px]]
==Двусвязный список ==
Первый элемент является следующим для последнего элемента списка.
[[Файл:Circurlar linked list.png (872×241).png|center|400px]]
==Операции в связном списке==
===Поиск===
find(k)
{
x = head;
while ((x->key != k)&&(x != NULL))
x = x -> next;
return x;
}
Поиск в худшем случае выполняется за <math>\Theta(n)</math>, так как может понадобиться просмотреть весь список.
===Вставка===
insert(k)
{
tmp = head;
x->key = k;
x->next = tmp;
head = x;
}
Время работы вставки O(1).
===Удаление===
Само удаление работает за O(1), но если требуется сначала найти удаляемый элемент, то на поиск + удаление потребуется <math>\Theta(n)</math> времени.
==См.также==
[[Массив с увеличением/уменьшением размера]]
