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

«Динамический список» перенаправляется сюда. Рекомендации Википедии, описывающие статьи списков, которые могут никогда не быть завершены, см. в Wikipedia:WikiProject Lists .

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

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

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

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

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

История

Связанные списки были разработаны в 1955–1956 годах Алленом Ньюэллом , Клиффом Шоу и Гербертом А. Саймоном в корпорации RAND и Университете Карнеги-Меллон в качестве основной структуры данных для их языка обработки информации (IPL). IPL использовалась авторами для разработки нескольких ранних программ искусственного интеллекта , включая Logic Theory Machine, General Task Solver и компьютерную шахматную программу. Отчеты об их работе появились в журнале IRE Transactions on Information Theory в 1956 году, а также в материалах нескольких конференций с 1957 по 1959 год, включая материалы Западной объединенной компьютерной конференции в 1957 и 1958 годах и обработку информации (материалы первой Международной конференции ЮНЕСКО по обработке информации). ) в 1959 году. Теперь уже классическая диаграмма, состоящая из блоков, представляющих узлы списка со стрелками, указывающими на последовательные узлы списка, появляется в «Программировании машины логической теории» Ньюэлла и Шоу в Proc. WJCC, февраль 1957 года. Ньюэлл и Саймон были отмечены премией Тьюринга ACM. в 1975 году за «внесенный фундаментальный вклад в искусственный интеллект, психологию человеческого познания и обработку списков». Проблема машинного перевода для обработки естественного языка побудила Виктора Ингве из Массачусетского технологического института (MIT) использовать связанные списки в качестве структур данных в своем языке программирования COMIT для компьютерных исследований в области лингвистики . Отчет об этом языке под названием «Язык программирования для механического перевода» появился в журнале Mechanical Translation в 1958 году.

Еще одно раннее появление связанных списков принадлежит Гансу Питеру Луну , который в январе 1953 года написал внутренний меморандум IBM , в котором предлагалось использовать связанные списки в связанных хеш-таблицах.

LISP , обозначающий процессор списков, был создан Джоном Маккарти в 1958 году, когда он работал в Массачусетском технологическом институте, а в 1960 году он опубликовал его проект в статье в журнале Communications of the ACM под названием «Рекурсивные функции символических выражений и их машинное вычисление, часть». Я". Одной из основных структур данных LISP является связанный список.

К началу 1960-х годов польза как связанных списков, так и языков, использующих эти структуры в качестве основного представления данных, была хорошо известна. Берт Грин из Лаборатории Линкольна Массачусетского технологического института опубликовал обзорную статью под названием «Компьютерные языки для манипулирования символами» в журнале IRE Transactions on Human Factors in Electronics в марте 1961 года, в которой суммированы преимущества подхода связанного списка. Более поздняя обзорная статья Боброу и Рафаэля «Сравнение компьютерных языков обработки списков» появилась в журнале Communications of the ACM в апреле 1964 года.

Несколько операционных систем, разработанных консультантами по техническим системам (первоначально из Вест-Лафайет, Индиана, а затем из Чапел-Хилл, Северная Каролина), использовали односвязные списки в качестве файловых структур. Запись каталога указывала на первый сектор файла, а последующие части файла находились с помощью указателей перемещения. Системы, использующие этот метод, включали Flex (для ЦП Motorola 6800 ), mini-Flex (тот же ЦП) и Flex9 (для ЦП Motorola 6809). Вариант, разработанный TSC для и продаваемый компанией Smoke Signal Broadcasting в Калифорнии, аналогичным образом использовал двусвязные списки.

Операционная система TSS/360, разработанная IBM для компьютеров System 360/370, использовала двусвязный список для каталога своей файловой системы. Структура каталогов была аналогична Unix, где каталог мог содержать файлы и другие каталоги и расширяться на любую глубину.

Основные понятия и номенклатура

Каждую запись связанного списка часто называют «элементом» или « узлом ».

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

