Список — различия между версиями
| Строка 17: | Строка 17: | ||
Рассмотрим базовые операции на примере односвязного списка. | Рассмотрим базовые операции на примере односвязного списка. | ||
===Вставка=== | ===Вставка=== | ||
| − | + | <pre> | |
| − | + | insert(newHead)// вставка в голову списка | |
| − | + | newHead.next = head; | |
| − | + | head = newHead; | |
| − | + | </pre> | |
| − | + | <pre> | |
| − | + | insertAfter(thisElement, thatElement)// вставка после this_element | |
| − | + | thatElement.next = thisElement.next; | |
| − | + | thisElement.next = thatElement; | |
| − | + | </pre> | |
| − | |||
| − | |||
===Поиск=== | ===Поиск=== | ||
| − | + | <pre> | |
| − | + | Search(value)//ищем элемент, в случае неудачи возвращаем NULL | |
| − | + | node = head; | |
| − | + | while (node != NULL) && (value != node.value) | |
| − | + | node = node.next; | |
| − | + | return node; | |
| − | + | </pre> | |
===Удаление=== | ===Удаление=== | ||
| − | + | <pre> | |
| − | + | removeHead()//удаление головы | |
| − | + | if head != NULL | |
| − | + | tmp = head; | |
| − | + | head = head.next; | |
| − | + | delete tmp; | |
| − | + | </pre> | |
| − | + | <pre> | |
| − | + | removeAfter(thisElement) | |
| − | + | if (thisElement != NULL) && (thisElement.next != NULL) | |
| − | + | tmp = thisElement.next; | |
| − | + | thisElement.next = thisElement.next.next; | |
| − | + | delete tmp; | |
| − | + | </pre> | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
==См.также== | ==См.также== | ||
[[Массив с увеличением/уменьшением размера]] | [[Массив с увеличением/уменьшением размера]] | ||
Версия 20:35, 8 июня 2012
Связный список - структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как стек и очередь.
Содержание
Односвязный список
Простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.
Двусвязный список
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.
XOR-связный список
В некоторых случаях использование двусвязного списка в явном виде является нецелесообразным. В целях экономии памяти можно хранить только результат выполнения операции Xor над адресами предыдущего и следующего элементов списка. Таким образом, зная адрес предыдущего элемента, мы можем вычислить адрес следующего элемента.
Циклический список
Первый элемент является следующим для последнего элемента списка.
.png)
Операции на списке
Рассмотрим базовые операции на примере односвязного списка.
Вставка
insert(newHead)// вставка в голову списка
newHead.next = head;
head = newHead;
insertAfter(thisElement, thatElement)// вставка после this_element
thatElement.next = thisElement.next;
thisElement.next = thatElement;
Поиск
Search(value)//ищем элемент, в случае неудачи возвращаем NULL
node = head;
while (node != NULL) && (value != node.value)
node = node.next;
return node;
Удаление
removeHead()//удаление головы
if head != NULL
tmp = head;
head = head.next;
delete tmp;
removeAfter(thisElement)
if (thisElement != NULL) && (thisElement.next != NULL)
tmp = thisElement.next;
thisElement.next = thisElement.next.next;
delete tmp;
См.также
Массив с увеличением/уменьшением размера
Ссылки
Литература
- Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 11.2
- Д. Кнут: Искусство программирования том 1 глава 2.2
