В информатике связанный список — это линейный набор элементов данных, порядок которых не задается их физическим размещением в памяти. Вместо этого каждый элемент указывает на следующий. Это структура данных, состоящая из набора узлов , которые вместе представляют последовательность . В своей самой простой форме каждый узел содержит данные и ссылку (другими словами, ссылку ) на следующий узел в последовательности. Эта структура позволяет эффективно вставлять или удалять элементы из любой позиции в последовательности во время итерации. Более сложные варианты добавляют дополнительные ссылки, позволяя более эффективно вставлять или удалять узлы в произвольных позициях. Недостатком связанных списков является то, что время доступа к данным линейно по отношению к количеству узлов в списке. Поскольку узлы последовательно связаны, доступ к любому узлу требует предварительного доступа к предыдущему узлу (что создает трудности в конвейеризации ). Более быстрый доступ, такой как случайный доступ, невозможен. Массивы имеют лучшую локальность кэша по сравнению со связанными списками.
Связанные списки являются одними из самых простых и распространенных структур данных. Они могут быть использованы для реализации нескольких других распространенных абстрактных типов данных , включая списки , стеки , очереди , ассоциативные массивы и S-выражения , хотя не редкость реализовать эти структуры данных напрямую, без использования связанного списка в качестве основы.
Главное преимущество связанного списка по сравнению с обычным массивом заключается в том, что элементы списка можно легко вставлять или удалять без перераспределения или реорганизации всей структуры, поскольку элементы данных не нужно хранить непрерывно в памяти или на диске, в то время как реструктуризация массива во время выполнения является гораздо более дорогой операцией. Связанные списки позволяют вставлять и удалять узлы в любой точке списка и позволяют делать это с постоянным числом операций, сохраняя ссылку, предшествующую добавляемой или удаляемой ссылке в памяти во время обхода списка.
С другой стороны, поскольку простые связанные списки сами по себе не допускают произвольного доступа к данным или какой-либо формы эффективной индексации, многие базовые операции, такие как получение последнего узла списка, поиск узла, содержащего заданные данные, или определение места, куда следует вставить новый узел, могут потребовать итерации по большинству или всем элементам списка.
Связанные списки были разработаны в 1955–1956 годах Алленом Ньюэллом , Клиффом Шоу и Гербертом А. Саймоном в корпорации RAND и Университете Карнеги-Меллона в качестве основной структуры данных для их языка обработки информации (IPL). IPL использовался авторами для разработки нескольких ранних программ искусственного интеллекта , включая Logic Theory Machine, General Problem Solver и программу для компьютерных шахмат. Отчеты об их работе появились в IRE Transactions on Information Theory в 1956 году и в нескольких трудах конференций с 1957 по 1959 год, включая Proceedings of the Western Joint Computer Conference в 1957 и 1958 годах и Information Processing (Proceedings of the first UNESCO International Conference on Information Processing) в 1959 году. Теперь уже классическая диаграмма, состоящая из блоков, представляющих узлы списка со стрелками, указывающими на последовательные узлы списка, появляется в «Programming the Logic Theory Machine» Ньюэлла и Шоу в Proc. WJCC, февраль 1957 г. Ньюэлл и Саймон были отмечены премией ACM Turing Award в 1975 г. за «внесение фундаментального вклада в искусственный интеллект, психологию человеческого познания и обработку списков». Проблема машинного перевода для обработки естественного языка привела Виктора Ингве из Массачусетского технологического института (MIT) к использованию связанных списков в качестве структур данных в его языке программирования COMIT для компьютерных исследований в области лингвистики . Отчет об этом языке под названием «Язык программирования для механического перевода» появился в Mechanical Translation в 1958 г. [ необходима ссылка ]
Еще одним ранним упоминанием связанных списков был Ганс Петер Лун , который в январе 1953 года написал внутренний меморандум IBM , в котором предлагалось использовать связанные списки в цепочечных хеш-таблицах. [1]
LISP , сокращение от listprocessor, был создан Джоном Маккарти в 1958 году, когда он работал в Массачусетском технологическом институте, а в 1960 году он опубликовал его проект в статье в Communications of the ACM под названием «Рекурсивные функции символических выражений и их вычисление машиной, часть I». Одной из основных структур данных LISP является связанный список.
К началу 1960-х годов полезность как связанных списков, так и языков, которые используют эти структуры в качестве основного представления данных, была хорошо известна. Берт Грин из лаборатории Линкольна Массачусетского технологического института опубликовал обзорную статью под названием «Компьютерные языки для манипуляции символами» в журнале IRE Transactions on Human Factors in Electronics в марте 1961 года, в которой суммировались преимущества подхода на основе связанных списков. Более поздняя обзорная статья «Сравнение компьютерных языков обработки списков» Боброва и Рафаэля появилась в журнале Communications of the ACM в апреле 1964 года.
Несколько операционных систем, разработанных Technical Systems Consultants (первоначально из West Lafayette Indiana, а позднее из Chapel Hill, North Carolina), использовали односвязные списки в качестве структур файлов. Запись каталога указывала на первый сектор файла, а последующие части файла находились путем перемещения указателей. Системы, использующие эту технику, включали Flex (для процессора Motorola 6800 ), mini-Flex (тот же процессор) и Flex9 (для процессора Motorola 6809). Вариант, разработанный TSC и продаваемый Smoke Signal Broadcasting в Калифорнии, использовал двусвязные списки таким же образом.
Операционная система TSS/360, разработанная IBM для машин System 360/370, использовала двойной связанный список для каталога файловой системы. Структура каталога была похожа на Unix, где каталог мог содержать файлы и другие каталоги и простираться на любую глубину.
Каждую запись связанного списка часто называют «элементом» или « узлом ».
Поле каждого узла, содержащее адрес следующего узла, обычно называется «следующей ссылкой» или «следующим указателем». Остальные поля известны как поля «данных», «информации», «значения», «груза» или «полезной нагрузки».
«Голова» списка — это его первый узел. «Хвост» списка может относиться либо к остальной части списка после головы, либо к последнему узлу в списке. В Lisp и некоторых производных языках следующий узел может называться « cdr » (произносится как /'kʊd.əɹ/ ) списка, в то время как полезная нагрузка головного узла может называться «car».
Односвязные списки содержат узлы, которые имеют поле 'value', а также поле 'next', которое указывает на следующий узел в строке узлов. Операции, которые могут быть выполнены с односвязными списками, включают вставку, удаление и обход.
Следующий код на языке C демонстрирует, как добавить новый узел со «значением» в конец односвязного списка:
// Каждый узел в связанном списке является структурой. Головной узел является первым узлом в списке.Узел * addNodeToTail ( Узел * head , значение int ) { // объявляем указатель Node и инициализируем его так, чтобы он указывал на новый Node (т. е. он будет иметь адрес памяти нового Node), добавляемый в конец списка. Узел * temp = malloc ( sizeof * temp ); /// 'malloc' в stdlib. temp -> value = value ; // Добавляем данные в поле value нового узла. temp -> next = NULL ; // инициализируем недействительные ссылки значением nil. если ( голова == NULL ) { head = temp ; // Если связанный список пуст (т. е. указатель на головной узел является нулевым указателем), то указатель на головной узел указывает на новый узел. } еще { Узел * p = head ; // Присваиваем указатель головного узла указателю узла 'p'. пока ( p -> следующий != NULL ) { p = p -> next ; // Проходим по списку, пока p не станет последним узлом. Последний узел всегда указывает на NULL. } p -> next = temp ; // Заставляем предыдущий последний узел указывать на новый узел. } return head ; // Возвращаем указатель на головной узел. }В «двойном связанном списке» каждый узел содержит, помимо ссылки на следующий узел, второе поле ссылки, указывающее на «предыдущий» узел в последовательности. Две ссылки могут называться «вперед('s')» и «назад», или «следующий» и «предыдущий»('предыдущий').
Метод, известный как XOR-связывание, позволяет реализовать двусвязный список с использованием одного поля связи в каждом узле. Однако этот метод требует возможности выполнять битовые операции с адресами и, следовательно, может быть недоступен в некоторых языках высокого уровня.
Многие современные операционные системы используют двусвязные списки для хранения ссылок на активные процессы, потоки и другие динамические объекты. [2] Распространенная стратегия руткитов , позволяющая избежать обнаружения, заключается в том, чтобы отсоединить себя от этих списков. [3]
В «многосвязном списке» каждый узел содержит два или более полей связи, каждое поле используется для соединения одного и того же набора данных, организованных в разном порядке (например, по имени, по отделу, по дате рождения и т. д.). Хотя двусвязный список можно рассматривать как частный случай многосвязного списка, тот факт, что два и более порядка противоположны друг другу, приводит к более простым и эффективным алгоритмам, поэтому их обычно рассматривают как отдельный случай.
В последнем узле связанного списка поле ссылки часто содержит нулевую ссылку, специальное значение используется для указания отсутствия дальнейших узлов. Менее распространенное соглашение — сделать так, чтобы оно указывало на первый узел списка; в этом случае список называется «кольцевым» или «кольцево связанным»; в противном случае он называется «открытым» или «линейным». Это список, в котором указатель последнего узла указывает на первый узел (т. е. указатель «следующей ссылки» последнего узла имеет адрес памяти первого узла).
В случае кольцевого двусвязного списка первый узел также указывает на последний узел списка.
В некоторых реализациях дополнительный узел 'sentinel' или 'dummy' может быть добавлен перед первой записью данных или после последней. Это соглашение упрощает и ускоряет некоторые алгоритмы обработки списков, гарантируя, что все ссылки могут быть безопасно разыменованы и что каждый список (даже не содержащий элементов данных) всегда имеет "первый" и "последний" узел.
Пустой список — это список, который не содержит записей данных. Обычно это то же самое, что сказать, что у него ноль узлов. Если используются узлы-ограничители, список обычно называют пустым, если в нем есть только узлы-ограничители.
Поля ссылок не обязательно должны быть физической частью узлов. Если записи данных хранятся в массиве и ссылаются на них по индексам, поле ссылок может храниться в отдельном массиве с теми же индексами, что и записи данных.
Поскольку ссылка на первый узел дает доступ ко всему списку, эта ссылка часто называется «адресом», «указателем» или «дескриптором» списка. Алгоритмы, которые манипулируют связанными списками, обычно получают такие дескрипторы для входных списков и возвращают дескрипторы для результирующих списков. Фактически, в контексте таких алгоритмов слово «список» часто означает «дескриптор списка». Однако в некоторых ситуациях может быть удобно ссылаться на список с помощью дескриптора, который состоит из двух ссылок, указывающих на его первый и последний узлы.
Перечисленные выше альтернативы можно произвольно комбинировать практически любым способом, так что могут быть кольцевые двусвязные списки без ограничителей, кольцевые односвязные списки с ограничителями и т. д.
Как и в случае с большинством вариантов в программировании и дизайне, ни один метод не подходит для всех обстоятельств. Структура данных связанного списка может хорошо работать в одном случае, но вызывать проблемы в другом. Это список некоторых распространенных компромиссов, связанных со структурами связанных списков.
Динамический массив — это структура данных, которая размещает все элементы в памяти последовательно и ведет подсчет текущего количества элементов. Если пространство, зарезервированное для динамического массива, превышено, он перераспределяется и (возможно) копируется, что является дорогостоящей операцией.
Связанные списки имеют несколько преимуществ перед динамическими массивами. Вставка или удаление элемента в определенной точке списка, предполагая, что указатель уже индексирован на узел (перед тем, который нужно удалить, или перед точкой вставки), является операцией с постоянным временем (иначе без этой ссылки это будет O(n)), тогда как вставка в динамический массив в случайных местах потребует перемещения половины элементов в среднем и всех элементов в худшем случае. Хотя можно «удалить» элемент из массива за постоянное время, каким-то образом пометив его слот как «свободный», это вызывает фрагментацию , которая затрудняет выполнение итерации.
Более того, в связанный список можно вставить произвольное количество элементов, ограниченное только общим объемом доступной памяти; в то время как динамический массив в конечном итоге заполнит свою базовую структуру данных массива и должен будет перераспределить память — дорогостоящая операция, которая может быть невозможна даже при фрагментации памяти, хотя стоимость перераспределения может быть усреднена по вставкам, а стоимость вставки из-за перераспределения все равно будет амортизирована O (1). Это помогает при добавлении элементов в конец массива, но вставка в (или удаление из) средних позиций все еще несет непомерные затраты из-за перемещения данных для поддержания непрерывности. Массив, из которого удалено много элементов, также может потребовать изменения размера, чтобы избежать траты слишком большого количества пространства.
С другой стороны, динамические массивы (а также структуры данных массивов фиксированного размера) допускают произвольный доступ с постоянным временем , в то время как связанные списки допускают только последовательный доступ к элементам. Фактически, односвязные списки можно легко просматривать только в одном направлении. Это делает связанные списки непригодными для приложений, где полезно быстро искать элемент по его индексу, например, для пирамидальной сортировки . Последовательный доступ к массивам и динамическим массивам также быстрее, чем к связанным спискам на многих машинах, поскольку они имеют оптимальную локальность ссылок и, таким образом, хорошо используют кэширование данных.
Другим недостатком связанных списков является необходимость в дополнительном хранилище для ссылок, что часто делает их непрактичными для списков небольших элементов данных, таких как символы или логические значения , поскольку накладные расходы на хранилище для ссылок могут превышать размер данных в два и более раз. Напротив, динамический массив требует только места для самих данных (и очень небольшого количества управляющих данных). [примечание 1] Также может быть медленно, а при наивном распределителе и расточительно выделять память отдельно для каждого нового элемента, проблема, как правило, решаемая с помощью пулов памяти .
Некоторые гибридные решения пытаются объединить преимущества двух представлений. Развернутые связанные списки хранят несколько элементов в каждом узле списка, увеличивая производительность кэша и одновременно уменьшая накладные расходы памяти для ссылок. Кодирование CDR также делает и то, и другое, заменяя ссылки фактическими данными, на которые ссылаются, которые выходят за пределы конца ссылающейся записи.
Хорошим примером, иллюстрирующим плюсы и минусы использования динамических массивов по сравнению со связанными списками, является реализация программы, которая решает задачу Иосифа Флавия . Задача Иосифа Флавия — это метод выборов, который работает, когда группа людей встает в круг. Начиная с заранее определенного человека, можно считать по кругу n раз. Как только достигнут n -й человек, следует удалить его из круга и заставить участников замкнуть круг. Процесс повторяется до тех пор, пока не останется только один человек. Этот человек выигрывает выборы. Это показывает сильные и слабые стороны связанного списка по сравнению с динамическим массивом, потому что если люди рассматриваются как связанные узлы в циклическом связанном списке, то это показывает, насколько легко связанный список может удалять узлы (поскольку ему нужно только переставить ссылки на разные узлы). Однако связанный список будет плохо находить следующего человека для удаления и ему придется искать по списку, пока он не найдет этого человека. Динамический массив, с другой стороны, будет плох в удалении узлов (или элементов), поскольку он не может удалить один узел, не сдвинув по отдельности все элементы вверх по списку на один. Однако, исключительно легко найти n- го человека в круге, напрямую ссылаясь на него по его положению в массиве.
Проблема ранжирования списков касается эффективного преобразования представления связанного списка в массив. Хотя это тривиально для обычного компьютера, решение этой проблемы параллельным алгоритмом является сложным и стало предметом многих исследований.
Сбалансированное дерево имеет схожие шаблоны доступа к памяти и накладные расходы пространства, как и связанный список, при этом допуская гораздо более эффективную индексацию, занимая O(log n) времени вместо O(n) для случайного доступа. Однако операции вставки и удаления обходятся дороже из-за накладных расходов на манипуляции с деревом для поддержания баланса. Существуют схемы для деревьев, которые автоматически поддерживают себя в сбалансированном состоянии: деревья AVL или красно-черные деревья .
Хотя двусвязные и кольцевые списки имеют преимущества перед односвязными линейными списками, линейные списки обладают некоторыми преимуществами, которые делают их предпочтительными в некоторых ситуациях.
Односвязный линейный список является рекурсивной структурой данных, поскольку он содержит указатель на меньший объект того же типа. По этой причине многие операции над односвязными линейными списками (например, слияние двух списков или перечисление элементов в обратном порядке) часто имеют очень простые рекурсивные алгоритмы, намного проще любого решения с использованием итеративных команд . Хотя эти рекурсивные решения можно адаптировать для двусвязных и циклически связанных списков, процедуры обычно требуют дополнительных аргументов и более сложных базовых случаев.
Линейные односвязные списки также допускают разделение хвоста , использование общей конечной части подсписка в качестве конечной части двух разных списков. В частности, если новый узел добавляется в начало списка, предыдущий список остается доступным в качестве хвоста нового — простой пример постоянной структуры данных . Опять же, это не относится к другим вариантам: узел никогда не может принадлежать двум разным кольцевым или двусвязным спискам.
В частности, узлы end-sentinel могут быть общими для отдельных связанных нециклических списков. Один и тот же узел end-sentinel может использоваться для каждого такого списка. В Lisp , например, каждый правильный список заканчивается ссылкой на специальный узел, обозначаемый nilили ().
Преимущества причудливых вариантов часто ограничиваются сложностью алгоритмов, а не их эффективностью. Круговой список, в частности, обычно можно эмулировать линейным списком вместе с двумя переменными, указывающими на первый и последний узлы, без дополнительных затрат.
Двусвязные списки требуют больше места на узел (если только не используется XOR-связывание ), а их элементарные операции более затратны; но ими часто легче манипулировать, поскольку они обеспечивают быстрый и простой последовательный доступ к списку в обоих направлениях. В двусвязном списке можно вставлять или удалять узел за постоянное количество операций, зная только адрес этого узла. Чтобы сделать то же самое в односвязном списке, необходимо иметь адрес указателя на этот узел, который является либо дескриптором всего списка (в случае первого узла), либо полем ссылки в предыдущем узле. Некоторые алгоритмы требуют доступа в обоих направлениях. С другой стороны, двусвязные списки не допускают совместного использования хвостов и не могут использоваться в качестве постоянных структур данных .
Круговой связанный список может быть естественным вариантом для представления массивов, которые являются естественно круглыми, например, углов многоугольника , пула буферов , которые используются и освобождаются в порядке FIFO («первым пришел, первым ушел»), или набора процессов, которые должны быть разделены во времени в циклическом порядке . В этих приложениях указатель на любой узел служит дескриптором всего списка.
В случае кольцевого списка указатель на последний узел дает легкий доступ также и к первому узлу, следуя одной ссылке. Таким образом, в приложениях, которым требуется доступ к обоим концам списка (например, при реализации очереди), кольцевая структура позволяет управлять структурой с помощью одного указателя вместо двух.
Круговой список можно разделить на два круговых списка за постоянное время, указав адреса последнего узла каждой части. Операция заключается в обмене содержимым полей ссылок этих двух узлов. Применение той же операции к любым двум узлам в двух различных списках объединяет два списка в один. Это свойство значительно упрощает некоторые алгоритмы и структуры данных, такие как quad-edge и face-edge.
Простейшим представлением пустого кольцевого списка (когда это имеет смысл) является нулевой указатель, указывающий, что в списке нет узлов. Без этого выбора многим алгоритмам приходится проверять этот особый случай и обрабатывать его отдельно. Напротив, использование null для обозначения пустого линейного списка более естественно и часто создает меньше особых случаев.
Для некоторых приложений может быть полезно использовать односвязные списки, которые могут быть как кольцевыми, так и линейными, или даже кольцевыми с линейным начальным сегментом. Алгоритмы поиска или иных операций с ними должны принимать меры предосторожности, чтобы избежать случайного попадания в бесконечный цикл. Один из известных методов заключается в том, чтобы второй указатель обходил список с половинной или удвоенной скоростью, и если оба указателя встречаются в одном и том же узле, цикл найден.
Узел Sentinel может упростить некоторые операции со списком, гарантируя, что следующие или предыдущие узлы существуют для каждого элемента, и что даже пустые списки имеют по крайней мере один узел. Можно также использовать узел Sentinel в конце списка с соответствующим полем данных, чтобы исключить некоторые проверки конца списка. Например, при сканировании списка в поисках узла с заданным значением x установка поля данных Sentinel в x делает ненужной проверку конца списка внутри цикла. Другим примером является слияние двух отсортированных списков: если их Sentinel имеют поля данных, установленные в +∞, выбор следующего выходного узла не требует специальной обработки для пустых списков.
Однако контрольные узлы занимают дополнительное пространство (особенно в приложениях, использующих много коротких списков), и они могут усложнить другие операции (например, создание нового пустого списка).
Однако, если кольцевой список используется только для имитации линейного списка, можно избежать некоторых из этих сложностей, добавив один узел-сентинел в каждый список между последним и первым узлами данных. При таком соглашении пустой список состоит только из узла-сентинел, указывающего на себя через ссылку на следующий узел. Тогда дескриптор списка должен быть указателем на последний узел данных перед сентинел, если список не пуст; или на сам сентинел, если список пуст.
Тот же трюк можно использовать для упрощения обработки двусвязного линейного списка, превратив его в кольцевой двусвязный список с одним узлом-ограничителем. Однако в этом случае дескриптор должен быть единственным указателем на сам фиктивный узел. [6]
При манипулировании связанными списками на месте необходимо соблюдать осторожность, чтобы не использовать значения, которые были признаны недействительными в предыдущих назначениях. Это делает алгоритмы вставки или удаления узлов связанных списков несколько тонкими. В этом разделе дается псевдокод для добавления или удаления узлов из одиночно, дважды и циклически связанных списков на месте. Везде null используется для обозначения маркера конца списка или сторожевого знака , который может быть реализован несколькими способами.
Структура данных узла будет иметь два поля. Также есть переменная firstNode , которая всегда указывает на первый узел в списке или равна null для пустого списка.
запись узла{ data; // Данные, хранящиеся в узле Node next // Ссылка [ 2] на следующий узел, null для последнего узла} Список записей{ Node firstNode // указывает на первый узел списка; null для пустого списка}Обход односвязного списка прост: начиная с первого узла и следуя по каждой следующей ссылке, пока не достигнем конца:
node := list.firstNode пока node не null (сделать что-нибудь с node.data) узел := узел.следующий
Следующий код вставляет узел после существующего узла в односвязном списке. На схеме показано, как это работает. Вставка узла перед существующим не может быть выполнена напрямую; вместо этого необходимо отслеживать предыдущий узел и вставлять узел после него.
function insertAfter( Node node, Node newNode) // вставить newNode после node новыйУзел.следующий := узел.следующий узел.следующий := новыйУзел
Вставка в начало списка требует отдельной функции. Это требует обновления firstNode .
function insertBeginning( List list, Node newNode) // вставить узел перед текущим первым узлом новыйУзел.следующий := список.первыйУзел список.первыйУзел := новыйУзел
Аналогично, существуют функции для удаления узла после заданного узла и для удаления узла из начала списка. Диаграмма демонстрирует первое. Чтобы найти и удалить определенный узел, нужно снова отслеживать предыдущий элемент.
function removeAfter( Node node) // удалить узел после этого obsoleteNode := node.next узел.следующий := узел.следующий.следующий уничтожить устаревший узел
function removeBeginning( List list) // удалить первый узел obsoleteNode := list.firstNode list.firstNode := list.firstNode.next // указывает на узел после удаленного узла уничтожить устаревший узел
Обратите внимание, что при удалении последнего узла в списке removeBeginning()устанавливается list.firstNodeзначение .null
Поскольку невозможно выполнить итерацию в обратном направлении, эффективные операции insertBeforeили removeBeforeневозможны. Вставка в список перед определенным узлом требует обхода списка, что в худшем случае будет иметь время выполнения O(n).
Добавление одного связанного списка к другому может быть неэффективным, если ссылка на хвост не сохраняется как часть структуры списка, поскольку необходимо обойти весь первый список, чтобы найти хвост, а затем добавить к нему второй список. Таким образом, если два линейно связанных списка имеют длину , асимптотическая временная сложность добавления списков составляет . В семействе языков Lisp добавление списков обеспечивается процедурой .append
Многие особые случаи операций со связанными списками можно устранить, включив фиктивный элемент в начало списка. Это гарантирует отсутствие особых случаев для начала списка и делает и insertBeginning()ненужными removeBeginning(), т. е. каждый элемент или узел находится рядом с другим узлом (даже первый узел находится рядом с фиктивным узлом). В этом случае первые полезные данные в списке будут найдены в .list.firstNode.next
В циклически связанном списке все узлы соединены в непрерывный круг без использования null. Для списков с началом и концом (например, очередь) сохраняется ссылка на последний узел в списке. Следующий узел после последнего узла является первым узлом. Элементы могут быть добавлены в конец списка и удалены из начала за постоянное время.
Кольцевые списки могут быть как односвязными, так и двусвязными.
Оба типа циклически связанных списков выигрывают от возможности проходить по всему списку, начиная с любого заданного узла. Это часто позволяет нам избегать хранения firstNode и lastNode , хотя если список может быть пустым, должно быть специальное представление для пустого списка, например, переменная lastNode , которая указывает на некоторый узел в списке или равна null , если он пуст; здесь используется такой lastNode . Это представление значительно упрощает добавление и удаление узлов с непустым списком, но пустые списки тогда являются особым случаем.
Предполагая, что someNode — это некоторый узел в непустом кольцевом односвязном списке, этот код выполняет итерацию по этому списку, начиная с someNode :
функция iterate(someNode) если someNode ≠ null узел := некоторыйУзел делать сделать что-нибудь с node.value узел := узел.следующий пока узел ≠ someNode
Обратите внимание, что тест " while node ≠ someNode" должен быть в конце цикла. Если тест переместить в начало цикла, процедура будет завершаться ошибкой всякий раз, когда в списке будет только один узел.
Эта функция вставляет узел "newNode" в кольцевой связанный список после заданного узла "node". Если "node" равен null, предполагается, что список пуст.
function insertAfter( Node node, Node newNode) if node = null // предполагаем, что список пуст новыйУзел.следующий := новыйУзел еще новыйУзел.следующий := узел.следующий узел.следующий := новыйУзел при необходимости обновите переменную lastNode
Предположим, что "L" — это переменная, указывающая на последний узел кольцевого связанного списка (или null, если список пуст). Чтобы добавить "newNode" в конец списка, можно сделать следующее:
вставитьПосле(L, новыйУзел)L := новыйУзел
Чтобы вставить «newNode» в начало списка, можно сделать следующее:
insertAfter(L, newNode) если L = null L := новыйУзел
Эта функция вставляет значение "newVal" перед заданным узлом "node" за время O(1). Новый узел был создан между "node" и следующим узлом, затем помещает значение "node" в этот новый узел и помещает "newVal" в "node". Таким образом, односвязный циклически связанный список с единственной переменной firstNode может вставляться как вперед, так и назад за время O(1).
function insertBefore( Node node, newVal) if node = null // предполагаем, что список пуст newNode := new Node(data:=newVal, next:=newNode) else newNode := new Node(data:=node.data, next:=node.next) node.data := newVal узел.следующий := новыйУзелпри необходимости обновите переменную firstNode
Эта функция удаляет ненулевой узел из списка размером больше 1 за время O(1). Она копирует данные из следующего узла в узел, а затем устанавливает указатель next узла для пропуска следующего узла.
функция remove( Node node) если node ≠ null и размер списка > 1 удаленныеДанные := узел.данные узел.данные := узел.следующие.данные узел.следующий = узел.следующий.следующий возврат удаленных данных
Языки, не поддерживающие никаких типов ссылок, все равно могут создавать ссылки, заменяя указатели индексами массива. Подход заключается в том, чтобы хранить массив записей , где каждая запись имеет целочисленные поля, указывающие индекс следующего (и, возможно, предыдущего) узла в массиве. Не все узлы в массиве нужно использовать. Если записи также не поддерживаются, вместо них часто можно использовать параллельные массивы .
В качестве примера рассмотрим следующую запись связанного списка, в которой вместо указателей используются массивы:
запись Entry { integer next; // индекс следующей записи в массиве integer prev; // предыдущая запись (если она дважды связана) string name; real balance;}Связанный список можно построить, создав массив этих структур и целочисленную переменную для хранения индекса первого элемента.
целочисленный списокHead Entry Records[1000]
Связи между элементами формируются путем помещения индекса массива следующей (или предыдущей) ячейки в поле Next или Prev внутри данного элемента. Например:
В приведенном выше примере ListHeadбудет установлено значение 2, местоположение первой записи в списке. Обратите внимание, что записи 3 и 5–7 не являются частью списка. Эти ячейки доступны для любых добавлений в список. Создав ListFreeцелочисленную переменную, можно создать свободный список для отслеживания доступных ячеек. Если все записи используются, размер массива придется увеличить или некоторые элементы придется удалить, прежде чем новые записи можно будет сохранить в списке.
Следующий код будет обходить список и отображать имена и баланс счета:
i := listHead while i ≥ 0 // цикл по списку print i, Records[i].name, Records[i].balance // печать записи i := Записи[i].следующий
При наличии выбора преимущества такого подхода включают в себя:
Однако этот подход имеет один главный недостаток: он создает и управляет частным пространством памяти для своих узлов. Это приводит к следующим проблемам:
По этим причинам данный подход в основном используется для языков, не поддерживающих динамическое распределение памяти. Эти недостатки также смягчаются, если максимальный размер списка известен на момент создания массива.
Многие языки программирования, такие как Lisp и Scheme, имеют встроенные односвязные списки. Во многих функциональных языках эти списки строятся из узлов, каждый из которых называется cons или cons cell . Cons имеет два поля: car , ссылку на данные для этого узла, и cdr , ссылку на следующий узел. Хотя cons cells можно использовать для построения других структур данных, это их основное назначение.
В языках, которые поддерживают абстрактные типы данных или шаблоны, ADT или шаблоны связанных списков доступны для построения связанных списков. В других языках связанные списки обычно строятся с использованием ссылок вместе с записями .
При построении связанного списка возникает выбор, хранить ли данные списка непосредственно в узлах связанного списка, называемых внутренним хранилищем , или просто хранить ссылку на данные, называемых внешним хранилищем . Внутреннее хранилище имеет то преимущество, что делает доступ к данным более эффективным, требует меньшего объема хранилища в целом, имеет лучшую локальность ссылок и упрощает управление памятью для списка (его данные выделяются и освобождаются одновременно с узлами списка).
Внешнее хранилище, с другой стороны, имеет преимущество в том, что оно более универсально, в том смысле, что одна и та же структура данных и машинный код могут использоваться для связанного списка независимо от размера данных. Это также упрощает размещение одних и тех же данных в нескольких связанных списках. Хотя при внутреннем хранилище одни и те же данные могут быть размещены в нескольких списках путем включения нескольких ссылок next в структуру данных узла, тогда необходимо будет создать отдельные процедуры для добавления или удаления ячеек на основе каждого поля. Можно создать дополнительные связанные списки элементов, которые используют внутреннее хранилище, используя внешнее хранилище, и иметь ячейки дополнительных связанных списков, хранящие ссылки на узлы связанного списка, содержащие данные.
В общем, если набор структур данных необходимо включить в связанные списки, то внешнее хранилище является наилучшим подходом. Если набор структур данных необходимо включить только в один связанный список, то внутреннее хранилище будет немного лучше, если только не доступен пакет общего связанного списка, использующий внешнее хранилище. Аналогично, если разные наборы данных, которые могут храниться в одной и той же структуре данных, должны быть включены в один связанный список, то внутреннее хранилище будет вполне достаточно.
Другой подход, который можно использовать с некоторыми языками, заключается в наличии различных структур данных, но все они имеют начальные поля, включая ссылки next (и prev , если это двойной связанный список) в одном и том же месте. После определения отдельных структур для каждого типа данных можно определить общую структуру, которая содержит минимальный объем данных, общих для всех других структур и содержащихся в верхней части (начале) структур. Затем можно создать общие процедуры, которые используют минимальную структуру для выполнения операций типа связанного списка, но затем отдельные процедуры могут обрабатывать определенные данные. Этот подход часто используется в процедурах анализа сообщений, где принимаются несколько типов сообщений, но все они начинаются с одного и того же набора полей, обычно включая поле для типа сообщения. Общие процедуры используются для добавления новых сообщений в очередь при их получении и удаления их из очереди для обработки сообщения. Затем поле типа сообщения используется для вызова правильной процедуры для обработки определенного типа сообщения.
Чтобы создать связанный список семей и их членов с использованием внутреннего хранилища, структура может выглядеть следующим образом:
запись член { // член семьи член next; string firstName; целое число age;}запись семья { // сама семья семья следующая; строка lastName; строка address; член члены // голова списка членов этой семьи}Чтобы распечатать полный список семей и их членов, используя внутреннюю память, напишите:
aFamily := Families // начать с главы списка семей , пока aFamily ≠ null // выполнить цикл по списку семей распечатать информацию о семье aMember := aFamily.members // получить главу списка членов этой семьи , пока aMember ≠ null // выполнить цикл по списку членов распечатать информацию об участнике aMember := aMember.следующий aFamily := aFamily.next
Используя внешнее хранилище, можно создать следующие структуры:
запись узла { // общая структура ссылки узел следующий; указатель данных // общий указатель для данных в узле}запись член { // структура для члена семьи string firstName; целое число age}запись семья { // структура для семьи строка lastName; строка адрес; узел members // голова списка членов этой семьи}Чтобы распечатать полный список семей и их членов с использованием внешнего хранилища, напишите:
famNode := Families // начать с заголовка списка семей , пока famNode ≠ null // выполнить цикл по списку семей aFamily := (family) famNode.data // извлечь семью из узла распечатать информацию о семье memNode := aFamily.members // получить список членов семьи , пока memNode ≠ null // выполнить цикл по списку членов aMember := (member)memNode.data // извлечь члена из узла распечатать информацию об участнике memNode := memNode.следующий famNode := famNode.next
Обратите внимание, что при использовании внешнего хранилища требуется дополнительный шаг для извлечения записи из узла и приведения ее к соответствующему типу данных. Это связано с тем, что и список семей, и список членов внутри семьи хранятся в двух связанных списках, использующих одну и ту же структуру данных ( узел ), а этот язык не имеет параметрических типов.
Пока число семейств, к которым может принадлежать член, известно во время компиляции, внутреннее хранилище работает нормально. Однако, если член должен быть включен в произвольное число семейств, а конкретное число известно только во время выполнения, потребуется внешнее хранилище.
Поиск определенного элемента в связанном списке, даже если он отсортирован, обычно требует O( n ) времени ( линейный поиск ). Это один из основных недостатков связанных списков по сравнению с другими структурами данных. В дополнение к вариантам, рассмотренным выше, ниже приведены два простых способа улучшить время поиска.
В неупорядоченном списке одной простой эвристикой для уменьшения среднего времени поиска является эвристика перемещения вперед , которая просто перемещает элемент в начало списка после его нахождения. Эта схема, удобная для создания простых кэшей, гарантирует, что самые последние использованные элементы также будут быстрее всего найдены снова.
Другой распространенный подход — « индексировать » связанный список с использованием более эффективной внешней структуры данных. Например, можно построить красно-черное дерево или хэш-таблицу , элементы которой являются ссылками на узлы связанного списка. Несколько таких индексов могут быть построены на одном списке. Недостатком является то, что эти индексы, возможно, придется обновлять каждый раз, когда добавляется или удаляется узел (или, по крайней мере, перед тем, как этот индекс будет использован снова).
Список произвольного доступа — это список с поддержкой быстрого произвольного доступа для чтения или изменения любого элемента в списке. [7] Одной из возможных реализаций является перекошенный двоичный список произвольного доступа, использующий перекошенную двоичную систему счисления , которая включает в себя список деревьев со специальными свойствами; это позволяет в худшем случае выполнять операции head/cons за постоянное время и в худшем случае выполнять случайный доступ к элементу по индексу за логарифмическое время. [7] Списки произвольного доступа могут быть реализованы как постоянные структуры данных . [7]
Списки с произвольным доступом можно рассматривать как неизменяемые связанные списки, поскольку они также поддерживают те же операции O(1) над головой и хвостом. [7]
Простым расширением списков с произвольным доступом является min-list, который обеспечивает дополнительную операцию, которая возвращает минимальный элемент во всем списке за постоянное время (без [ необходимо разъяснение ] сложностей мутации). [7]
И стеки , и очереди часто реализуются с использованием связанных списков и просто ограничивают тип поддерживаемых операций.
Список пропуска — это связанный список, дополненный слоями указателей для быстрого перехода через большое количество элементов, а затем спуска на следующий слой. Этот процесс продолжается до самого нижнего слоя, который является фактическим списком.
Бинарное дерево можно рассматривать как тип связанного списка, где элементы сами являются связанными списками той же природы. Результатом является то, что каждый узел может включать ссылку на первый узел одного или двух других связанных списков, которые вместе со своим содержимым образуют поддеревья ниже этого узла.
Неразвернутый связанный список — это связанный список, в котором каждый узел содержит массив значений данных. Это приводит к повышению производительности кэша , поскольку больше элементов списка находятся в памяти смежно, и снижению накладных расходов на память, поскольку для каждого элемента списка требуется хранить меньше метаданных.
Хеш -таблица может использовать связанные списки для хранения цепочек элементов, которые хешируются в одну и ту же позицию в хеш-таблице.
Куча разделяет некоторые свойства упорядочения связанного списка, но почти всегда реализуется с использованием массива. Вместо ссылок от узла к узлу, следующие и предыдущие индексы данных вычисляются с использованием индекса текущих данных .
Самоорганизующийся список переупорядочивает свои узлы на основе некоторой эвристики, которая сокращает время поиска для извлечения данных, сохраняя часто используемые узлы во главе списка.
{{cite book}}: |work=проигнорировано ( помощь )