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

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

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

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

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

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

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

История

Связанные списки были разработаны в 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 гг., А также в материалах обработки информации (Proceedings of the firstМеждународная конференция ЮНЕСКО по обработке информации) в 1959 г. Теперь уже ставшая классической диаграмма, состоящая из блоков, представляющих узлы списка со стрелками, указывающими на последовательные узлы списка, появляется в «Программировании машины логической теории» Ньюэлла и Шоу в Proc. WJCC, февраль 1957 г. Ньюэлл и Саймон были отмечены премией ACM Turing в 1975 г. за «основной вклад в искусственный интеллект, психологию человеческого познания и обработку списков». Проблемой машинного перевода для обработки естественного языка руководил Виктор Ингве из Массачусетского технологического института.(MIT) использовать связанные списки в качестве структур данных на своем языке программирования COMIT для компьютерных исследований в области лингвистики . Отчет об этом языке под названием «Язык программирования для механического перевода» появились в механическом переводе в 1958 г. ^{[ править ]}

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

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 ;  // Указываем предыдущий последний узел на новый созданный узел.  }  вернуть  голову ; }

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

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

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

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

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

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

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

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

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

Сторожевые узлы

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

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

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

Связывание хэшей

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

Перечислить дескрипторы

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

Комбинируя альтернативы

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

Компромиссы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Двусвязные и односвязные

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Singly linked lists

Our node data structure will have two fields. We also keep a variable firstNode which always points to the first node in the list, or is null for an empty list.

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

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

Traversal of a singly linked list is simple, beginning at the first node and following each next link until we come to the end:

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

The following code inserts a node after an existing node in a singly linked list. The diagram shows how it works. Inserting a node before an existing one cannot be done directly; instead, one must keep track of the previous node and insert a node after it.

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

Inserting at the beginning of the list requires a separate function. This requires updating firstNode.

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

Similarly, we have functions for removing the node after a given node, and for removing a node from the beginning of the list. The diagram demonstrates the former. To find and remove a particular node, one must again keep track of the previous element.

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

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

Notice that removeBeginning() sets list.firstNode to null when removing the last node in the list.

Since we can't iterate backwards, efficient insertBefore or removeBefore operations are not possible. Inserting to a list before a specific node requires traversing the list, which would have a worst case running time of O(n).

Appending one linked list to another can be inefficient unless a reference to the tail is kept as part of the List structure, because we must traverse the entire first list in order to find the tail, and then append the second list to this. Thus, if two linearly linked lists are each of length ${\displaystyle n}$, list appending has asymptotic time complexity of ${\displaystyle O(n)}$. In the Lisp family of languages, list appending is provided by the append procedure.

Many of the special cases of linked list operations can be eliminated by including a dummy element at the front of the list. This ensures that there are no special cases for the beginning of the list and renders both insertBeginning() and removeBeginning() unnecessary. In this case, the first useful data in the list will be found at list.firstNode.next.

Circularly linked list

In a circularly linked list, all nodes are linked in a continuous circle, without using null. For lists with a front and a back (such as a queue), one stores a reference to the last node in the list. The next node after the last node is the first node. Elements can be added to the back of the list and removed from the front in constant time.

Circularly linked lists can be either singly or doubly linked.

Both types of circularly linked lists benefit from the ability to traverse the full list beginning at any given node. This often allows us to avoid storing firstNode and lastNode, although if the list may be empty we need a special representation for the empty list, such as a lastNode variable which points to some node in the list or is null if it's empty; we use such a lastNode here. This representation significantly simplifies adding and removing nodes with a non-empty list, but empty lists are then a special case.

Algorithms

Assuming that someNode is some node in a non-empty circular singly linked list, this code iterates through that list starting with someNode:

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

Notice that the test "while node ≠ someNode" must be at the end of the loop. If the test was moved to the beginning of the loop, the procedure would fail whenever the list had only one node.

