Список — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
Связный список - структура данных, состоящая из узлов, содержащих помимо собственных данных ссылки на следующий или предыдущий узел списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]]
+
Связный список - структура данных, состоящая из узлов, содержащих помимо собственных данных ссылки на следующий или предыдущий узел списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]].Вставка и удаление в списке работают за O(1).
  
 
__TOC__
 
__TOC__
Строка 13: Строка 13:
 
Первый элемент является следующим для последнего элемента списка.
 
Первый элемент является следующим для последнего элемента списка.
 
[[Файл:Circurlar linked list.png (872×241).png|center|400px]]
 
[[Файл:Circurlar linked list.png (872×241).png|center|400px]]
 
+
==См.также==
 +
[[Массив с увеличением/уменьшением размера]]
 
==Ссылки ==
 
==Ссылки ==
 
http://en.wikipedia.org/wiki/Linked_list Linked list
 
http://en.wikipedia.org/wiki/Linked_list Linked list

Версия 19:38, 26 апреля 2011

Связный список - структура данных, состоящая из узлов, содержащих помимо собственных данных ссылки на следующий или предыдущий узел списка. С помощью списков можно реализовать такие структуры данных как стек и очередь.Вставка и удаление в списке работают за O(1).

Односвязный список

Простейшай реализация. В узлах хранятся данные и указатель на следующий элемент в списке.

Single linked list-1-.png

Двусвязный список

Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.

Doubly linked list.png

XOR-связный список

XOR-связный список — структура данных, похожая на обычный двусвязный список, однако в каждом элементе хранящая только один адрес — результат выполнения операции XOR над адресами предыдущего и следующего элементов списка. Для того, чтобы перемещаться по списку, необходимо взять два последовательных адреса и выполнить над ними операцию XOR, которая и даст реальный адрес следующего элемента.

Циклический список

Первый элемент является следующим для последнего элемента списка.

Circurlar linked list.png (872×241).png

См.также

Массив с увеличением/уменьшением размера

Ссылки

http://en.wikipedia.org/wiki/Linked_list Linked list

Литература

  • Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 11.2
  • Д. Кнут: Искусство программирования том 1 глава 2.2