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

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

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

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

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

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

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

Недостатки [ править ]

• Они используют больше памяти, чем массивы, из-за хранилища, используемого их указателями .
• Узлы в связанном списке должны читаться по порядку с самого начала, поскольку связанные списки по своей сути являются последовательным доступом .
• Узлы хранятся несмежно, что значительно увеличивает периоды времени, необходимые для доступа к отдельным элементам в списке, особенно с кешем ЦП .
• Когда дело доходит до обратного обхода, в связанных списках возникают трудности. Например, односвязные списки неудобны для перемещения назад ^[1], и хотя двусвязные списки несколько легче читать, память расходуется на выделение места для обратного указателя .

История [ править ]

Связанные списки были разработаны в 1955–1956 гг. Алленом Ньюэллом , Клиффом Шоу и Гербертом А. Саймоном из корпорации RAND в качестве основной структуры данных для их языка обработки информации . Авторы использовали IPL для разработки нескольких ранних программ искусственного интеллекта , в том числе Logic Theory Machine, General Problem Solver и компьютерной шахматной программы. Отчеты об их работе появились в IRE Transactions on Information Theory в 1956 г., а также в материалах нескольких конференций с 1957 по 1959 г., в том числе в Proceedings of the Western Joint Computer Conference в 1957 и 1958 гг.Международная конференция ЮНЕСКО по обработке информации) в 1959 году. Теперь ставшая классической диаграмма, состоящая из блоков, представляющих узлы списка со стрелками, указывающими на последовательные узлы списка, появляется в «Программировании машины логической теории» Ньюэлла и Шоу в Proc. WJCC, февраль 1957 года. Ньюэлл и Саймон были отмечены премией ACM Turing в 1975 году за «основной вклад в искусственный интеллект, психологию человеческого познания и обработку списков». Проблемой машинного перевода для обработки естественного языка руководил Виктор Ингве из Массачусетского технологического института.(MIT) использовать связанные списки в качестве структур данных на своем языке программирования COMIT для компьютерных исследований в области лингвистики . Отчет об этом языке под названием «Язык программирования для механического перевода» появились в механическом переводе в 1958 г. ^{[ править ]}

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

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

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

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

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

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

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

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

Односвязный список [ править ]

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

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