This function inserts a node "newNode" into a circular linked list after a given node "node". If "node" is null, it assumes that the list is empty.

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

Suppose that "L" is a variable pointing to the last node of a circular linked list (or null if the list is empty). To append "newNode" to the end of the list, one may do

insertAfter(L, newNode)L := newNode

To insert "newNode" at the beginning of the list, one may do

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

This function inserts a value "newVal" before a given node "node" in O(1) time. We create a new node between "node" and the next node, and then put the value of "node" into that new node, and put "newVal" in "node". Thus, a singly linked circularly linked list with only a firstNode variable can both insert to the front and back in O(1) time.

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

This function removes a non-null node from a list of size greater than 1 in O(1) time. It copies data from the next node into the node, and then sets the node's next pointer to skip over the next node.

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

Linked lists using arrays of nodes

Languages that do not support any type of reference can still create links by replacing pointers with array indices. The approach is to keep an array of records, where each record has integer fields indicating the index of the next (and possibly previous) node in the array. Not all nodes in the array need be used. If records are also not supported, parallel arrays can often be used instead.

As an example, consider the following linked list record that uses arrays instead of pointers:

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

A linked list can be built by creating an array of these structures, and an integer variable to store the index of the first element.

integer listHeadEntry Records[1000]

Links between elements are formed by placing the array index of the next (or previous) cell into the Next or Prev field within a given element. For example:

In the above example, ListHead would be set to 2, the location of the first entry in the list. Notice that entry 3 and 5 through 7 are not part of the list. These cells are available for any additions to the list. By creating a ListFree integer variable, a free list could be created to keep track of what cells are available. If all entries are in use, the size of the array would have to be increased or some elements would have to be deleted before new entries could be stored in the list.

The following code would traverse the list and display names and account balance:

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

When faced with a choice, the advantages of this approach include:

• The linked list is relocatable, meaning it can be moved about in memory at will, and it can also be quickly and directly serialized for storage on disk or transfer over a network.
• Especially for a small list, array indexes can occupy significantly less space than a full pointer on many architectures.
• Locality of reference can be improved by keeping the nodes together in memory and by periodically rearranging them, although this can also be done in a general store.
• Naïve dynamic memory allocators can produce an excessive amount of overhead storage for each node allocated; almost no allocation overhead is incurred per node in this approach.
• Seizing an entry from a pre-allocated array is faster than using dynamic memory allocation for each node, since dynamic memory allocation typically requires a search for a free memory block of the desired size.

This approach has one main disadvantage, however: it creates and manages a private memory space for its nodes. This leads to the following issues:

