Связанный список: варианты реализации

Связанные списки с использованием массивов узлов

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

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

class Entry {
  int next; // индекс следующей записи в массиве
  int prev; // индекс предыдущей записи (если двусвязный)
  String name;
  float balance;
}

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

int head;
Entry[] Records;

Связи между элементами формируются путем помещения индекса массива следующей (или предыдущей) ячейки в поле next или prev внутри данного элемента. Например:

В приведенном выше примере ListHead будет установлен в 2, местоположение первой записи в списке. Обратите внимание, что записи с 3 по 5 не являются частью списка. Эти ячейки доступны для любых дополнений в списке. Создав целочисленную переменную ListFree, можно создать свободный список, чтобы отслеживать доступные ячейки. Если все записи используются, размер массива должен быть увеличен или некоторые элементы должны быть удалены, прежде чем новые записи могут быть сохранены в списке.

Преимущества этого подхода включают в себя:

Связанный список можно перемещать, что означает, что он может перемещаться в памяти по желанию, а также может быть быстро и напрямую сериализован для хранения на диске или передачи по сети.
Особенно для небольшого списка индексы массивов могут занимать значительно меньше места, чем полный указатель на многих архитектурах.
Локальная ссылка может быть улучшена путем хранения узлов в памяти и периодической их реорганизации, хотя это также можно сделать в обычном хранилище.
Наивные динамические распределители памяти могут создавать чрезмерный объем служебной памяти для каждого выделенного узла; при таком подходе на каждый узел почти не накладываются дополнительные расходы.
Извлечение записи из предварительно выделенного массива происходит быстрее, чем использование динамического выделения памяти для каждого узла, поскольку динамическое выделение памяти обычно требует поиска свободного блока памяти желаемого размера.

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

Это увеличивает сложность реализации.
Увеличение большого массива при его заполнении может быть трудным или невозможным, тогда как поиск места для нового узла связанного списка в большом общем пуле памяти может быть проще.
Добавление элементов в динамический массив иногда (когда он заполнен) неожиданно занимает линейное (O(n)) вместо постоянного времени (хотя это все еще амортизированная константа).
Использование общего пула памяти оставляет больше памяти для других данных, если список меньше ожидаемого или если много узлов освобождено.

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

Языковая поддержка

Многие языки программирования, такие как Lisp и Scheme, имеют встроенные односвязные списки. Во многих функциональных языках эти списки состоят из узлов, каждый из которых называется cons или cons ячейка. cons имеют два поля: car, ссылка на данные для этого узла и cdr, ссылка на следующий узел. Хотя cons-ячейки могут использоваться для построения других структур данных, это является их основным назначением.

На языках, которые поддерживают абстрактные типы данных или шаблоны, ADT или шаблоны связанного списка доступны для создания связанных списков. На других языках связанные списки обычно создаются с использованием ссылок вместе с записями.

Внутреннее и внешнее хранилище

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

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

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

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

Ускорение поиска

Поиск определенного элемента в связанном списке, даже если он отсортирован, обычно требует времени O(n) (линейный поиск). Это один из основных недостатков связанных списков над другими структурами данных. В дополнение к рассмотренным выше вариантам, ниже приведены два простых способа улучшить время поиска.

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

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

Списки произвольного доступа

Список произвольного доступа - это список с поддержкой быстрого произвольного доступа для чтения или изменения любого элемента в списке. Одной из возможных реализаций является асимметричный двоичный список произвольного доступа, использующий асимметричную систему двоичных чисел, которая включает в себя список деревьев со специальными свойствами; это позволяет в наихудшем случае для выполнения head/cons операции с постоянным временем, а также в наихудшем случае доступ к элементу по индексу за логарифмическое время. Списки произвольного доступа могут быть реализованы как постоянные структуры данных.

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

Простым расширением списков произвольного доступа является min-list, который предоставляет дополнительную операцию, которая выдает минимальный элемент во всем списке за постоянное время (без сложности мутации).

Связанные структуры данных

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

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

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

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

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

Куча (heap) разделяет некоторые из свойств упорядочения связанного списка, но почти всегда реализуется с использованием массива. Вместо ссылок от узла к узлу следующие и предыдущие индексы данных рассчитываются с использованием индекса текущих данных.

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

Поиск по этому блогу

Alex tools