Двусвязный список | это... Что такое Двусвязный список? (original) (raw)

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

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

В информатике, cвя́зный спи́сок — структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующее и/или предыдущее поле. Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.

Содержание

• 1 Виды связных списков
  • 1.1 Линейный связный список
    * 1.1.1 Односвязный список
    * 1.1.2 Двусвязный список
    * 1.1.3 XOR-связный список
  • 1.2 Кольцевой связный список
  • 1.3 Список с пропусками
  • 1.4 Развёрнутый связный список
• 2 Достоинства
• 3 Недостатки
• 4 См. также

Виды связных списков

Линейный связный список

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

В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента из данного невозможно.

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

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

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

Кольцевой связный список

Разновидностью связных списков является кольцевой (циклический, замкнутый) список. Он тоже может быть односвязным или двусвязным. Последний элемент кольцевого списка содержит указатель на первый, а первый (в случае двусвязного списка) — на последний.

Список с пропусками

Развёрнутый связный список

Достоинства

• лёгкость добавления и удаления элементов
• размер ограничен только объёмом памяти компьютера и разрядностью указателей

Недостатки

• сложность определения адреса элемента по его индексу (номеру) в списке
• на поля-указатели (указатели на следующий и предыдущий элемент) расходуется дополнительная память (в массивах, например, указатели не нужны)
• работа со списком медленнее, чем с массивами, так как к любому элементу списка можно обратиться, только пройдя все предшествующие ему элементы
• элементы списка могут быть расположены в памяти разреженно, что окажет негативный эффект на кэширование процессора
• над связными списками гораздо труднее (хотя и в принципе возможно) производить параллельные векторные операции, такие как вычисление суммы

См. также

• Список структур данных
• Стек
• Очередь
• Дерево
• Сортировка связного списка

Wikimedia Foundation.2010.

Полезное

Смотреть что такое "Двусвязный список" в других словарях:

• Связный список — В информатике, связный список базовая динамическая структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка.[1] Принципиальным… … Википедия
• Односвязный список — В информатике, cвязный список структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующее и/или предыдущее поле. Принципиальным преимуществом перед массивом является… … Википедия
• Связанный список — В информатике, cвязный список структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующее и/или предыдущее поле. Принципиальным преимуществом перед массивом является… … Википедия
• XOR-связный список — структура данных, похожая на обычный двусвязный список, однако в каждом элементе хранящая только один адрес результат выполнения операции XOR над адресами предыдущего и следующего элементов списка. Для того, чтобы перемещаться по списку,… … Википедия
• Развёрнутый связный список — список, каждый физический элемент которого содержит несколько логических (обычно в виде массива, что … Википедия
• Xor-связанный список — XOR связный список структура данных, похожая на обычный двусвязный список, однако в каждом элементе хранящая только один адрес результат выполнения операции XOR над адресами предыдущего и следующего элементов списка. Для того, чтобы перемещаться… … Википедия
• Структура данных — Бинарное дерево, простой пример ветвящейся связной структуры данных. Структура данных (англ. data structure) программная единица, позволяющая хран … Википедия
• Коллекция (программирование) — У этого термина существуют и другие значения, см. Коллекция. Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные исто … Википедия
• Коллекция данных — Коллекция в программировании программный объект, содержащий в себе, тем или иным образом, набор значений одного или различных типов, и позволяющий обращаться к этим значениям. Коллекция позволяет записывать в себя значения и извлекать их.… … Википедия
• Двусвязная очередь — (жарг. дэк, дек от англ. deque double ended queue; двухсторонняя очередь, двусвязный список, очередь с двумя концами) структура д … Википедия