Список — различия между версиями
| Строка 4: | Строка 4: | ||
==Односвязный список == | ==Односвязный список == | ||
Простейшай реализация. В узлах хранятся данные и указатель на следующий элемент в списке. | Простейшай реализация. В узлах хранятся данные и указатель на следующий элемент в списке. | ||
| − | [[Файл:Single linked list-1-.png]] | + | [[Файл:Single linked list-1-.png|center|400px]] |
==Двусвязный список == | ==Двусвязный список == | ||
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы. | Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы. | ||
| − | [[Файл:Doubly linked list.png]] | + | [[Файл:Doubly linked list.png|center|400px]] |
===XOR-связный список === | ===XOR-связный список === | ||
XOR-связный список — структура данных, похожая на обычный двусвязный список, однако в каждом элементе хранящая только один адрес — результат выполнения операции XOR над адресами предыдущего и следующего элементов списка. Для того, чтобы перемещаться по списку, необходимо взять два последовательных адреса и выполнить над ними операцию XOR, которая и даст реальный адрес следующего элемента. | XOR-связный список — структура данных, похожая на обычный двусвязный список, однако в каждом элементе хранящая только один адрес — результат выполнения операции XOR над адресами предыдущего и следующего элементов списка. Для того, чтобы перемещаться по списку, необходимо взять два последовательных адреса и выполнить над ними операцию XOR, которая и даст реальный адрес следующего элемента. | ||
==Циклический список== | ==Циклический список== | ||
Первый элемент является следующим для последнего элемента списка. | Первый элемент является следующим для последнего элемента списка. | ||
| − | [[Файл:Circurlar linked list.png (872×241).png]] | + | [[Файл:Circurlar linked list.png (872×241).png|center|400px]] |
==Ссылки == | ==Ссылки == | ||
Версия 19:25, 26 апреля 2011
Связный список - структура данных, состоящая из узлов, содержащих помимо собственных данных ссылки на следующий или предыдущий узел списка. С помощью списков можно реализовать такие структуры данных как стек и очередь
Содержание
Односвязный список
Простейшай реализация. В узлах хранятся данные и указатель на следующий элемент в списке.
Двусвязный список
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.
XOR-связный список
XOR-связный список — структура данных, похожая на обычный двусвязный список, однако в каждом элементе хранящая только один адрес — результат выполнения операции XOR над адресами предыдущего и следующего элементов списка. Для того, чтобы перемещаться по списку, необходимо взять два последовательных адреса и выполнить над ними операцию XOR, которая и даст реальный адрес следующего элемента.
Циклический список
Первый элемент является следующим для последнего элемента списка.
.png)
Ссылки
http://en.wikipedia.org/wiki/Linked_list Linked list
Литература
- Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 11.2
- Д. Кнут: Искусство программирования том 1 глава 2.2
