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

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

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

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

Односвязный список (однонаправленный связный список)

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

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

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

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

Характеристики

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

Односвязный список в языках программирования

Си

struct list
{
  int field; // поле данных
  struct list *next; // указатель на следующий элемент
};

применение односвязного списка:

struct list* l1 = (struct list*)malloc(sizeof(struct list));
l1->field = 1;
l1->next = (struct list*)malloc(sizeof(struct list));
l1->next->field = 2;
l1->next->next = (struct list*)malloc(sizeof(struct list));
/* и т.д. */

Двусвязный список (двунаправленный связный список)

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

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

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

Используется редко.

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

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

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

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

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

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

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

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

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

Преимущества

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

Недостатки

Недостатки связных списков вытекают из их главного свойства — последовательного доступа к данным:

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

См. также

• Сортировка связного списка

Примечания

1. Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, 2nd edition. The MIT Press, 2001. ISBN 0-262-03293-7
2. Выравнивание данных