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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Виды связных списков[править | править вики-текст]

Линейный связный список[править | править вики-текст]

Односвязный список (однонаправленный связный список)[править | править вики-текст]

Single linked list.png
Разновидность связного списка — односвязный список, содержащий 3 элемента

Линейный однонаправленный список — это структура данных, состоящая из элементов одного типа, связанных между собой последовательно посредством указателей. Каждый элемент списка имеет указатель на следующий элемент. Последний элемент списка указывает на NULL. Элемент, на который нет указателя, является первым (головным) элементом списка. Здесь ссылка в каждом узле указывает на следующий узел в списке. В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое текущего узла, невозможно.

В информатике линейный список обычно определяется как абстрактный тип данных (АТД), формализующий понятие упорядоченной коллекции данных. На практике линейные списки обычно реализуются при помощи массивов и связных списков. Иногда термин «список» неформально используется также как синоним понятия «связный список». К примеру, АТД нетипизированного изменяемого списка может быть определён как набор из конструктора и основных операций:

  1. операция, проверяющая список на пустоту;
  2. 3 операции добавления объекта в список (в начало, конец или внутрь после любого (n-ого) элемента списка);
  3. операция вычисляющая первый (головной) элемент списка;
  4. операция доступа к списку, состоящему из всех элементов исходного списка, кроме первого.

Характеристики[править | править вики-текст]

  • Длина списка. Количество элементов в списке.
  • Списки могут быть типизированными или нетипизированными. Если список типизирован, то тип его элементов задан, и все его элементы должны иметь типы, совместимые с заданным типом элементов списка. Обычно списки, реализованные при помощи массивов, являются типизированными.
  • Список может быть сортированным или несортированным
  • В зависимости от реализации может быть возможен произвольный доступ к элементам списка.

Двусвязный список (двунаправленный связный список)[править | править вики-текст]

Doubly linked list.png

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

XOR-связный список[править | править вики-текст]

Кольцевой связный список[править | править вики-текст]

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

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

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

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

Список с пропусками[править | править вики-текст]

Развёрнутый связный список[править | править вики-текст]

Достоинства[править | править вики-текст]

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

Недостатки[править | править вики-текст]

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, 2nd edition. The MIT Press, 2001. ISBN 0-262-03293-7