Список — различия между версиями
(→Вставка) |
|||
| Строка 1: | Строка 1: | ||
| − | Связный список - структура данных, состоящая из узлов, содержащих помимо собственных данных ссылки на следующий или предыдущий узел списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]] | + | Связный список - структура данных, состоящая из узлов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий узел списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]]. |
__TOC__ | __TOC__ | ||
| Строка 15: | Строка 15: | ||
==Операции в связном списке== | ==Операции в связном списке== | ||
===Поиск=== | ===Поиск=== | ||
| − | find(k) | + | find(k) |
{ | { | ||
x = head; | x = head; | ||
| − | while ((x | + | while ((x.key != k)&&(x != NULL)) |
| − | x = x | + | x = x.next; |
return x; | return x; | ||
} | } | ||
| Строка 26: | Строка 26: | ||
===Вставка=== | ===Вставка=== | ||
| − | insert(k) | + | insert(k) |
{ | { | ||
tmp = head; | tmp = head; | ||
| − | x | + | x.key = k; |
| − | x | + | x.next = tmp; |
head = x; | head = x; | ||
} | } | ||
| Строка 36: | Строка 36: | ||
===Удаление=== | ===Удаление=== | ||
| − | delete(k) | + | delete(k) |
{ | { | ||
tmp = find(k); | tmp = find(k); | ||
| Строка 42: | Строка 42: | ||
{ | { | ||
//освобождаем память | //освобождаем память | ||
| − | tmp = tmp | + | tmp = tmp.next; |
} | } | ||
} | } | ||
Версия 00:31, 4 мая 2011
Связный список - структура данных, состоящая из узлов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий узел списка. С помощью списков можно реализовать такие структуры данных как стек и очередь.
Содержание
Односвязный список
Простейшай реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.
Двусвязный список
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.
XOR-связный список
XOR-связный список — структура данных, похожая на обычный двусвязный список, однако в каждом элементе хранящая только один адрес — результат выполнения операции XOR над адресами предыдущего и следующего элементов списка. Для того, чтобы перемещаться по списку, необходимо взять два последовательных адреса и выполнить над ними операцию XOR, которая и даст реальный адрес следующего элемента.
Циклический список
Первый элемент является следующим для последнего элемента списка.
.png)
Операции в связном списке
Поиск
find(k)
{
x = head;
while ((x.key != k)&&(x != NULL))
x = x.next;
return x;
}
Поиск в худшем случае выполняется за , так как может понадобиться просмотреть весь список.
Вставка
insert(k)
{
tmp = head;
x.key = k;
x.next = tmp;
head = x;
}
Время работы вставки O(1).
Удаление
delete(k)
{
tmp = find(k);
if (tmp != NULL)
{
//освобождаем память
tmp = tmp.next;
}
}
Само удаление работает за O(1), но если требуется сначала найти удаляемый элемент, то на поиск + удаление потребуется времени.
См.также
Массив с увеличением/уменьшением размера
Ссылки
http://en.wikipedia.org/wiki/Linked_list Linked list
Литература
- Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 11.2
- Д. Кнут: Искусство программирования том 1 глава 2.2
