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

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

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

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

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

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

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

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

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

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

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

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

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

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