«Голова» списка — это его первый узел. «Хвост» списка может относиться либо к остальной части списка после головы, либо к последнему узлу в списке. В Лиспе и некоторых производных языках следующий узел может называться « cdr » (произносится /'kʊd.əɹ/ ) списка, а полезные данные головного узла могут называться «автомобилем».

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

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

Односвязный список, узлы которого содержат два поля: целочисленное значение (данные) и ссылку на следующий узел.

Следующий код языка C демонстрирует, как добавить новый узел со «значением» в конец односвязного списка:

// Each node in a linked list is a structure. The head node is the first node in the list.

Node *addNodeToTail(Node *head, int value) {
    // declare Node pointer and initialize to point to the new Node (i.e., it will have the new Node's memory address) being added to the end of the list.
    Node *temp  = malloc(sizeof *temp); /// 'malloc' in stdlib.
    temp->value = value; // Add data to the value field of the new Node.
    temp->next  = NULL; // initialize invalid links to nil.
    
    if (head == NULL) {
        head = temp;     // If the linked list is empty (i.e., the head node pointer is a null pointer), then have the head node pointer point to the new Node.
    }
    else {
        Node *p = head;   // Assign the head node pointer to the Node pointer 'p'.
        while (p->next != NULL) {
            p = p->next;    // Traverse the list until p is the last Node. The last Node always points to NULL.
        }
        p->next = temp; // Make the previously last Node point to the new Node.
    }
    
    return head;    // Return the head node pointer.
}

Двусвязный список

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

В «двусвязном списке» каждый узел содержит, помимо ссылки на следующий узел, второе поле ссылки, указывающее на «предыдущий» узел в последовательности. Эти две ссылки могут называться «вперед(-ы») и «назад» или «следующий» и «предыдущий» («предыдущий»).

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

Метод, известный как XOR-связывание, позволяет реализовать двусвязный список с использованием одного поля ссылки в каждом узле. Однако этот метод требует возможности выполнять битовые операции с адресами и поэтому может быть недоступен в некоторых языках высокого уровня.

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

Многосвязный список

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

Круговой связанный список

В последнем узле связанного списка поле ссылки часто содержит нулевую ссылку, для указания отсутствия дальнейших узлов используется специальное значение. Менее распространенное соглашение — указать на первый узел списка; в этом случае список называется «круговым» или «циклически связанным»; в противном случае его называют «открытым» или «линейным». Это список , в котором указатель последнего узла указывает на первый узел (т. е. указатель «следующей ссылки» последнего узла имеет адрес памяти первого узла).

Круговой связанный список

В случае циклического двусвязного списка первый узел также указывает на последний узел списка.

Дозорные узлы

Основная статья: Узел Sentinel

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

Пустые списки

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

Хэш-связывание

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

Список дескрипторов

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

Объединение альтернатив

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

Компромиссы

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

Связанные списки и динамические массивы

Сравнение структур данных списка

	Пик (индекс)	Изменить (вставить или удалить) в…			Лишнее пространство, средний
		Начало	Конец	Середина
Связанный список	Θ( п )	Я(1)	Θ(1) — известный конечный элемент; Θ( n ), неизвестный конечный элемент	Θ( п )	Θ( п )
Множество	Я(1)	—	—	—	0
Динамический массив	Я(1)	Θ( п )	Θ(1) амортизировано	Θ( п )	Θ( п )
Сбалансированное дерево	Θ(логарифм n)	Θ(логарифм n)	Θ(логарифм n )	Θ(логарифм n )	Θ( п )
произвольного доступа Список	Θ(логарифм n)	Я(1)	—	—	Θ( п )
Дерево хешированного массива	Я(1)	Θ( п )	Θ(1) амортизировано	Θ( п )	Θ(√ п )

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

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

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

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

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

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

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

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

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

Односвязные линейные списки по сравнению с другими списками

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

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

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

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

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

Двойная связь против одинарной связи

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

Круговая связь против линейной связи

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

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

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

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

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

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

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

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

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

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

Операции со связанным списком

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

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

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

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

record Node
{
    data; // The data being stored in the node
    Node next // A reference to the next node, null for last node
}

record List
{
    Node firstNode // points to first node of list; null for empty list
}

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

node := list.firstNode
while node not null
    (do something with node.data)
    node := node.next

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

Схема вставки узла в односвязный список

function insertAfter(Node node, Node newNode) // insert newNode after node
    newNode.next := node.next
    node.next    := newNode

Для вставки в начало списка требуется отдельная функция. Для этого необходимо обновить firstNode .

function insertBeginning(List list, Node newNode) // insert node before current first node
    newNode.next   := list.firstNode
    list.firstNode := newNode

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

Схема удаления узла из односвязного списка

function removeAfter(Node node) // remove node past this one
    obsoleteNode := node.next
    node.next := node.next.next
    destroy obsoleteNode

function removeBeginning(List list) // remove first node
    obsoleteNode := list.firstNode
    list.firstNode := list.firstNode.next // point past deleted node
    destroy obsoleteNode

Обратите внимание, что removeBeginning() наборы list.firstNode к null при удалении последнего узла в списке.

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

Добавление одного связанного списка к другому может быть неэффективным, если только ссылка на хвост не сохраняется как часть структуры List, поскольку мы должны пройти весь первый список, чтобы найти хвост, а затем добавить к нему второй список. Таким образом, если каждый из двух линейно связанных списков имеет длину $n$, добавление списка имеет асимптотическую временную сложность $O(n)$. В семействе языков Lisp добавление списка обеспечивается функцией append процедура.

Многие особые случаи операций со связанным списком можно устранить, включив фиктивный элемент в начале списка. Это гарантирует отсутствие особых случаев в начале списка и отображает оба insertBeginning() и removeBeginning() ненужно, т. е. каждый элемент или узел находится рядом с другим узлом (даже первый узел находится рядом с фиктивным узлом). В этом случае первые полезные данные в списке будут находиться по адресу list.firstNode.next.

Циклически связанный список

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

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

Оба типа циклически связанных списков выигрывают от возможности проходить весь список, начиная с любого заданного узла. Это часто позволяет нам избежать хранения firstNode и LastNode , хотя, если список может быть пустым, нам нужно специальное представление для пустого списка, например, переменная LastNode, которая указывает на некоторый узел в списке или имеет значение NULL , если он пуст; мы используем здесь такой последний узел . Такое представление значительно упрощает добавление и удаление узлов с непустым списком, но тогда пустые списки представляют собой особый случай.

Алгоритмы

Предполагая, что someNode — это некоторый узел в непустом циклическом односвязном списке, этот код выполняет итерацию по этому списку, начиная с someNode :

function iterate(someNode)
    if someNode ≠ null
        node := someNode
    do
        do something with node.value
        node := node.next
    while node ≠ someNode

Обратите внимание, что проверка « while node ≠ someNode» должна находиться в конце цикла. Если тест был перенесен в начало цикла, процедура завершится неудачно, если в списке будет только один узел.

Эта функция вставляет узел «newNode» в циклический связанный список после заданного узла «node». Если «узел» равен нулю, предполагается, что список пуст.

function insertAfter(Node node, Node newNode)
    if node = null    // assume list is empty
        newNode.next := newNode
    else
        newNode.next := node.next
        node.next := newNode
    update lastNode variable if necessary

Предположим, что «L» — переменная, указывающая на последний узел циклического связанного списка (или значение null, если список пуст). Чтобы добавить «newNode» в конец списка, можно сделать

insertAfter(L, newNode)
L := newNode

Чтобы вставить «newNode» в начало списка, можно сделать

insertAfter(L, newNode)
if L = null
    L := newNode

Эта функция вставляет значение «newVal» перед данным узлом «node» за время O(1). Мы создаем новый узел между «узлом» и следующим узлом, а затем помещаем значение «узла» в этот новый узел и помещаем «newVal» в «узел». Таким образом, односвязный циклически связанный список только с переменной firstNode может вставляться как вперед, так и назад за время O(1).

function insertBefore(Node node, newVal)
    if node = null    // assume list is empty
        newNode := new Node(data:=newVal, next:=newNode)
    else
        newNode := new Node(data:=node.data, next:=node.next)
        node.data := newVal
        node.next := newNode
    update firstNode variable if necessary

Эта функция удаляет ненулевой узел из списка размером больше 1 за время O(1). узла Он копирует данные из следующего узла в узел, а затем устанавливает указатель следующего для пропуска следующего узла.

function remove(Node node)
    if node ≠ null and size of list > 1
        removedData := node.data
        node.data := node.next.data
        node.next = node.next.next
        return removedData

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

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

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

record Entry {
    integer next; // index of next entry in array
    integer prev; // previous entry (if double-linked)
    string name;
    real balance;
}

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

integer listHead
Entry Records[1000]

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

Индекс	Следующий	Предыдущий	Имя	Баланс
0	1	4	Джонс, Джон	123.45
1	−1	0	Смит, Джозеф	234.56
2 (заголовок списка)	4	−1	Адамс, Адам	0.00
3			Не обращай внимания, Игнатий.	999.99
4	0	2	Другая, Анита	876.54
5
6
7

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

Следующий код будет проходить по списку и отображать имена и баланс счета:

i := listHead
while i ≥ 0 // loop through the list
    print i, Records[i].name, Records[i].balance // print entry
    i := Records[i].next

К преимуществам такого подхода при выборе можно отнести:

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

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

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

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

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

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

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

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

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

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

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

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

Пример внутреннего и внешнего хранилища

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

record member { // member of a family
    member next;
    string firstName;
    integer age;
}
record family { // the family itself
    family next;
    string lastName;
    string address;
    member members // head of list of members of this family
}

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

aFamily := Families // start at head of families list
while aFamily ≠ null // loop through list of families
    print information about family
    aMember := aFamily.members // get head of list of this family's members
    while aMember ≠ null // loop through list of members
        print information about member
        aMember := aMember.next
    aFamily := aFamily.next

Используя внешнее хранилище, мы создадим следующие структуры:

record node { // generic link structure
    node next;
    pointer data // generic pointer for data at node
}
record member { // structure for family member
    string firstName;
    integer age
}
record family { // structure for family
    string lastName;
    string address;
    node members // head of list of members of this family
}

Чтобы распечатать полный список семей и их членов, используя внешнее хранилище, мы могли бы написать:

famNode := Families // start at head of families list
while famNode ≠ null // loop through list of families
    aFamily := (family) famNode.data // extract family from node
    print information about family
    memNode := aFamily.members // get list of family members
    while memNode ≠ null // loop through list of members
        aMember := (member)memNode.data // extract member from node
        print information about member
        memNode := memNode.next
    famNode := famNode.next

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Дальнейшее чтение

• Хуан, Ангел (2006). «Глава 20 – Структуры данных; ID06 – ПРОГРАММИРОВАНИЕ с использованием JAVA (слайд-часть книги Кей С. Хорстманна «Большая Java»)» (PDF) . п. 3. Архивировано из оригинала (PDF) 6 января 2012 г. Проверено 10 июля 2011 г.
• Блэк, Пол Э. (16 августа 2004 г.). Питерс, Вреда; Блэк, Пол Э. (ред.). «связанный список» . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий . Проверено 14 декабря 2004 г.
• Антонакос, Джеймс Л.; Мэнсфилд, Кеннет С. младший (1999). Практические структуры данных с использованием C/C++ . Прентис-Холл. стр. 165–190 . ISBN  0-13-280843-9 .
• Коллинз, Уильям Дж. (2005) [2002]. Структуры данных и платформа коллекций Java . Нью-Йорк: МакГроу Хилл. стр. 239–303. ISBN  0-07-282379-8 .
• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стоун, Клиффорд (2003). Введение в алгоритмы . С Прессой. стр. 205–213, 501–505. ISBN  0-262-03293-7 .
• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001). «10.2: Связанные списки». Введение в алгоритмы (2-е изд.). МТИ Пресс. стр. 204–209. ISBN  0-262-03293-7 .
• Грин, Берт Ф. младший (1961). «Компьютерные языки для манипулирования символами». IRE Transactions по человеческому фактору в электронике (2): 3–8. дои : 10.1109/THFE2.1961.4503292 .
• Маккарти, Джон (1960). «Рекурсивные функции символьных выражений и их машинное вычисление, часть I» . Коммуникации АКМ . 3 (4): 184. дои : 10.1145/367177.367199 . S2CID   1489409 .
• Кнут, Дональд (1997). «2.2.3-2.2.5». Фундаментальные алгоритмы (3-е изд.). Аддисон-Уэсли. стр. 254–298. ISBN  0-201-89683-4 .
• Ньюэлл, Аллен ; Шоу, ФК (1957). «Программирование логической теоретической машины». Материалы Западной объединенной компьютерной конференции : 230–240.
• Парланте, Ник (2001). «Основы связанных списков» (PDF) . Стэнфордский университет . Проверено 21 сентября 2009 г.
• Седжвик, Роберт (1998). Алгоритмы в C. Эддисон Уэсли. стр. 90–109 . ISBN  0-201-31452-5 .
• Шаффер, Клиффорд А. (1998). Практическое введение в структуры данных и анализ алгоритмов . Нью-Джерси: Прентис Холл. стр. 77–102. ISBN  0-13-660911-2 .
• Уилкс, Морис Винсент (1964). «Эксперимент с самокомпилируемым компилятором для простого языка обработки списков». Ежегодный обзор автоматического программирования . 4 (1). Пергамон Пресс: 1. doi : 10.1016/0066-4138(64)90013-8 .
• Уилкс, Морис Винсент (1964). «Списки и почему они полезны». Доходы Национальной конференции ACM, Филадельфия, 1964 г. (P – 64). АКМ: F1–1.
• Шанмугасундарам, Кулеш (4 апреля 2005 г.). «Описание связанного списка ядра Linux» . Архивировано из оригинала 25 сентября 2009 г. Проверено 21 сентября 2009 г.

Внешние ссылки

• Описание из Словаря алгоритмов и структур данных.
• Введение в связанные списки , Библиотека компьютерных наук Стэнфордского университета
• Проблемы связанных списков , Библиотека компьютерных наук Стэнфордского университета
• Структуры открытых данных. Глава 3. Связанные списки , Пэт Морин
• Патент на идею наличия узлов, одновременно находящихся в нескольких связанных списках (обратите внимание, что этот метод широко использовался в течение многих десятилетий до того, как был выдан патент).
• Реализация односвязного списка в C
• Реализация односвязного списка в C++.
• Реализация двусвязного списка в C
• Реализация двусвязного списка в C++.