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

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

Связанные списки против динамических массивов

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

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

Более того, произвольное количество элементов может быть вставлено в связанный список, ограниченный только общей доступной памятью; в то время как динамический массив в конечном итоге заполнит свою базовую структуру данных массива, и ему придется перераспределять данные (заново выделять память) - дорогая операция, которая может оказаться даже невозможной при фрагментации памяти. Хотя стоимость перераспределения может быть усреднена по вставкам, стоимость вставки из-за перераспределения все равно будет амортизированной O(1). Это помогает с добавлением элементов в конце массива, но вставка (или удаление из) средних позиций по-прежнему сопряжена с чрезмерными затратами из-за перемещения данных для поддержания смежности. Размер массива, из которого удалено много элементов, также может быть изменен, чтобы не тратить слишком много места.

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

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

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

Хороший пример, который подчеркивает плюсы и минусы использования динамических массивов и связанных списков, - это реализация программы, решающей проблему Иосифа. Проблема Иосифа является методом выборов, который работает, когда группа людей стоит в кругу. Начиная с заранее определенного человека, вы считаете по кругу n раз. Как только вы достигнете n-го человека, выньте его из круга и попросите участников замкнуть круг. Затем посчитайте по кругу те же n раз и повторяйте процесс, пока не останется только один человек. Этот человек побеждает на выборах. Это показывает сильные и слабые стороны связанного списка по сравнению с динамическим массивом, потому что если вы рассматриваете людей как связанные узлы в круговом связанном списке, то это показывает, насколько легко связанный список может удалять узлы (так как ему нужно только переставить ссылки на разные узлы). Тем не менее, связанный список будет плох в поиске следующего человека для удаления, и ему нужно будет искать в списке, пока не найдет этого человека. Динамический массив, с другой стороны, будет плох в удалении узлов (или элементов), поскольку он не может удалить один узел без индивидуального смещения всех элементов вверх по списку на один. Тем не менее, исключительно легко найти n-го человека в круге, напрямую ссылаясь на него по его положению в массиве.

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

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

Односвязные линейные списки против других списков

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

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

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

В частности, конечные дозорные узлы могут совместно использоваться односвязными некруговыми списками. Один и тот же конечный дозорный узел может использоваться для каждого такого списка. Например, в Lisp каждый правильный список заканчивается ссылкой на специальный узел, обозначаемый nil или (), чьи ссылки CAR и CDR указывают на себя. Таким образом, процедура Lisp может безопасно взять CAR или CDR любого списка.

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

Двусвязные против односвязных

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

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

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

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

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

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

Использование дозорных узлов

Дозорный узел может упростить определенные операции со списками, гарантируя, что следующий или предыдущий узлы существуют для каждого элемента и что даже пустые списки имеют по крайней мере один узел. Можно также использовать сторожевой узел в конце списка с соответствующим полем данных, чтобы исключить некоторые проверки конца списка. Например, при сканировании списка в поисках узла с заданным значением x, установка поля данных дозорного в x делает ненужным тестирование на конец списка внутри цикла. Другим примером является объединение двух отсортированных списков: если у их стражей поля данных установлены на +∞, выбор следующего выходного узла не требует специальной обработки для пустых списков.

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

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

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

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

Alex tools