Узел  ADDNODE ( узел  головки ,  INT  значение )  {  узла  температуры ,  р ;  // объявляем два узла temp и p  temp  =  createNode ();  // предполагаем, что createNode создает новый узел с данными = 0, а затем указывает на NULL.  темп -> данные  =  значение ;  // добавляем значение элемента в часть данных узла  if  ( head  ==  NULL )  {  head  =  temp ;  // когда связанный список пуст  }  else  { p  =  голова ;  // присваиваем заголовок p  while  ( p -> next  ! =  NULL )  {  p  =  p -> next ;  // Обходим список, пока p не станет последним узлом. Последний узел всегда указывает на NULL.  }  p -> next  =  temp ;  // Указываем предыдущий последний узел на новый созданный узел.  }  вернуть  голову ; }

Двусвязный список [ править ]

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

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

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

Многосвязный список [ править ]

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

Циркулярно связанный список [ править ]

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

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

Сторожевые узлы [ править ]

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

Пустые списки [ править ]

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

Связывание хэшей [ править ]

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

Перечислить дескрипторы [ править ]

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

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

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

Компромиссы [ править ]

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

Связанные списки и динамические массивы [ править ]

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

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

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

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

Еще одним недостатком связанных списков является дополнительное хранилище, необходимое для ссылок, что часто делает их непрактичными для списков небольших элементов данных, таких как символы или логические значения , поскольку накладные расходы на хранилище для ссылок могут в два или более раз превышать размер данные. Напротив, динамический массив требует только места для самих данных (и очень небольшого количества управляющих данных). ^{[примечание 1]} Также может быть медленным, а при наивном распределителе расточительным выделять память отдельно для каждого нового элемента, проблема обычно решается с использованием пулов памяти .

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

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

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

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

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

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

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

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

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

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

Двусвязные и односвязные [ править ]

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

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

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

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

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

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

Использование сторожевых узлов [ править ]

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

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

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

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

Связанные списки операций [ править ]

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

Линейно связанные списки [ править ]

Односвязные списки [ править ]

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

 узел записи{ данные; // Данные хранятся в узле  Узел следующий // Ссылка [2] на следующий узел, null для последнего узла}

 Список записей{ Node firstNode // указывает на первый узел списка; null для пустого списка}

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

node: = list.firstNode, а node не null (сделайте что-нибудь с node.data) узел: = node.next

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

function insertAfter ( Node node, Node newNode) // вставляем newNode после узла newNode.next: = node.next node.next: = newNode

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

function insertBeginning ( List list, Node newNode) // вставить узел перед текущим первым узлом newNode.next: = list.firstNode list.firstNode: = newNode

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

function removeAfter ( Node node) // удаляем узел за этим obsoleteNode: = node.next node.next: = node.next.next уничтожить устаревший узел

function removeBeginning ( Список списка) // удаляем первый узел obsoleteNode: = list.firstNode list.firstNode: = list.firstNode.next // указывает мимо удаленного узла уничтожить устаревший узел

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

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

Добавление одного связанного списка к другому может быть неэффективным, если ссылка на хвост не сохраняется как часть структуры списка, потому что мы должны пройти весь первый список, чтобы найти хвост, а затем добавить к нему второй список. Таким образом, если каждый из двух линейно связанных списков имеет длину , асимптотическая временная сложность добавления списка составляет . В семействе языков Лисп добавление списка обеспечивается процедурой.${\ displaystyle n}$${\ Displaystyle О (п)}$append

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

Циркулярно связанный список [ править ]

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

Списки с круговой связью могут быть односвязными или двусвязными.

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

Алгоритмы [ править ]

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

функция итерация (someNode), если someNode ≠ null узел: = someNode делать сделать что-нибудь с node.value узел: = node.next пока узел ≠ someNode

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

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

function insertAfter ( Node node, Node newNode) if node = null // предполагаем, что список пуст newNode.next: = newNode еще newNode.next: = node.next node.next: = newNodeпри необходимости обновить переменную lastNode

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

insertAfter (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: = новый узел (data: = newVal, next: = newNode) иначе newNode: = новый узел (data: = node.data, next: = node.next) node.data: = newVal node.next: = newNodeпри необходимости обновить переменную firstNode

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

функция удалить ( узел узла), если узел ≠ null и размер списка> 1 удаленные данные: = node.data node.data: = node.next.data node.next = node.next.next вернуть удаленные данные

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

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

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

запись  Entry { целое число далее; // индекс следующей записи в массиве  integer prev; // предыдущая запись (если двойная ссылка)  string name; реальный баланс;}

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

целочисленный listHead Entry Records [1000]

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

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

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

i: = listHead while i ≥ 0 // цикл по списку print i, Records [i] .name, Records [i] .balance // печать записи i: = Records [i] .next

Когда стоит перед выбором, преимущества такого подхода включают:

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

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

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

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

Языковая поддержка [ править ]

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

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

Внутреннее и внешнее хранилище [ править ]

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

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

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

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

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

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

запись  член { // член семьи  члена следующего; строка firstName; целочисленный возраст;}запись  семьи { // сама  семья family next; строка lastName; строковый адрес; member members // глава списка членов этой семьи}

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

aFamily: = Families // начало списка семейств, а aFamily ≠ null  // цикл по списку семейств распечатать информацию о семье aMember: = aFamily.members // получение главы списка членов этого семейства, в  то время как aMember ≠ null  // цикл по списку членов распечатать информацию о члене aMember: = aMember.next aFamily: = aFamily.next

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

запись  узла { // общая ссылка структура  узла рядом; данные указателя // общий указатель на данные в узле}record  member { // структура члена семьи  string firstName; целочисленный возраст}record  family { // структура для семейства  string lastName; строковый адрес; node members // глава списка членов этого семейства}

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

famNode: = Families // начинается с главы списка семейств, в то время как famNode ≠ null  // цикл по списку семейств aFamily: = (family) famNode.data // извлекает семью из узла распечатать информацию о семье memNode: = aFamily.members // получение списка членов семьи, в  то время как memNode loop null  // цикл по списку членов aMember: = (member) memNode.data // извлечение члена из узла распечатать информацию о члене memNode: = memNode.next famNode: = famNode.next

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

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

Ускорение поиска [ править ]

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

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

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

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

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

Списки произвольного доступа можно рассматривать как неизменяемые связанные списки, поскольку они также поддерживают одни и те же операции O (1) head и tail. ^[9]

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

Связанные структуры данных [ править ]

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

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

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

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

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

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

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

Примечания [ править ]

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Хуан, Ангел (2006). «Ch20 - структуры данных; ID06 - ПРОГРАММИРОВАНИЕ с помощью JAVA (слайд из книги« Большая Java », автор: CayS. Horstmann)» (PDF) . п. 3. Архивировано из оригинального (PDF) 06.01.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). Введение в алгоритмы . MIT Press. С. 205–213, 501–505. ISBN 0-262-03293-7.
• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001). «10.2: Связанные списки». Введение в алгоритмы (2-е изд.). MIT Press. С. 204–209. ISBN 0-262-03293-7.
• Грин, Берт Ф., младший (1961). «Компьютерные языки для манипулирования символами». Операции IRE по человеческому фактору в электронике (2): 3–8. DOI : 10.1109 / THFE2.1961.4503292 .
• Маккарти, Джон (1960). «Рекурсивные функции символьных выражений и их машинное вычисление, часть I» . Коммуникации ACM . 3 (4): 184. DOI : 10.1145 / 367177.367199 .
• Кнут, Дональд (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). «Эксперимент с самокомпилирующимся компилятором для простого языка обработки списков». Годовой обзор в автоматическом программировании . Pergamon Press. 4 (1): 1. DOI : 10,1016 / 0066-4138 (64) 90013-8 .
• Уилкс, Морис Винсент (1964). «Списки и почему они полезны». Поступления Национальной конференции ACM, Филадельфия , 1964 . ACM (P – 64): F1–1.
• Шанмугасундарам, Кулеш (2004-04-2005). «Объяснение связанного списка ядра Linux» . Проверено 21 сентября 2009 .

Внешние ссылки [ править ]

Викискладе есть медиафайлы, связанные со связанными списками .

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