• It increases complexity of the implementation.
• Growing a large array when it is full may be difficult or impossible, whereas finding space for a new linked list node in a large, general memory pool may be easier.
• Adding elements to a dynamic array will occasionally (when it is full) unexpectedly take linear (O(n)) instead of constant time (although it's still an amortized constant).
• Using a general memory pool leaves more memory for other data if the list is smaller than expected or if many nodes are freed.

For these reasons, this approach is mainly used for languages that do not support dynamic memory allocation. These disadvantages are also mitigated if the maximum size of the list is known at the time the array is created.

Language support

Many programming languages such as Lisp and Scheme have singly linked lists built in. In many functional languages, these lists are constructed from nodes, each called a cons or cons cell. The cons has two fields: the car, a reference to the data for that node, and the cdr, a reference to the next node. Although cons cells can be used to build other data structures, this is their primary purpose.

In languages that support abstract data types or templates, linked list ADTs or templates are available for building linked lists. In other languages, linked lists are typically built using references together with records.

Internal and external storage

When constructing a linked list, one is faced with the choice of whether to store the data of the list directly in the linked list nodes, called internal storage, or merely to store a reference to the data, called external storage. Internal storage has the advantage of making access to the data more efficient, requiring less storage overall, having better locality of reference, and simplifying memory management for the list (its data is allocated and deallocated at the same time as the list nodes).

External storage, on the other hand, has the advantage of being more generic, in that the same data structure and machine code can be used for a linked list no matter what the size of the data is. It also makes it easy to place the same data in multiple linked lists. Although with internal storage the same data can be placed in multiple lists by including multiple next references in the node data structure, it would then be necessary to create separate routines to add or delete cells based on each field. It is possible to create additional linked lists of elements that use internal storage by using external storage, and having the cells of the additional linked lists store references to the nodes of the linked list containing the data.

In general, if a set of data structures needs to be included in linked lists, external storage is the best approach. If a set of data structures need to be included in only one linked list, then internal storage is slightly better, unless a generic linked list package using external storage is available. Likewise, if different sets of data that can be stored in the same data structure are to be included in a single linked list, then internal storage would be fine.

Another approach that can be used with some languages involves having different data structures, but all have the initial fields, including the next (and prev if double linked list) references in the same location. After defining separate structures for each type of data, a generic structure can be defined that contains the minimum amount of data shared by all the other structures and contained at the top (beginning) of the structures. Then generic routines can be created that use the minimal structure to perform linked list type operations, but separate routines can then handle the specific data. This approach is often used in message parsing routines, where several types of messages are received, but all start with the same set of fields, usually including a field for message type. The generic routines are used to add new messages to a queue when they are received, and remove them from the queue in order to process the message. The message type field is then used to call the correct routine to process the specific type of message.

Example of internal and external storage

Suppose you wanted to create a linked list of families and their members. Using internal storage, the structure might look like the following:

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

To print a complete list of families and their members using internal storage, we could write:

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

Using external storage, we would create the following structures:

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

To print a complete list of families and their members using external storage, we could write:

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

Notice that when using external storage, an extra step is needed to extract the record from the node and cast it into the proper data type. This is because both the list of families and the list of members within the family are stored in two linked lists using the same data structure (node), and this language does not have parametric types.

As long as the number of families that a member can belong to is known at compile time, internal storage works fine. If, however, a member needed to be included in an arbitrary number of families, with the specific number known only at run time, external storage would be necessary.

Speeding up search

Finding a specific element in a linked list, even if it is sorted, normally requires O(n) time (linear search). This is one of the primary disadvantages of linked lists over other data structures. In addition to the variants discussed above, below are two simple ways to improve search time.

In an unordered list, one simple heuristic for decreasing average search time is the move-to-front heuristic, which simply moves an element to the beginning of the list once it is found. This scheme, handy for creating simple caches, ensures that the most recently used items are also the quickest to find again.

Another common approach is to "index" a linked list using a more efficient external data structure. For example, one can build a red–black tree or hash table whose elements are references to the linked list nodes. Multiple such indexes can be built on a single list. The disadvantage is that these indexes may need to be updated each time a node is added or removed (or at least, before that index is used again).

Random-access lists

A random-access list is a list with support for fast random access to read or modify any element in the list.^[9] One possible implementation is a skew binary random-access list using the skew binary number system, which involves a list of trees with special properties; this allows worst-case constant time head/cons operations, and worst-case logarithmic time random access to an element by index.^[9] Random-access lists can be implemented as persistent data structures.^[9]

Random-access lists can be viewed as immutable linked lists in that they likewise support the same O(1) head and tail operations.^[9]

A simple extension to random-access lists is the min-list, which provides an additional operation that yields the minimum element in the entire list in constant time (without^{[clarification needed]} mutation complexities).^[9]

Related data structures

Both stacks and queues are often implemented using linked lists, and simply restrict the type of operations which are supported.

The skip list is a linked list augmented with layers of pointers for quickly jumping over large numbers of elements, and then descending to the next layer. This process continues down to the bottom layer, which is the actual list.

A binary tree can be seen as a type of linked list where the elements are themselves linked lists of the same nature. The result is that each node may include a reference to the first node of one or two other linked lists, which, together with their contents, form the subtrees below that node.

An unrolled linked list is a linked list in which each node contains an array of data values. This leads to improved cache performance, since more list elements are contiguous in memory, and reduced memory overhead, because less metadata needs to be stored for each element of the list.

A hash table may use linked lists to store the chains of items that hash to the same position in the hash table.

A heap shares some of the ordering properties of a linked list, but is almost always implemented using an array. Instead of references from node to node, the next and previous data indexes are calculated using the current data's index.

A self-organizing list rearranges its nodes based on some heuristic which reduces search times for data retrieval by keeping commonly accessed nodes at the head of the list.

Notes

References

Further reading

• Juan, Angel (2006). "Ch20 –Data Structures; ID06 - PROGRAMMING with JAVA (slide part of the book 'Big Java', by CayS. Horstmann)" (PDF). p. 3. Archived from the original (PDF) on 2012-01-06. Retrieved 2011-07-10.
• Black, Paul E. (2004-08-16). Pieterse, Vreda; Black, Paul E. (eds.). "linked list". Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. Retrieved 2004-12-14.
• Antonakos, James L.; Mansfield, Kenneth C., Jr. (1999). Practical Data Structures Using C/C++. Prentice-Hall. pp. 165–190. ISBN 0-13-280843-9.
• Collins, William J. (2005) [2002]. Data Structures and the Java Collections Framework. New York: McGraw Hill. pp. 239–303. ISBN 0-07-282379-8.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2003). Introduction to Algorithms. MIT Press. pp. 205–213, 501–505. ISBN 0-262-03293-7.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "10.2: Linked lists". Introduction to Algorithms (2nd ed.). MIT Press. pp. 204–209. ISBN 0-262-03293-7.
• Green, Bert F., Jr. (1961). "Computer Languages for Symbol Manipulation". IRE Transactions on Human Factors in Electronics (2): 3–8. doi:10.1109/THFE2.1961.4503292.
• McCarthy, John (1960). "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I". Communications of the ACM. 3 (4): 184. doi:10.1145/367177.367199.
• Knuth, Donald (1997). "2.2.3-2.2.5". Fundamental Algorithms (3rd ed.). Addison-Wesley. pp. 254–298. ISBN 0-201-89683-4.
• Newell, Allen; Shaw, F. C. (1957). "Programming the Logic Theory Machine". Proceedings of the Western Joint Computer Conference: 230–240.
• Parlante, Nick (2001). "Linked list basics" (PDF). Stanford University. Retrieved 2009-09-21.
• Sedgewick, Robert (1998). Algorithms in C. Addison Wesley. pp. 90–109. ISBN 0-201-31452-5.
• Shaffer, Clifford A. (1998). A Practical Introduction to Data Structures and Algorithm Analysis. New Jersey: Prentice Hall. pp. 77–102. ISBN 0-13-660911-2.
• Wilkes, Maurice Vincent (1964). "An Experiment with a Self-compiling Compiler for a Simple List-Processing Language". Annual Review in Automatic Programming. Pergamon Press. 4 (1): 1. doi:10.1016/0066-4138(64)90013-8.
• Wilkes, Maurice Vincent (1964). "Lists and Why They are Useful". Proceeds of the ACM National Conference, Philadelphia 1964. ACM (P–64): F1–1.
• Shanmugasundaram, Kulesh (2005-04-04). "Linux Kernel Linked List Explained". Retrieved 2009-09-21.

External links

Wikimedia Commons has media related to Linked lists.

• Description from the Dictionary of Algorithms and Data Structures
• Introduction to Linked Lists, Stanford University Computer Science Library
• Linked List Problems, Stanford University Computer Science Library
• Open Data Structures - Chapter 3 - Linked Lists, Pat Morin
• Patent for the idea of having nodes which are in several linked lists simultaneously (note that this technique was widely used for many decades before the patent was granted)