Список — различия между версиями
| Строка 7: | Строка 7: | ||
==Двусвязный список == | ==Двусвязный список == | ||
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы. | Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы. | ||
| − | [[Файл: | + | [[Файл:twiceSpisok.png|center|400px]] |
===XOR-связный список === | ===XOR-связный список === | ||
В некоторых случаях использование двусвязного списка в явном виде является нецелесообразным. В целях экономии памяти можно хранить только результат выполнения операции Xor над адресами предыдущего и следующего элементов списка. Таким образом, зная адрес предыдущего элемента, мы можем вычислить адрес следующего элемента. | В некоторых случаях использование двусвязного списка в явном виде является нецелесообразным. В целях экономии памяти можно хранить только результат выполнения операции Xor над адресами предыдущего и следующего элементов списка. Таким образом, зная адрес предыдущего элемента, мы можем вычислить адрес следующего элемента. | ||
| Строка 31: | Строка 31: | ||
thisElement.next = thatElement; | thisElement.next = thatElement; | ||
</pre> | </pre> | ||
| + | [[Файл:insertAfter.png|center|490px]] | ||
===Поиск=== | ===Поиск=== | ||
Для того, чтобы найти элемент по значению (<tex>value</tex>), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем <tex>NULL</tex>. | Для того, чтобы найти элемент по значению (<tex>value</tex>), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем <tex>NULL</tex>. | ||
| Строка 49: | Строка 50: | ||
delete tmp; | delete tmp; | ||
</pre> | </pre> | ||
| + | [[Файл:removeHead.png|center|430px]] | ||
Удаление элемента после заданного (<tex>thisElement</tex>) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект. | Удаление элемента после заданного (<tex>thisElement</tex>) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект. | ||
<pre> | <pre> | ||
| Строка 57: | Строка 59: | ||
delete tmp; | delete tmp; | ||
</pre> | </pre> | ||
| + | [[Файл:removeAfter.png|center|550px]] | ||
==См.также== | ==См.также== | ||
[[Массив с увеличением/уменьшением размера]] | [[Массив с увеличением/уменьшением размера]] | ||
==Ссылки == | ==Ссылки == | ||
| − | [http://en.wikipedia.org/wiki/Linked_list Linked list] | + | * [http://en.wikipedia.org/wiki/Linked_list Linked list - Wikipedia] |
| + | |||
| + | * [http://ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_(%D0%B8%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0) Список - Википедия] | ||
==Литература == | ==Литература == | ||
* Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 11.2 | * Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 11.2 | ||
* Д. Кнут: Искусство программирования том 1 глава 2.2 | * Д. Кнут: Искусство программирования том 1 глава 2.2 | ||
Версия 13:01, 10 июня 2012
Связный список - структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как стек и очередь.
Содержание
Односвязный список
Простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.
Двусвязный список
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.
XOR-связный список
В некоторых случаях использование двусвязного списка в явном виде является нецелесообразным. В целях экономии памяти можно хранить только результат выполнения операции Xor над адресами предыдущего и следующего элементов списка. Таким образом, зная адрес предыдущего элемента, мы можем вычислить адрес следующего элемента.
Циклический список
Первый элемент является следующим для последнего элемента списка.
Операции на списке
Рассмотрим базовые операции на примере односвязного списка.
Вставка
Очевиден случай, когда необходимо добавить элемент () в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.
insert(newHead)
newHead.next = head;
head = newHead;
Если же на нужно вставить элемент () в определенную позицию после какого-то другого элемента (), то просто изменим соответствующие ссылки.
insertAfter(thisElement, thatElement)
thatElement.next = thisElement.next;
thisElement.next = thatElement;
Поиск
Для того, чтобы найти элемент по значению (), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем .
Search(value)
node = head;
while node != NULL and value != node.value
node = node.next;
return node;
Удаление
Для того, чтобы удалить голову списка - переназначим указатель на голову на второй элемент списка, а голову удалим.
removeHead()//удаление головы
if head != NULL
tmp = head;
head = head.next;
delete tmp;
Удаление элемента после заданного () происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.
removeAfter(thisElement)
if thisElement.next != NULL
tmp = thisElement.next;
thisElement.next = thisElement.next.next;
delete tmp;
См.также
Массив с увеличением/уменьшением размера
Ссылки
Литература
- Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 11.2
- Д. Кнут: Искусство программирования том 1 глава 2.2
