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

Связный список: структура данных в программировании. Узлы содержат данные и ссылку на следующий элемент. Эффективное добавление/удаление данных.

18 мин чтения

100%

Источник: Linked list — Wikipedia

Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.

Содержание

Введение

Структура данных с узлами, указывающими на следующий узел.

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

In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence. In its most basic form, each node contains data, and a reference (in other words, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. More complex variants add additional links, allowing more efficient insertion or removal of nodes at arbitrary positions. A drawback of linked lists is that data access time is linear in respect to the number of nodes in the list. Because nodes are serially linked, accessing any node requires that the prior node be accessed beforehand (which introduces difficulties in pipelining). Faster access, such as random access, is not feasible. Arrays have better cache locality compared to linked lists. Linked lists are among the simplest and most common data structures. They can be used to implement several other common abstract data types, including lists, stacks, queues, associative arrays, and S expressions, though it is not uncommon to implement those data structures directly without using a linked list as the basis. The principal benefit of a linked list over a conventional array is that the list elements can be easily inserted or removed without reallocation or reorganization of the entire structure because the data items do not need to be stored contiguously in memory or on disk, while restructuring an array at run time is a much more expensive operation. Linked lists allow insertion and removal of nodes at any point in the list, and allow doing so with a constant number of operations by keeping the link previous to the link being added or removed in memory during list traversal. On the other hand, since simple linked lists by themselves do not allow random access to the data or any form of efficient indexing, many basic operations—such as obtaining the last node of the list, finding a node that contains a given datum, or locating the place where a new node should be inserted—may require iterating through most or all of the list elements.

История

Связанные списки были разработаны в 1955–1956 годах Алленом Ньюэллом, Клиффом Шоу и Гербертом А. Саймоном в RAND Corporation и Университете Карнеги — Меллона в качестве основной структуры данных для их языка обработки информации (IPL). Авторы использовали IPL для разработки нескольких ранних программ искусственного интеллекта, включая Машину логической теории, Универсальный решатель задач и компьютерную шахматную программу. Отчеты об их работе появились в IRE Transactions on Information Theory в 1956 году, а также в материалах нескольких конференций с 1957 по 1959 год, включая Proceedings of the Western Joint Computer Conference в 1957 и 1958 годах и Information Processing (Материалы первой Международной конференции ЮНЕСКО по обработке информации) в 1959 году. Теперь уже классическая диаграмма, состоящая из блоков, представляющих узлы списка со стрелками, указывающими на последующие узлы списка, появилась в работе Ньюэлла и Шоу "Программирование Машины логической теории" в Proc. WJCC, февраль 1957 года. Ньюэлл и Саймон были удостоены премии ACM Turing в 1975 году за "основной вклад в искусственный интеллект, психологию человеческого познания и обработку списков". Проблема машинного перевода в области обработки естественного языка привела Виктора Ингве из Массачусетского технологического института (MIT) к использованию связанных списков в качестве структур данных в его языке программирования COMIT для компьютерных исследований в области лингвистики. Отчет об этом языке под названием "Язык программирования для машинного перевода" был опубликован в журнале Mechanical Translation в 1958 году. Еще одним ранним примером использования связанных списков был случай с Хансом Петером Луном, который в январе 1953 года написал внутренний меморандум IBM, предлагающий использовать связанные списки в цепных хеш-таблицах. LISP, расшифровывающийся как процессор списков, был создан Джоном Маккарти в 1958 году, когда он работал в MIT, а в 1960 году он опубликовал его описание в статье в Communications of the ACM под названием "Рекурсивные функции символических выражений и их машинное вычисление, часть I". Связанный список является одной из основных структур данных LISP. К началу 1960-х годов полезность как связанных списков, так и языков, использующих эти структуры в качестве основного представления данных, была хорошо установлена. Берт Грин из Лаборатории Линкольна MIT опубликовал обзорную статью под названием "Компьютерные языки для манипулирования символами" в IRE Transactions on Human Factors in Electronics в марте 1961 года, в которой обобщены преимущества подхода с использованием связанных списков. Более поздняя обзорная статья "Сравнение языков обработки списков" авторства Боброу и Рафаэля появилась в Communications of the ACM в апреле 1964 года. Несколько операционных систем, разработанных Technical Systems Consultants (первоначально базировавшихся в Вест-Лафайетте, штат Индиана, а затем в Чапел-Хилл, штат Северная Каролина), использовали одинарно связанные списки в качестве файловых структур. Запись в каталоге указывала на первый сектор файла, а последующие части файла находились путем обхода указателей. Системы, использующие эту технику, включали Flex (для процессора Motorola 6800), mini Flex (тот же процессор) и Flex9 (для процессора Motorola 6809). Вариант, разработанный TSC для и продаваемый Smoke Signal Broadcasting в Калифорнии, использовал двойные связанные списки аналогичным образом. Операционная система TSS/360, разработанная IBM для машин System 360/370, использовала двойной связанный список для своего каталога файловой системы. Структура каталогов была аналогична Unix, где каталог мог содержать файлы и другие каталоги и иметь любую глубину.

Linked lists were developed in 1955–1956, by Allen Newell, Cliff Shaw and Herbert A. Simon at RAND Corporation and Carnegie Mellon University as the primary data structure for their Information Processing Language (IPL). IPL was used by the authors to develop several early artificial intelligence programs, including the Logic Theory Machine, the General Problem Solver, and a computer chess program. Reports on their work appeared in IRE Transactions on Information Theory in 1956, and several conference proceedings from 1957 to 1959, including Proceedings of the Western Joint Computer Conference in 1957 and 1958, and Information Processing (Proceedings of the first UNESCO International Conference on Information Processing) in 1959. The now classic diagram consisting of blocks representing list nodes with arrows pointing to successive list nodes appears in "Programming the Logic Theory Machine" by Newell and Shaw in Proc. WJCC, February 1957. Newell and Simon were recognized with the ACM Turing Award in 1975 for having "made basic contributions to artificial intelligence, the psychology of human cognition, and list processing". The problem of machine translation for natural language processing led Victor Yngve at Massachusetts Institute of Technology (MIT) to use linked lists as data structures in his COMIT programming language for computer research in the field of linguistics. A report on this language entitled "A programming language for mechanical translation" appeared in Mechanical Translation in 1958. Another early appearance of linked lists was by Hans Peter Luhn who wrote an internal IBM memorandum in January 1953 that suggested the use of linked lists in chained hash tables. LISP, standing for list processor, was created by John McCarthy in 1958 while he was at MIT and in 1960 he published its design in a paper in the Communications of the ACM, entitled "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I". One of LISP's major data structures is the linked list. By the early 1960s, the utility of both linked lists and languages which use these structures as their primary data representation was well established. Bert Green of the MIT Lincoln Laboratory published a review article entitled "Computer languages for symbol manipulation" in IRE Transactions on Human Factors in Electronics in March 1961 which summarized the advantages of the linked list approach. A later review article, "A Comparison of list processing computer languages" by Bobrow and Raphael, appeared in Communications of the ACM in April 1964. Several operating systems developed by Technical Systems Consultants (originally of West Lafayette Indiana, and later of Chapel Hill, North Carolina) used singly linked lists as file structures. A directory entry pointed to the first sector of a file, and succeeding portions of the file were located by traversing pointers. Systems using this technique included Flex (for the Motorola 6800 CPU), mini Flex (same CPU), and Flex9 (for the Motorola 6809 CPU). A variant developed by TSC for and marketed by Smoke Signal Broadcasting in California, used doubly linked lists in the same manner. The TSS/360 operating system, developed by IBM for the System 360/370 machines, used a double linked list for their file system catalog. The directory structure was similar to Unix, where a directory could contain files and other directories and extend to any depth.

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

Каждый элемент в связном списке часто называется "элементом" или "узлом". Поле каждого узла, содержащее адрес следующего узла, обычно называется "следующей ссылкой" или "следующим указателем". Остальные поля известны как поля "данные", "информация", "значение", "содержимое" или "полезная нагрузка". "Голова" списка – это его первый узел. "Хвост" списка может относиться либо к остальной части списка после головы, либо к последнему узлу в списке. В Lisp и некоторых производных языках следующий узел может называться "cdr" (произносится как ) списка, а полезная нагрузка головного узла – "car".

Список с двойным ссылкой

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

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

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

Циркулярный перечень

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

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

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

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

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

Ссылка на хэш

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

Список ручек

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

Сочетание альтернатив

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

Компромиссные меры

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

Ссылки на списки против динамических массивов

Динамический массив — это структура данных, которая выделяет все элементы последовательно в памяти и хранит текущее количество элементов. Если пространство, зарезервированное для динамического массива, исчерпано, происходит его перераспределение и (возможно) копирование, что является дорогостоящей операцией. Связные списки обладают рядом преимуществ перед динамическими массивами. Вставка или удаление элемента в определенной точке списка, при условии, что у нас уже есть указатель на узел (перед удаляемым или перед точкой вставки), выполняется за постоянное время (в противном случае, без этой ссылки, за O(n)). В то время как вставка в динамический массив в произвольном месте потребует перемещения в среднем половины элементов, а в худшем случае — всех элементов. Хотя можно "удалить" элемент из массива за постоянное время, просто пометив его ячейку как "свободную", это приводит к фрагментации, которая замедляет итерацию. Более того, в связный список можно вставить произвольное количество элементов, ограниченное только объемом доступной памяти, в то время как динамический массив в конечном итоге заполнит базовую структуру данных массива и потребует перераспределения — дорогостоящей операции, которая может оказаться невозможной при фрагментированной памяти. Однако стоимость перераспределения можно усреднить по вставкам, и стоимость вставки из-за перераспределения все равно будет амортизированной O(1). Это полезно при добавлении элементов в конец массива, но вставка в (или удаление из) средних позиций по-прежнему обходится дорого из-за необходимости перемещения данных для сохранения непрерывности. Массив, из которого удалено много элементов, также может потребовать изменения размера, чтобы избежать излишнего расходования памяти. С другой стороны, динамические массивы (а также массивы фиксированного размера) обеспечивают произвольный доступ за постоянное время, в то время как связные списки допускают только последовательный доступ к элементам. В односвязных списках можно легко перемещаться только в одном направлении. Это делает связные списки непригодными для приложений, где требуется быстрый поиск элемента по его индексу, например, для сортировки кучей. Последовательный доступ к массивам и динамическим массивам также часто быстрее, чем к связным спискам, поскольку они обладают оптимальной локальностью ссылок и эффективно используют кэш данных. Еще одним недостатком связных списков является дополнительное хранилище, необходимое для ссылок, что часто делает их непрактичными для списков небольших элементов данных, таких как символы или булевы значения, поскольку накладные расходы на хранение ссылок могут в два или более раза превышать размер самих данных. В отличие от этого, динамический массив требует только места для самих данных (и небольшого объема служебных данных). Выделение памяти отдельно для каждого нового элемента также может быть медленным и неэффективным при использовании наивного аллокатора, проблема, обычно решаемая с помощью пулов памяти. Некоторые гибридные решения пытаются объединить преимущества обоих представлений. Развернутые связные списки хранят несколько элементов в каждом узле списка, повышая производительность кэша и снижая накладные расходы на память для ссылок. CDR-кодирование делает то же самое, заменяя ссылки фактическими данными, на которые они указывают, что расширяется за пределы записи, содержащей ссылку. Хорошим примером, демонстрирующим преимущества и недостатки динамических массивов и связных списков, является реализация программы, решающей задачу Иосифа Флавия. Задача Иосифа Флавия — это метод выбора, при котором группа людей стоит в кругу. Начиная с заранее определенного человека, можно отсчитывать n человек по кругу. Как только достигнут n-й человек, его следует удалить из круга, и участники должны сомкнуть круг. Процесс повторяется, пока не останется только один человек. Этот человек побеждает в выборах. Это демонстрирует сильные и слабые стороны связного списка и динамического массива: если рассматривать людей как связанные узлы в круговом связном списке, то становится очевидным, насколько легко связный список может удалять узлы (поскольку ему нужно только переставить ссылки на другие узлы). Однако связному списку будет сложно найти следующего человека для удаления, и ему придется просматривать список, пока он его не найдет. Динамический массив, с другой стороны, будет испытывать трудности при удалении узлов (или элементов), поскольку он не может удалить один узел, не сдвигая все элементы списка на одну позицию вверх. Однако найти n-го человека в круге, обратившись к нему напрямую по его позиции в массиве, чрезвычайно просто. Задача ранжирования списка связана с эффективным преобразованием представления связного списка в массив. Хотя для обычного компьютера она тривиальна, решение этой задачи параллельным алгоритмом является сложным и было предметом многочисленных исследований. Сбалансированное дерево имеет аналогичные шаблоны доступа к памяти и накладные расходы на хранение, что и связный список, но обеспечивает гораздо более эффективный поиск, занимающий O(log n) времени вместо O(n) для произвольного доступа. Однако операции вставки и удаления более затратны из-за накладных расходов на манипуляции с деревом для поддержания баланса. Существуют схемы, позволяющие деревьям автоматически поддерживать сбалансированное состояние: AVL-деревья или красно-черные деревья.

A dynamic array is a data structure that allocates all elements contiguously in memory, and keeps a count of the current number of elements. If the space reserved for the dynamic array is exceeded, it is reallocated and (possibly) copied, which is an expensive operation. Linked lists have several advantages over dynamic arrays. Insertion or deletion of an element at a specific point of a list, assuming that we have indexed a pointer to the node (before the one to be removed, or before the insertion point) already, is a constant time operation (otherwise without this reference it is O(n)), whereas insertion in a dynamic array at random locations will require moving half of the elements on average, and all the elements in the worst case. While one can "delete" an element from an array in constant time by somehow marking its slot as "vacant", this causes fragmentation that impedes the performance of iteration. Moreover, arbitrarily many elements may be inserted into a linked list, limited only by the total memory available; while a dynamic array will eventually fill up its underlying array data structure and will have to reallocate—an expensive operation, one that may not even be possible if memory is fragmented, although the cost of reallocation can be averaged over insertions, and the cost of an insertion due to reallocation would still be amortized O(1). This helps with appending elements at the array's end, but inserting into (or removing from) middle positions still carries prohibitive costs due to data moving to maintain contiguity. An array from which many elements are removed may also have to be resized in order to avoid wasting too much space. On the other hand, dynamic arrays (as well as fixed size array data structures) allow constant time random access, while linked lists allow only sequential access to elements. Singly linked lists, in fact, can be easily traversed in only one direction. This makes linked lists unsuitable for applications where it's useful to look up an element by its index quickly, such as heapsort. Sequential access on arrays and dynamic arrays is also faster than on linked lists on many machines, because they have optimal locality of reference and thus make good use of data caching. Another disadvantage of linked lists is the extra storage needed for references, which often makes them impractical for lists of small data items such as characters or Boolean values, because the storage overhead for the links may exceed by a factor of two or more the size of the data. In contrast, a dynamic array requires only the space for the data itself (and a very small amount of control data). It can also be slow, and with a naïve allocator, wasteful, to allocate memory separately for each new element, a problem generally solved using memory pools. Some hybrid solutions try to combine the advantages of the two representations. Unrolled linked lists store several elements in each list node, increasing cache performance while decreasing memory overhead for references. CDR coding does both these as well, by replacing references with the actual data referenced, which extends off the end of the referencing record. A good example that highlights the pros and cons of using dynamic arrays vs. linked lists is by implementing a program that resolves the Josephus problem. The Josephus problem is an election method that works by having a group of people stand in a circle. Starting at a predetermined person, one may count around the circle n times. Once the nth person is reached, one should remove them from the circle and have the members close the circle. The process is repeated until only one person is left. That person wins the election. This shows the strengths and weaknesses of a linked list vs. a dynamic array, because if the people are viewed as connected nodes in a circular linked list, then it shows how easily the linked list is able to delete nodes (as it only has to rearrange the links to the different nodes). However, the linked list will be poor at finding the next person to remove and will need to search through the list until it finds that person. A dynamic array, on the other hand, will be poor at deleting nodes (or elements) as it cannot remove one node without individually shifting all the elements up the list by one. However, it is exceptionally easy to find the nth person in the circle by directly referencing them by their position in the array. The list ranking problem concerns the efficient conversion of a linked list representation into an array. Although trivial for a conventional computer, solving this problem by a parallel algorithm is complicated and has been the subject of much research. A balanced tree has similar memory access patterns and space overhead to a linked list while permitting much more efficient indexing, taking O(log n) time instead of O(n) for a random access. However, insertion and deletion operations are more expensive due to the overhead of tree manipulations to maintain balance. Schemes exist for trees to automatically maintain themselves in a balanced state: AVL trees or red–black trees.

Линейные списки с отдельными ссылками и другие списки

В то время как двойные и циклические списки имеют преимущества перед односвязными линейными списками, линейные списки предлагают некоторые преимущества, которые делают их предпочтительнее в определенных ситуациях. Односвязный линейный список является рекурсивной структурой данных, поскольку он содержит указатель на объект меньшего размера того же типа. По этой причине многие операции над односвязными линейными списками (такие как объединение двух списков или перечисление элементов в обратном порядке) часто имеют очень простые рекурсивные алгоритмы, значительно более простые, чем любое решение с использованием итеративных команд. Хотя эти рекурсивные решения можно адаптировать для двойных и циклических списков, процедуры обычно требуют дополнительных аргументов и более сложных базовых случаев. Линейные односвязные списки также допускают совместное использование хвоста, то есть использование общей конечной части подсписка в качестве конечной части двух разных списков. В частности, если новый узел добавляется в начало списка, исходный список остается доступным в качестве хвоста нового – простой пример устойчивой структуры данных. Это не относится к другим вариантам: узел не может одновременно принадлежать двум различным циклическим или двусвязным спискам. В частности, конечные сигнальные узлы могут совместно использоваться между односвязными нециклическими списками. Один и тот же конечный сигнальный узел может использоваться для каждого такого списка. Например, в Lisp каждый корректный список заканчивается ссылкой на специальный узел, обозначаемый nil. Преимущества более сложных вариантов часто ограничиваются сложностью алгоритмов, а не их эффективностью. Циклический список, в частности, обычно можно эмулировать линейным списком вместе с двумя переменными, указывающими на первый и последний узлы, без дополнительных затрат.

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

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

Круговые и линейные связи

Кругосвязанный список может быть естественным выбором для представления массивов, имеющих циклическую природу, например, вершин многоугольника, пула буферов, используемых и освобождаемых в порядке FIFO ("первый пришел – первый ушел"), или набора процессов, которым требуется разделение времени по принципу циклического перебора. В этих приложениях указатель на любой узел служит дескриптором для всего списка. В случае кругового списка, указатель на последний узел обеспечивает легкий доступ к первому узлу, следуя по одной ссылке. Таким образом, в приложениях, требующих доступа к обоим концам списка (например, при реализации очереди), циклическая структура позволяет управлять структурой с помощью одного указателя, вместо двух. Круговой список можно разделить на два круговых списка за постоянное время, указав адреса последнего узла каждой части. Операция заключается в обмене содержимым полей ссылок этих двух узлов. Применение той же операции к любым двум узлам в двух различных списках объединяет эти списки в один. Это свойство значительно упрощает некоторые алгоритмы и структуры данных, такие как двуреберная и граничная ребра. Самым простым представлением пустого кругового списка (когда это имеет смысл) является нулевой указатель, указывающий на отсутствие узлов в списке. Без этого выбора многим алгоритмам пришлось бы проверять этот особый случай и обрабатывать его отдельно. Напротив, использование нулевого указателя для обозначения пустого линейного списка более естественно и часто создает меньше особых случаев. Для некоторых приложений может быть полезно использовать односвязные списки, которые могут переключаться между круговым и линейным состоянием, или даже быть круговыми с линейным начальным сегментом. Алгоритмы для поиска или других операций с такими списками должны принимать меры предосторожности, чтобы избежать случайного попадания в бесконечный цикл. Один из известных методов – использование второго указателя, перемещающегося по списку с половинной или удвоенной скоростью, и если оба указателя встретятся в одном узле, это означает, что обнаружен цикл.

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

Узел-страж может упростить некоторые операции со списком, гарантируя существование следующего или предыдущего узла для каждого элемента и обеспечивая наличие как минимум одного узла даже в пустых списках. Также можно использовать узел-страж в конце списка с соответствующим полем данных, чтобы избежать проверок на конец списка. Например, при сканировании списка в поисках узла со значением x, установка поля данных узла-стража в x избавляет от необходимости проверять конец списка внутри цикла. Другой пример – объединение двух отсортированных списков: если поля данных узлов-стражей установлены в +∞, выбор следующего выходного узла не требует специальной обработки для пустых списков. Однако узлы-стражи занимают дополнительное место (особенно в приложениях, работающих с множеством коротких списков), и могут усложнять другие операции (например, создание нового пустого списка). Если же кольцевой список используется лишь для имитации линейного списка, можно избежать части этой сложности, добавив один узел-страж в каждый список между последним и первым узлами данных. В этом случае пустой список состоит только из узла-стража, указывающего на себя по ссылке `next`. Обработчик списка должен быть указателем на последний узел данных перед узлом-стражем, если список не пуст, или на сам узел-страж, если список пуст. Тот же прием можно использовать для упрощения обработки двусвязного линейного списка, преобразовав его в двусвязный кольцевой список с одним узлом-стражем. Однако в этом случае обработчик должен быть единственным указателем на сам фиктивный узел.

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

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

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

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