Связанный список в программировании - одна из важнейших структур, данных, в которой элементы линейно упорядочены, но порядок определяется не номерами элементов, а указателями, входящих в состав элементов списка и указывают на следующий за данным элемент или на следующий и предыдущий элементы. Список имеет «голову» - первый элемент и «хвост» - последний элемент.
Связанные списки имеют серию преимуществ по сравнению с массивами. В частности, в них гораздо эффективнее (за время О (1), т.е. независимо от количества элементов) выполняются процедуры добавления и удаления элементов. Зато, массивы намного лучше в операциях, требующих непосредственного доступа к каждому элементу, что в случае со связанными списками невозможно и требует последовательного перебора всех элементов, предшествующих данному.
Разновидности связанных списков
Односторонне связанные списки
В одностороннем связанном списке, который является простейшим видом связанных списков, каждый элемент состоит из двух полей: data или данных, и указателя next на следующий элемент. Если указатель не указывает на другой элемент (иначе: next = NULL), то считается, что данный элемент - последний в списке.
Двусторонний связанный список
В Двустороннем связанном списке, элемент состоит из трех полей - указателя на предыдущий элемент prev, поля данных data и указателя next на следующий элемент. Если prev = NULL, то у элемента нет предшественника (т.е. он является «головой» списка), если next = NULL, то у него нет преемника («хвост» списка).
Кольцевой список
В кольцевом списке первый и последний элемент связаны. То есть, поле prev головы списка указывает на хвост списка, а поле next хвоста списка указывает на голову списка.
Применение списков
Списки интенсивно применяются в программировании как самостоятельные структуры. Также на их основе могут строиться более сложные структуры данных, такие как деревья. На базе списков также могут быть реализованы стеки и очереди.
Преимущества и недостатки
В общем случае, если необходимо оперировать с динамическими множествами, где присутствуют интенсивные операции по установке и извлечении элементов, существуют достаточно убедительные аргументы для подключения связанных списков.
Связанные списки и массивы
Списки имеют некоторые преимущества над массивами. Они достаточно эффективны в отношении операций добавления или удаления элемента в произвольном месте списка, выполняя их за постоянное время, тогда как массивы для этого требуют времени O (n), то есть время возрастает с ростом количества элементов массива.
В списках также не существует проблемы расширения, которая рано или поздно возникает в массивах фиксированного размера, когда возникает необходимость включить в него дополнительные элементы. Точно так, фиксированный массив, из которого были удалены многие элементы (или они просто не используются), является очень неэффективным с точки зрения использования памяти. Функционирование списков возможно в ситуации, когда память компьютера фрагментирована, тогда как массивы преимущественно требуют непрерывной области для хранения.
Кроме того, массивы позволяют непосредственный доступ к любому элементу. Односторонне связанные списки требуют прохождения всех предыдущих элементов. Это приводит к сложностям применения списков в задачах, где необходимо быстро находить элемент по его индексу, например в алгоритмах сортировки. Кэширование списков в таких случаях почти не дает эффекта.
Другим очевидным недостатком списков является необходимость вместе с полезной информацией дополнительно хранить информацию об указателях, что сказывается на эффективности использования памяти этими структурами.
Двустороннее и одностороннее связывание
Двустороннее связывание требует больше памяти на элемент и больших вычислительных затрат на выполнение элементарных операций. Но такими списками легче манипулировать, потому что они позволяют прохождение по списку в обоих направлениях, что является необходимым условием функционирования некоторых алгоритмов.
