Связанный список

Связанный список

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

Содержание

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

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

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

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

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

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

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

Основная статья: XOR-связный список

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

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

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

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

Основная статья: Список с пропусками

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

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

Достоинства

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

Недостатки

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

См. также


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Полезное


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

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

  • Развернутый связанный список — Развёрнутый связанный список список, каждый физический элемент которого содержит несколько логических (обычно в виде массива, что позволяет ускорить доступ к отдельным элементам). Позволяет значительно уменьшить размер памяти и увеличить… …   Википедия

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

  • Список понятий — Список понятий, содержащих слово «русский» Содержание 1 Классические понятия 2 Зарубежные понятия 3 Новые понятия …   Википедия

  • Список знаменитостей в South Park — В этой статье приводится список знаменитостей, упомянутых или спародированных тем или иным образом в мультсериале «Южный парк». Звёздочкой (*) помечены умершие знаменитости, буквой (V) отмечены персонажи, которых озвучивали их реальные прототипы …   Википедия

  • Список эпизодов телесериала «Дневники вампира» — Список серий сверхъестественного драматического американского телесериала «Дневники вампира», разработанного Кевином Уильямсоном и Джули Плек и снятого по мотивам одноименной серии книг, написанной Лизой Джейн Смит. Пилотная серия была показана… …   Википедия

  • Список шашечных терминов — Список терминов, применяющие в игре в шашки. атака наступательные действия (серия ходов) в партии, наиболее решительный способ достижения цели. Атака Гоогланда (международные шашки). Вторжение белых (черных) с 27 на 22 (с 24 на 29) в дебюте,… …   Википедия

  • Список персонажей и организаций в F.E.A.R. — Список персонажей компьютерной игры F.E.A.R., F.E.A.R. 2: Project Origin, F.E.A.R. 3 и официальных дополнений к играм. Содержание 1 Армия США 1.1 Ф.Е.А.Р. 1.1.1 Сотрудники F.E.A.R …   Википедия

  • Список модификаций игр компании Valve — Содержание 1 Модификации, перешедшие на коммерческую основу …   Википедия

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


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»