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

Давайте обсудим способы линейного представления набора данных. Хранить данные из набора мы будем в линейном списке.

Линейный список

Линейный список — последовательность узлов (nodes), в которых хранятся записи. Все $n$ узлов $x_1, x_2, \dotsc, x_n$ логически организованы последовательно. То есть узел $x_k$ следует за узлом $x_{k-1}$ и предшествует узлу $x_{k+1}$ для всех $1 < k < n$ .

Обращаю внимание на то, что это только логическая упорядоченность. Физически узлы могут располагаться как угодно, какие-то узлы даже могут физически отсутствовать, главное чтобы логическая связь была такой.

С элементами линейного списка обычно совершаются следующие операции

Получение доступа к $k$ -му узлу списка для чтения, изменения полей записи и т.д.
Вставка нового узла сразу после или до $k$ -го узла списка
Удаление $k$ -го узла из списка
Объединение нескольких списков в один
Разбиение одного списка на несколько
Создание копии списка

Сделать структуру данных, которая бы эффективно выполняла все эти операции очень сложно. На самом деле для большинства задач это и не нужно.

Отдельного внимания заслуживают операции 1-3 при граничных случаях $k=1$ и $k=n$ . При таком условии эти операции можно выполнять в общем случае эффективнее и проще.

Связные списки

Линейные списки линейными делает логическая упорядоченность их элементов. Естественно желание превратить логическую упорядоченность в физическую. Вариантов это сделать много, но мы разберём только два основных, на которых строятся все остальные. Давайте превратим логическое высказывание «за этим узлом следует» в физическую ссылку.

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

Линейные списки, упорядоченные посредством ссылок называются связными списками. Есть несколько типов связных списков, которые я предлагаю подробно рассмотреть.

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

Связный список, в котором в каждом узле хранится только ссылка на следующий элемент, называется односвязным списком (одна связь).

Структура узла представляет собой нечто подобное

struct node:
    ref node next
    some additional data

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

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

Двусвязные списки

В каждый узел связного списка можно включить не одну. а две связи: на следующий и на предыдущий узлы.

struct node:
    node previous
    node next
    ...data...

Полуторасвязный список

Sparse list