Список — различия между версиями
| Строка 1: | Строка 1: | ||
Связный список - структура данных, состоящая из узлов, содержащих помимо собственных данных ссылки на следующий или предыдущий узел списка. | Связный список - структура данных, состоящая из узлов, содержащих помимо собственных данных ссылки на следующий или предыдущий узел списка. | ||
| − | |||
__TOC__ | __TOC__ | ||
| − | == Односвязный список == | + | ==Односвязный список == |
| − | == Двусвязный список == | + | В узлах хранятся данные и указатель на следующий элемент в списке. |
| + | ==Двусвязный список == | ||
| + | Также хранится указатель на предыдущий элемент списка, благодаря чему в таком смысле проще удалять и переставлять элементы. | ||
| + | ==XOR-связный список == | ||
XOR-связный список — структура данных, похожая на обычный двусвязный список, однако в каждом элементе хранящая только один адрес — результат выполнения операции XOR над адресами предыдущего и следующего элементов списка. Для того, чтобы перемещаться по списку, необходимо взять два последовательных адреса и выполнить над ними операцию XOR, которая и даст реальный адрес следующего элемента. | XOR-связный список — структура данных, похожая на обычный двусвязный список, однако в каждом элементе хранящая только один адрес — результат выполнения операции XOR над адресами предыдущего и следующего элементов списка. Для того, чтобы перемещаться по списку, необходимо взять два последовательных адреса и выполнить над ними операцию XOR, которая и даст реальный адрес следующего элемента. | ||
| − | == | + | ==Ссылки == |
| + | http://en.wikipedia.org/wiki/Linked_list Linked list | ||
| + | |||
| + | ==Литература == | ||
| + | * Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 11.2 | ||
| + | * Д. Кнут: Искусство программирования том 1 глава 2.2 | ||
Версия 06:45, 22 марта 2011
Связный список - структура данных, состоящая из узлов, содержащих помимо собственных данных ссылки на следующий или предыдущий узел списка.
Односвязный список
В узлах хранятся данные и указатель на следующий элемент в списке.
Двусвязный список
Также хранится указатель на предыдущий элемент списка, благодаря чему в таком смысле проще удалять и переставлять элементы.
XOR-связный список
XOR-связный список — структура данных, похожая на обычный двусвязный список, однако в каждом элементе хранящая только один адрес — результат выполнения операции XOR над адресами предыдущего и следующего элементов списка. Для того, чтобы перемещаться по списку, необходимо взять два последовательных адреса и выполнить над ними операцию XOR, которая и даст реальный адрес следующего элемента.
Ссылки
http://en.wikipedia.org/wiki/Linked_list Linked list
Литература
- Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 11.2
- Д. Кнут: Искусство программирования том 1 глава 2.2
