Список — различия между версиями
| Строка 29: | Строка 29: | ||
===Поиск=== | ===Поиск=== | ||
| − | Search() | + | Search()//ищем элемент |
{ | { | ||
node = head; | node = head; | ||
while ((node != NULL) && (we_are_looking_not_for(node))) | while ((node != NULL) && (we_are_looking_not_for(node))) | ||
node = node->next; | node = node->next; | ||
| + | return node; | ||
} | } | ||
===Удаление=== | ===Удаление=== | ||
| − | + | removeHead()//удаление головы | |
| + | { | ||
| + | if (head != NULL) | ||
| + | { | ||
| + | tmp = head; | ||
| + | head = head->next; | ||
| + | delete tmp; | ||
| + | } | ||
| + | } | ||
| + | |||
| − | + | removeAfter(this_element) | |
| + | { | ||
| + | if ((this_element != NULL)&&(this_element->next != NULL)) | ||
| + | { | ||
| + | tmp = this_element->next; | ||
| + | this_element->next = this_element->next->next; | ||
| + | delete tmp; | ||
| + | } | ||
| + | } | ||
==См.также== | ==См.также== | ||
[[Массив с увеличением/уменьшением размера]] | [[Массив с увеличением/уменьшением размера]] | ||
Версия 10:34, 7 июня 2011
Связный список - структура данных, состоящая из узлов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий узел списка. С помощью списков можно реализовать такие структуры данных как стек и очередь.
Содержание
Односвязный список
Простейшай реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.
Двусвязный список
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.
XOR-связный список
XOR-связный список — структура данных, похожая на обычный двусвязный список, однако в каждом элементе хранящая только один адрес — результат выполнения операции XOR над адресами предыдущего и следующего элементов списка. Для того, чтобы перемещаться по списку, необходимо взять два последовательных адреса и выполнить над ними операцию XOR, которая и даст реальный адрес следующего элемента.
Циклический список
Первый элемент является следующим для последнего элемента списка.
.png)
Операции на списке
Рассмотрим базовые операции на примере односвязного списка.
Вставка
insert(new_head)// вставка в голову списка
{
new_head->next = head;
head = new_head;
}
insertAfter(this_element, that_element)// вставка после this_element
{
that_element->next = this_element->next;
this_element->next = that_element;
}
Поиск
Search()//ищем элемент
{
node = head;
while ((node != NULL) && (we_are_looking_not_for(node)))
node = node->next;
return node;
}
Удаление
removeHead()//удаление головы
{
if (head != NULL)
{
tmp = head;
head = head->next;
delete tmp;
}
}
removeAfter(this_element)
{
if ((this_element != NULL)&&(this_element->next != NULL))
{
tmp = this_element->next;
this_element->next = this_element->next->next;
delete tmp;
}
}
См.также
Массив с увеличением/уменьшением размера
Ссылки
http://en.wikipedia.org/wiki/Linked_list Linked list
Литература
- Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 11.2
- Д. Кнут: Искусство программирования том 1 глава 2.2
