В информатике связанный список — это линейный набор элементов данных, порядок которых не определяется их физическим размещением в памяти. Вместо этого каждый элемент указывает на следующий. Это структура данных , состоящая из набора узлов , которые вместе представляют последовательность . В своей самой простой форме каждый узел содержит данные и ссылку (другими словами, ссылку ) на следующий узел в последовательности. Эта структура позволяет эффективно вставлять или удалять элементы из любой позиции последовательности во время итерации. В более сложных вариантах добавляются дополнительные ссылки, позволяющие более эффективно вставлять или удалять узлы в произвольных позициях. Недостатком связанных списков является то, что время доступа к данным линейно зависит от количества узлов в списке. Поскольку узлы последовательно связаны, доступ к любому узлу требует предварительного доступа к предыдущему узлу (что создает трудности при конвейерной обработке ). Более быстрый доступ, такой как произвольный доступ, невозможен. Массивы имеют лучшую локальность кэша по сравнению со связанными списками.
Связанные списки являются одними из самых простых и распространенных структур данных. Их можно использовать для реализации нескольких других распространенных абстрактных типов данных , включая списки , стеки , очереди , ассоциативные массивы и 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 , в котором предлагалось использовать связанные списки в связанных хеш-таблицах. [1]
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 демонстрирует, как добавить новый узел со «значением» в конец односвязного списка:
// Каждый узел связанного списка является структурой. Головной узел — это первый узел в списке.Node * addNodeToTail ( Node * head , int value ) { // объявляем указатель узла и инициализируем его, чтобы он указывал на новый узел (т. е. он будет иметь адрес памяти нового узла), добавляемый в конец списка. Узел * temp = malloc ( sizeof * temp ); /// 'malloc' в stdlib. температура -> значение = значение ; // Добавляем данные в поле значения нового узла Node. температура -> следующий = NULL ; // инициализируем недействительные ссылки равными нулю. если ( голова == NULL ) { голова = температура ; // Если связанный список пуст (т. е. указатель головного узла является нулевым указателем), тогда указатель головного узла должен указывать на новый Node. } еще { Узел * p = голова ; // Назначаем указатель головного узла указателю узла 'p'. while ( p -> следующий != NULL ) { р = р -> следующий ; // Проходим по списку, пока p не станет последним узлом. Последний узел всегда указывает на NULL. } р -> следующий = темп ; // Сделать предыдущий последний узел точкой нового узла. } вернуть голову ; // Возвращаем указатель головного узла. }В «двусвязном списке» каждый узел содержит, помимо ссылки на следующий узел, второе поле ссылки, указывающее на «предыдущий» узел в последовательности. Эти две ссылки могут называться «вперед(-ы») и «назад» или «следующий» и «предыдущий» («предыдущий»).
Метод, известный как XOR-связывание, позволяет реализовать двусвязный список с использованием одного поля ссылки в каждом узле. Однако этот метод требует возможности выполнять битовые операции с адресами и поэтому может быть недоступен в некоторых языках высокого уровня.
Многие современные операционные системы используют двусвязные списки для хранения ссылок на активные процессы, потоки и другие динамические объекты. [2] Распространенной стратегией, позволяющей руткитам избежать обнаружения, является отсоединение себя от этих списков. [3]
В «многосвязном списке» каждый узел содержит два или более полей связи, причем каждое поле используется для соединения одного и того же набора данных, расположенных в разном порядке (например, по имени, по отделу, по дате рождения и т. д.). . Хотя двусвязный список можно рассматривать как частный случай многосвязного списка, тот факт, что два и более порядка противоположны друг другу, приводит к более простым и эффективным алгоритмам, поэтому их обычно рассматривают как отдельный случай.
В последнем узле связанного списка поле ссылки часто содержит нулевую ссылку, для указания отсутствия дальнейших узлов используется специальное значение. Менее распространенное соглашение — указать на первый узел списка; в этом случае список называется «круговым» или «циклически связанным»; в противном случае его называют «открытым» или «линейным». Это список , в котором указатель последнего узла указывает на первый узел (т. е. указатель «следующей ссылки» последнего узла имеет адрес памяти первого узла).
В случае циклического двусвязного списка первый узел также указывает на последний узел списка.
В некоторых реализациях дополнительный «сторожевой» или «фиктивный» узел может быть добавлен перед первой записью данных или после последней. Это соглашение упрощает и ускоряет некоторые алгоритмы обработки списков, гарантируя, что все ссылки могут быть безопасно разыменованы и что каждый список (даже тот, который не содержит элементов данных) всегда имеет «первый» и «последний» узел.
Пустой список — это список, который не содержит записей данных. Обычно это то же самое, что сказать, что у него ноль узлов. Если используются дозорные узлы, список обычно считается пустым, если в нем есть только дозорные узлы.
Поля ссылок не обязательно должны быть физически частью узлов. Если записи данных хранятся в массиве и на них ссылаются их индексы, поле ссылки может храниться в отдельном массиве с теми же индексами, что и записи данных.
Поскольку ссылка на первый узел дает доступ ко всему списку, эту ссылку часто называют «адресом», «указателем» или «дескриптором» списка. Алгоритмы, управляющие связанными списками, обычно получают такие дескрипторы для входных списков и возвращают дескрипторы в результирующие списки. Фактически, в контексте таких алгоритмов слово «список» часто означает «дескриптор списка». Однако в некоторых ситуациях может быть удобно обращаться к списку с помощью дескриптора, состоящего из двух ссылок, указывающих на его первый и последний узлы.
Перечисленные выше альтернативы можно произвольно комбинировать практически любым способом, поэтому можно иметь циклические двусвязные списки без дозорных, циклические односвязные списки с дозорными и т. д.
Как и большинство вариантов компьютерного программирования и дизайна, ни один метод не подходит для всех обстоятельств. Структура данных связанного списка может хорошо работать в одном случае, но вызывать проблемы в другом. Это список некоторых распространенных компромиссов, связанных со структурами связанных списков.
Динамический массив — это структура данных, которая размещает все элементы в памяти последовательно и ведет подсчет текущего количества элементов. Если пространство, зарезервированное для динамического массива, превышено, оно перераспределяется и (возможно) копируется, что является дорогостоящей операцией.
Связанные списки имеют ряд преимуществ перед динамическими массивами. Вставка или удаление элемента в определенной точке списка, при условии, что мы уже проиндексировали указатель на узел (перед тем, который нужно удалить, или перед точкой вставки), является операцией с постоянным временем (иначе без этого по ссылке это O(n)), тогда как вставка в динамический массив в случайные места потребует перемещения в среднем половины элементов, а в худшем случае - всех элементов. Хотя можно «удалить» элемент из массива за постоянное время, каким-то образом пометив его слот как «свободный», это вызывает фрагментацию , затрудняющую выполнение итерации.
Более того, в связанный список можно вставить произвольное количество элементов, ограниченное только общим объемом доступной памяти; в то время как динамический массив в конечном итоге заполнит свою базовую структуру данных массива и его придется перераспределить — дорогостоящая операция, которая может быть даже невозможна, если память фрагментирована, хотя стоимость перераспределения может быть усреднена по вставкам, а стоимость перераспределения может быть усреднена по вставкам, а стоимость вставка из-за перераспределения все равно будет амортизироваться O (1). Это помогает при добавлении элементов в конец массива, но вставка в средние позиции (или удаление из них) по-прежнему сопряжена с непомерно высокими затратами из-за перемещения данных для поддержания непрерывности. Массив, из которого удалено много элементов, возможно, также придется изменить размер, чтобы не тратить слишком много места.
С другой стороны, динамические массивы (а также структуры данных массива фиксированного размера) допускают произвольный доступ с постоянным временем , тогда как связанные списки допускают только последовательный доступ к элементам. Фактически, односвязные списки можно легко перемещать только в одном направлении. Это делает связанные списки непригодными для приложений, в которых полезно быстро искать элемент по его индексу, таких как пирамидальная сортировка . Последовательный доступ к массивам и динамическим массивам на многих машинах также быстрее, чем к связанным спискам, поскольку они имеют оптимальную локальность ссылок и, таким образом, эффективно используют кэширование данных.
Еще одним недостатком связанных списков является дополнительное хранилище, необходимое для ссылок, что часто делает их непрактичными для списков небольших элементов данных, таких как символы или логические значения , поскольку накладные расходы на хранилище для ссылок могут в два или более раза превышать размер списка. данные. Напротив, динамический массив требует только места для самих данных (и очень небольшого количества управляющих данных). [примечание 1] Выделение памяти отдельно для каждого нового элемента также может быть медленным, а с наивным распределителем - расточительным. Эта проблема обычно решается с помощью пулов памяти .
Некоторые гибридные решения пытаются объединить преимущества двух представлений. Развернутые связанные списки хранят несколько элементов в каждом узле списка, что увеличивает производительность кэша и одновременно снижает нагрузку на память для ссылок. Кодирование CDR также выполняет обе эти задачи, заменяя ссылки фактическими данными, на которые ссылаются, которые выходят за пределы ссылающейся записи.
Хорошим примером, показывающим плюсы и минусы использования динамических массивов по сравнению со связанными списками, является реализация программы, решающей проблему Джозефуса . Задача Иосифа Флавия — это метод выборов, при котором группа людей стоит в кругу. Начиная с заранее определенного человека, можно сосчитать по кругу n раз. Как только будет достигнут n- й человек, следует удалить его из круга и попросить участников замкнуть круг. Процесс повторяется до тех пор, пока не останется только один человек. Этот человек побеждает на выборах. Это показывает сильные и слабые стороны связанного списка по сравнению с динамическим массивом, потому что, если людей рассматривать как связанные узлы в циклическом связанном списке, это показывает, насколько легко связанный список может удалять узлы (поскольку для этого достаточно всего лишь переставьте ссылки на разные узлы). Однако связанный список будет неспособен найти следующего человека, которого нужно удалить, и ему придется искать по списку, пока не будет найден этот человек. С другой стороны, динамический массив будет плохо удалять узлы (или элементы), поскольку он не может удалить один узел без индивидуального сдвига всех элементов вверх по списку на один. Однако найти n- го человека в круге исключительно легко , напрямую ссылаясь на него по его положению в массиве.
Проблема ранжирования списка касается эффективного преобразования представления связанного списка в массив. Хотя решение этой задачи с помощью параллельного алгоритма тривиально для обычного компьютера, оно сложно и стало предметом большого количества исследований.
Сбалансированное дерево имеет те же шаблоны доступа к памяти и накладные расходы на пространство, что и связный список, но при этом обеспечивает гораздо более эффективную индексацию, затрачивая время O(log n) вместо O(n) для произвольного доступа. Однако операции вставки и удаления обходятся дороже из-за затрат на манипуляции с деревом для поддержания баланса. Существуют схемы автоматического поддержания деревьев в сбалансированном состоянии: деревья AVL или красно-черные деревья .
Хотя двусвязные и циклические списки имеют преимущества перед односвязными линейными списками, линейные списки обладают некоторыми преимуществами, которые делают их предпочтительными в некоторых ситуациях.
Односвязный линейный список — это рекурсивная структура данных, поскольку он содержит указатель на меньший объект того же типа. По этой причине многие операции с односвязными линейными списками (например, объединение двух списков или перечисление элементов в обратном порядке) часто имеют очень простые рекурсивные алгоритмы, намного более простые, чем любое решение с использованием итеративных команд . Хотя эти рекурсивные решения можно адаптировать для двусвязных и циклически связанных списков, для этих процедур обычно требуются дополнительные аргументы и более сложные базовые случаи.
Линейные односвязные списки также допускают совместное использование хвостов — использование общей конечной части подсписка в качестве конечной части двух разных списков. В частности, если в начало списка добавляется новый узел, прежний список остается доступным как хвост нового — простой пример постоянной структуры данных . Опять же, это не относится к другим вариантам: узел никогда не может принадлежать двум разным кольцевым или двусвязным спискам.
В частности, конечные контрольные узлы могут использоваться совместно в односвязных нециклических списках. Один и тот же конечный контрольный узел может использоваться для каждого такого списка. В Lisp , например, каждый правильный список заканчивается ссылкой на специальный узел, обозначаемый nilили ().
Преимущества необычных вариантов часто ограничиваются сложностью алгоритмов, а не их эффективностью. В частности, циклический список обычно можно имитировать линейным списком вместе с двумя переменными, указывающими на первый и последний узлы, без каких-либо дополнительных затрат.
Двусвязные списки требуют больше места на узел (если только не используется XOR-связывание ), а их элементарные операции обходятся дороже; но ими часто легче манипулировать, поскольку они обеспечивают быстрый и простой последовательный доступ к списку в обоих направлениях. В двусвязном списке можно вставить или удалить узел за постоянное количество операций, зная только адрес этого узла. Чтобы сделать то же самое в односвязном списке, необходимо иметь адрес указателя на этот узел, который является либо дескриптором всего списка (в случае первого узла), либо полем связи в предыдущем узле. Некоторые алгоритмы требуют доступа в обоих направлениях. С другой стороны, двусвязные списки не допускают совместного использования хвостов и не могут использоваться в качестве постоянных структур данных .
Циклически связанный список может быть естественным вариантом для представления массивов, которые имеют естественную круглую форму, например, углы многоугольника , пул буферов , которые используются и освобождаются в порядке FIFO («первым пришел — первым вышел»), или набор процессы, которые должны быть разделены по времени в циклическом порядке . В этих приложениях указатель на любой узел служит дескриптором всего списка.
В циклическом списке указатель на последний узел обеспечивает легкий доступ и к первому узлу, перейдя по одной ссылке. Таким образом, в приложениях, требующих доступа к обоим концам списка (например, при реализации очереди), циклическая структура позволяет обрабатывать структуру одним указателем вместо двух.
Циклический список можно разделить на два циклических списка за постоянное время, указав адреса последнего узла каждой части. Операция заключается в замене содержимого полей ссылок этих двух узлов. Применение одной и той же операции к любым двум узлам в двух разных списках объединяет два списка в один. Это свойство значительно упрощает некоторые алгоритмы и структуры данных, такие как четырехгранное ребро и ребро грани.
Простейшим представлением пустого циклического списка (если это имеет смысл) является нулевой указатель, указывающий, что в списке нет узлов. Без этого выбора многим алгоритмам приходится проверять этот особый случай и обрабатывать его отдельно. Напротив, использование нуля для обозначения пустого линейного списка более естественно и часто создает меньше особых случаев.
Для некоторых приложений может быть полезно использовать односвязные списки, которые могут быть циклическими и линейными или даже циклическими с линейным начальным сегментом. Алгоритмы поиска или иной работы с ними должны принимать меры предосторожности, чтобы избежать случайного входа в бесконечный цикл. Один из хорошо известных методов заключается в том, чтобы второй указатель перемещался по списку с половиной или вдвое большей скоростью, и если оба указателя встречаются в одном и том же узле, вы знаете, что нашли цикл.
Узел Sentinel может упростить определенные операции со списком, гарантируя, что следующий или предыдущий узлы существуют для каждого элемента и что даже в пустых списках есть хотя бы один узел. Можно также использовать контрольный узел в конце списка с соответствующим полем данных, чтобы исключить некоторые проверки конца списка. Например, при сканировании списка в поисках узла с заданным значением x установка поля данных дозорного в x делает ненужной проверку на конец списка внутри цикла. Другой пример — объединение двух отсортированных списков: если их дозорные поля имеют значения +∞, выбор следующего выходного узла не требует специальной обработки для пустых списков.
Однако дозорные узлы занимают дополнительное пространство (особенно в приложениях, использующих множество коротких списков) и могут усложнять другие операции (например, создание нового пустого списка).
Однако если циклический список используется просто для имитации линейного списка, можно избежать некоторой сложности этой сложности, добавив один контрольный узел в каждый список между последним и первым узлами данных. Согласно этому соглашению, пустой список состоит только из сторожевого узла, указывающего на себя через ссылку следующего узла. В этом случае дескриптор списка должен быть указателем на последний узел данных перед дозорным, если список не пуст; или самому дозорному, если список пуст.
Тот же трюк можно использовать для упрощения обработки двусвязного линейного списка, превратив его в циклический двусвязный список с одним контрольным узлом. Однако в этом случае дескриптор должен быть единственным указателем на сам фиктивный узел. [8]
При манипулировании связанными списками на месте необходимо соблюдать осторожность, чтобы не использовать значения, которые вы признали недействительными в предыдущих назначениях. Это делает алгоритмы вставки или удаления узлов связанного списка несколько тонкими. В этом разделе представлен псевдокод для добавления или удаления узлов из одинарных, двусвязных и циклически связанных списков на месте. Всюду мы будем использовать значение null для обозначения маркера конца списка или дозорного , который может быть реализован несколькими способами.
Наша структура данных узла будет иметь два поля. Мы также сохраняем переменную firstNode , которая всегда указывает на первый узел в списке или имеет значение null для пустого списка.
запись узла{ данные; // Данные сохраняются в узле Node next // Ссылка [2] на следующий узел, нулевая для последнего узла} список записей{ Node firstNode // указывает на первый узел списка; ноль для пустого списка}Обход односвязного списка прост, начиная с первого узла и следуя по каждой следующей ссылке, пока не дойдем до конца:
node := list.firstNode, пока узел не равен нулю (сделайте что-нибудь с node.data) узел := узел.следующий
Следующий код вставляет узел после существующего узла в односвязном списке. На схеме показано, как это работает. Вставка узла перед существующим не может быть выполнена напрямую; вместо этого необходимо отслеживать предыдущий узел и вставлять узел после него.
function InsertAfter( Node node, Node newNode) // вставляем новыйNode после узла новыйУзел.следующий := узел.следующий node.next := новыйузел
Для вставки в начало списка требуется отдельная функция. Для этого необходимо обновить firstNode .
function InsertBeginning( List list, Node newNode) // вставляем узел перед текущим первым узлом newNode.next := list.firstNode list.firstNode := новыйNode
Точно так же у нас есть функции для удаления узла после заданного узла и для удаления узла из начала списка. Диаграмма демонстрирует первое. Чтобы найти и удалить тот или иной узел, необходимо снова отслеживать предыдущий элемент.
function removeAfter( Node node) // удаляем узел за этим устаревшийNode:= node.next узел.следующий:= узел.следующий.следующий уничтожить устаревший узел
function removeBeginning( List list) // удаляем первый узел устаревшийNode:= list.firstNode list.firstNode := list.firstNode.next // точка за удаленным узлом уничтожить устаревший узел
Обратите внимание, что значение removeBeginning()устанавливается при удалении последнего узла в списке.list.firstNodenull
Поскольку мы не можем выполнять итерацию в обратном направлении, эффективные операции insertBeforeor removeBeforeневозможны. Вставка в список перед конкретным узлом требует обхода списка, что в худшем случае будет иметь время выполнения O(n).
Добавление одного связанного списка к другому может быть неэффективным, если ссылка на хвост не сохраняется как часть структуры List, поскольку мы должны пройти весь первый список, чтобы найти хвост, а затем добавить к нему второй список. Таким образом, если каждый из двух линейно связанных списков имеет длину , добавление списка имеет асимптотическую временную сложность . В семействе языков Lisp добавление списка обеспечивается процедурой .append
Многие особые случаи операций со связанным списком можно устранить, включив фиктивный элемент в начале списка. Это гарантирует отсутствие особых случаев для начала списка и делает оба insertBeginning()элемента removeBeginning()ненужными, т. е. каждый элемент или узел находится рядом с другим узлом (даже первый узел находится рядом с фиктивным узлом). В этом случае первые полезные данные в списке будут находиться по адресу .list.firstNode.next
В циклически связанном списке все узлы связаны в непрерывный круг без использования значения null. Для списков с передней и задней частью (например, очереди) сохраняется ссылка на последний узел списка. Следующий узел после последнего узла является первым узлом. Элементы можно добавлять в конец списка и удалять из начала за постоянное время.
Циклически связанные списки могут быть как одинарными, так и двусвязными.
Оба типа циклически связанных списков выигрывают от возможности проходить весь список, начиная с любого заданного узла. Это часто позволяет нам избежать хранения firstNode и LastNode , хотя, если список может быть пустым, нам нужно специальное представление для пустого списка, например, переменная LastNode , которая указывает на некоторый узел в списке или имеет значение NULL , если он пуст; мы используем здесь такой последний узел . Такое представление значительно упрощает добавление и удаление узлов с непустым списком, но тогда пустые списки представляют собой особый случай.
Предполагая, что someNode — это некоторый узел в непустом циклическом односвязном списке, этот код выполняет итерацию по этому списку, начиная с someNode :
функция итерации (someNode), если someNode ≠ null узел:= некоторыйNode делать сделайте что-нибудь с node.value узел := узел.следующий в то время как узел ≠ someNode
Обратите внимание, что проверка « while node ≠ someNode» должна находиться в конце цикла. Если тест был перенесен в начало цикла, процедура завершится неудачно, если в списке будет только один узел.
Эта функция вставляет узел «newNode» в циклический связанный список после заданного узла «node». Если «узел» равен нулю, предполагается, что список пуст.
function InsertAfter( Node node, Node newNode) if node = null // предполагаем, что список пуст новыйУзел.следующий := новыйУзел еще новыйУзел.следующий := узел.следующий node.next := новыйузелпри необходимости обновите переменную LastNode
Предположим, что «L» — переменная, указывающая на последний узел циклического связанного списка (или значение null, если список пуст). Чтобы добавить «newNode» в конец списка, можно сделать
InsertAfter (L, новый узел)L := новыйузел
Чтобы вставить «newNode» в начало списка, можно сделать
InsertAfter(L, newNode), если L = ноль L := новыйузел
Эта функция вставляет значение «newVal» перед данным узлом «node» за время O(1). Мы создаем новый узел между «узлом» и следующим узлом, а затем помещаем значение «узла» в этот новый узел и помещаем «newVal» в «узел». Таким образом, односвязный циклически связанный список только с переменной firstNode может вставляться как вперед, так и назад за время O(1).
function InsertBefore( Node node, newVal) if node = null // предположим, что список пуст newNode := новый узел(data:=newVal, next:=newNode) else newNode := новый узел(data:=node.data, next:=node.next) node.data:= новоеVal node.next := новыйузелпри необходимости обновите переменную firstNode
Эта функция удаляет ненулевой узел из списка размером больше 1 за время O(1). Он копирует данные из следующего узла в узел, а затем устанавливает указатель следующего узла для пропуска следующего узла.
функция удаления ( узел узла) , если узел ≠ null и размер списка > 1 удаленные данные: = node.data узел.данные:= узел.следующие.данные узел.следующий = узел.следующий.следующий вернуть удаленные данные
Языки, которые не поддерживают ссылки какого-либо типа , все равно могут создавать ссылки, заменяя указатели индексами массива. Подход заключается в том, чтобы сохранить массив записей , где каждая запись имеет целочисленные поля , указывающие индекс следующего (и, возможно, предыдущего) узла в массиве. Не обязательно использовать все узлы массива. Если записи также не поддерживаются, вместо них часто можно использовать параллельные массивы .
В качестве примера рассмотрим следующую запись связанного списка, в которой вместо указателей используются массивы:
запись Entry { целое число следующее; // индекс следующей записи в массиве целочисленное предыдущее; // предыдущая запись (если двойная связь) имя строки ; реальный баланс;}Связный список можно построить, создав массив этих структур и целочисленную переменную для хранения индекса первого элемента.
целое число listHead Entry Records[1000]
Ссылки между элементами формируются путем помещения индекса массива следующей (или предыдущей) ячейки в поле «Следующий» или «Предыдущий» внутри данного элемента. Например:
В приведенном выше примере ListHeadбудет установлено значение 2 — местоположение первой записи в списке. Обратите внимание, что записи 3 и 5–7 не являются частью списка. Эти ячейки доступны для любых дополнений к списку. Создав ListFreeцелочисленную переменную, можно создать свободный список для отслеживания доступных ячеек. Если все записи используются, размер массива придется увеличить или удалить некоторые элементы, прежде чем новые записи смогут быть сохранены в списке.
Следующий код будет проходить по списку и отображать имена и баланс счета:
i := listHead while i ≥ 0 // цикл по списку print i, Records[i].name, Records[i].balance // печать записи я := Записи[i].следующий
К преимуществам такого подхода при выборе можно отнести:
Однако у этого подхода есть один главный недостаток: он создает и управляет частным пространством памяти для своих узлов. Это приводит к следующим проблемам:
По этим причинам этот подход в основном используется для языков, не поддерживающих динамическое выделение памяти. Эти недостатки также смягчаются, если максимальный размер списка известен на момент создания массива.
Многие языки программирования, такие как Lisp и Scheme , имеют встроенные односвязные списки. Во многих функциональных языках эти списки состоят из узлов, каждый из которых называется cons или cons-ячейкой . Cons имеет два поля: car — ссылка на данные для этого узла и cdr — ссылка на следующий узел. Хотя cons-ячейки можно использовать для построения других структур данных, это их основная цель.
В языках, поддерживающих абстрактные типы данных или шаблоны, доступны ADT или шаблоны связанных списков для создания связанных списков. В других языках связанные списки обычно создаются с использованием ссылок и записей .
При построении связанного списка приходится выбирать, хранить ли данные списка непосредственно в узлах связанного списка, называемом внутренним хранилищем , или просто хранить ссылку на данные, называемое внешним хранилищем . Преимущество внутреннего хранилища заключается в том, что он делает доступ к данным более эффективным, требует меньше места для хранения в целом, обеспечивает лучшую локальность ссылок и упрощает управление памятью для списка (его данные выделяются и освобождаются одновременно с узлами списка).
С другой стороны, внешнее хранилище имеет то преимущество, что оно является более универсальным, поскольку для связанного списка можно использовать одну и ту же структуру данных и машинный код независимо от размера данных. Это также позволяет легко размещать одни и те же данные в нескольких связанных списках. Хотя при использовании внутреннего хранилища одни и те же данные можно поместить в несколько списков путем включения нескольких ссылок на следующий узел в структуру данных узла, в этом случае потребуется создать отдельные процедуры для добавления или удаления ячеек на основе каждого поля. Можно создавать дополнительные связанные списки элементов, которые используют внутреннюю память, используя внешнее хранилище, а ячейки дополнительных связанных списков сохраняют ссылки на узлы связанного списка, содержащие данные.
В общем, если набор структур данных необходимо включить в связанные списки, лучшим подходом является внешнее хранилище. Если набор структур данных необходимо включить только в один связанный список, то внутреннее хранилище немного лучше, если только не доступен универсальный пакет связанного списка, использующий внешнее хранилище. Аналогично, если разные наборы данных, которые могут храниться в одной и той же структуре данных, должны быть включены в один связанный список, тогда подойдет внутреннее хранилище.
Другой подход, который можно использовать с некоторыми языками, предполагает наличие разных структур данных, но все они имеют начальные поля, включая ссылки на следующее (и предыдущее , если двусвязный список) в одном и том же месте. После определения отдельных структур для каждого типа данных можно определить общую структуру, содержащую минимальный объем данных, общих для всех других структур и содержащихся в верхней части (начале) структур. Затем можно создать общие процедуры, которые используют минимальную структуру для выполнения операций типа связанного списка, но затем отдельные процедуры могут обрабатывать конкретные данные. Этот подход часто используется в процедурах анализа сообщений, когда принимаются сообщения нескольких типов, но все они начинаются с одного и того же набора полей, обычно включая поле для типа сообщения. Общие процедуры используются для добавления новых сообщений в очередь при их получении и удаления их из очереди для обработки сообщения. Поле типа сообщения затем используется для вызова правильной процедуры для обработки сообщения определенного типа.
Предположим, вы хотите создать связанный список семей и их членов. При использовании внутренней памяти структура может выглядеть следующим образом:
запись члена { // член члена семьи следующий; строка FirstName; целочисленный возраст;}запись семейства { // само семейство Family next; строка LastName; адрес строки ; члены- члены // глава списка членов этой семьи}Чтобы распечатать полный список семей и их членов, используя внутреннюю память, мы могли бы написать:
aFamily := Family // начинается с начала списка семейств , while aFamily ≠ null // циклически перебирает список семейств распечатать информацию о семье aMember := aFamily.members // получаем начало списка членов этой семьи while aMember ≠ null // циклически перебираем список членов распечатать информацию об участнике aMember := aMember.next aFamily := aFamily.next
Используя внешнее хранилище, мы создадим следующие структуры:
узел записи { // узел общей структуры ссылки next; данные указателя // общий указатель на данные в узле}запись члена { // структура для члена семейства string firstName; Целочисленный возраст}Record Family { // структура семейства string LastName; адрес строки ; члены узла // глава списка членов этого семейства}Чтобы распечатать полный список семей и их членов, используя внешнее хранилище, мы могли бы написать:
famNode := Families // начинаются с начала списка семейств while famNode ≠ null // циклически просматриваем список семейств aFamily := (family) famNode.data // извлекаем семейство из узла распечатать информацию о семье memNode := aFamily.members // получаем список членов семьи while memNode ≠ null // циклически перебираем список членов aMember := (member)memNode.data // извлекаем члена из узла распечатать информацию об участнике memNode := memNode.next famNode := famNode.next
Обратите внимание, что при использовании внешнего хранилища требуется дополнительный шаг для извлечения записи из узла и приведения ее к соответствующему типу данных. Это связано с тем, что и список семейств, и список членов семейства хранятся в двух связанных списках, использующих одну и ту же структуру данных ( узел ), и в этом языке нет параметрических типов.
Пока количество семейств, к которым может принадлежать член, известно во время компиляции, внутреннее хранилище работает нормально. Однако если члена необходимо включить в произвольное количество семейств, причем конкретное число известно только во время выполнения, потребуется внешнее хранилище.
Поиск определенного элемента в связанном списке, даже если он отсортирован, обычно требует времени O( n ) ( линейный поиск ). Это один из основных недостатков связанных списков по сравнению с другими структурами данных. В дополнение к вариантам, рассмотренным выше, ниже приведены два простых способа сократить время поиска.
В неупорядоченном списке одной простой эвристикой для уменьшения среднего времени поиска является эвристика перемещения вперед , которая просто перемещает элемент в начало списка, как только он будет найден. Эта схема, удобная для создания простых кэшей, гарантирует, что самые недавно использованные элементы будут быстрее найдены снова.
Другой распространенный подход — « индексировать » связанный список с использованием более эффективной внешней структуры данных. Например, можно построить красно-черное дерево или хеш-таблицу , элементы которой являются ссылками на узлы связанного списка. В одном списке можно построить несколько таких индексов. Недостаток заключается в том, что эти индексы, возможно, придется обновлять каждый раз, когда узел добавляется или удаляется (или, по крайней мере, перед повторным использованием этого индекса).
Список произвольного доступа — это список с поддержкой быстрого произвольного доступа для чтения или изменения любого элемента в списке. [9] Одной из возможных реализаций является косой двоичный список произвольного доступа с использованием косой двоичной системы счисления , который включает в себя список деревьев со специальными свойствами; это позволяет выполнять операции head/cons с постоянным временем в худшем случае и произвольный доступ к элементу по индексу с логарифмическим временем в худшем случае. [9] Списки произвольного доступа могут быть реализованы как постоянные структуры данных . [9]
Списки произвольного доступа можно рассматривать как неизменяемые связанные списки, поскольку они также поддерживают одни и те же операции с головкой и хвостом O(1). [9]
Простым расширением списков с произвольным доступом является min-list, который предоставляет дополнительную операцию, которая дает минимальный элемент во всем списке за постоянное время (без [ необходимых пояснений ] сложностей мутации). [9]
И стеки , и очереди часто реализуются с использованием связанных списков и просто ограничивают тип поддерживаемых операций.
Список пропуска — это связанный список, дополненный слоями указателей для быстрого перехода по большому количеству элементов и последующего перехода к следующему слою. Этот процесс продолжается до нижнего уровня, который представляет собой фактический список.
Бинарное дерево можно рассматривать как тип связанного списка, элементы которого сами являются связанными списками одной и той же природы. В результате каждый узел может включать ссылку на первый узел одного или двух других связанных списков, которые вместе со своим содержимым образуют поддеревья ниже этого узла.
Развернутый связанный список — это связанный список, в котором каждый узел содержит массив значений данных. Это приводит к повышению производительности кэша , поскольку большее количество элементов списка находится в памяти подряд, и уменьшению накладных расходов на память, поскольку для каждого элемента списка необходимо хранить меньше метаданных.
В хеш-таблице могут использоваться связанные списки для хранения цепочек элементов, которые хэшируются в одну и ту же позицию в хеш-таблице.
Куча разделяет некоторые свойства упорядочивания связанного списка, но почти всегда реализуется с использованием массива . Вместо ссылок от узла к узлу следующий и предыдущий индексы данных рассчитываются с использованием индекса текущих данных.
Самоорганизующийся список переупорядочивает свои узлы на основе некоторой эвристики, которая сокращает время поиска для получения данных, сохраняя общедоступные узлы в начале списка.
{{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка ){{cite book}}: |work=игнорируется ( помощь )