61
правка
Изменения
Нет описания правки
==Двусвязный список ==
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.
[[Файл:Doubly linked listtwiceSpisok.png|center|400px]]
===XOR-связный список ===
В некоторых случаях использование двусвязного списка в явном виде является нецелесообразным. В целях экономии памяти можно хранить только результат выполнения операции Xor над адресами предыдущего и следующего элементов списка. Таким образом, зная адрес предыдущего элемента, мы можем вычислить адрес следующего элемента.
thisElement.next = thatElement;
</pre>
[[Файл:insertAfter.png|center|490px]]
===Поиск===
Для того, чтобы найти элемент по значению (<tex>value</tex>), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем <tex>NULL</tex>.
delete tmp;
</pre>
[[Файл:removeHead.png|center|430px]]
Удаление элемента после заданного (<tex>thisElement</tex>) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.
<pre>
delete tmp;
</pre>
[[Файл:removeAfter.png|center|550px]]
==См.также==
[[Массив с увеличением/уменьшением размера]]
==Ссылки ==
* [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
* Д. Кнут: Искусство программирования том 1 глава 2.2
