С точки зрения разработчика JavaScript
Я считаю, что в стремлении стать лучшим разработчиком важно время от времени выходить за рамки парадигмы вашего языка, чтобы больше узнавать о концепциях, которые в противном случае могут не появиться естественным образом в его контексте. В JavaScript одной из таких концепций является связанный список. Это краткое введение призвано предоставить (очень) широкий обзор того, что такое связанный список, а также его плюсы и минусы по сравнению с его более известным аналогом - массивом.
Основная концепция вычислений, которую разработчики языков высокого уровня склонны принимать как должное (в том числе и я), заключается в том, что структуры данных занимают место в памяти. Мы живем во времена беспрецедентного процветания памяти. Где вы можете сгенерировать столько сложных структур данных, сколько пожелает ваша маленькая душа, и никто не моргнет глазом. Этого не было во времена Безумного Макса низкоуровневых языков, таких как C. Раньше память была дефицитным ресурсом, который вам нужно было явно выделить, а затем очистить для использования в другие части вашей программы. Из-за нехватки памяти массивы должны были иметь фиксированную длину, приписываемую им при создании. Это означало, что добавление дополнительных элементов сверх первоначально определенной емкости массива было дорогостоящей операцией, поскольку это включало создание нового массива с большей емкостью и перемещение каждого элемента из старого массива в новый, включая вновь вставленный элемент. Кроме того, поскольку массивы непрерывны в памяти; Это означает, что они занимают непрерывный кусок, соответствующий длине массива, добавление элементов в начало или середину массива, независимо от того, есть ли у него емкость для нового элемента, может быть дорогостоящим. Здесь на помощь приходят связанные списки.
В общих чертах, вы можете рассматривать связанный список как альтернативу массиву. Вместо использования индексов каждый элемент или узел в связанном списке сам по себе является структурой данных, состоящей из значения и контрольной точки. к следующему узлу в списке. По сути, они действуют как направления к следующему узлу в памяти от предыдущего узла. Последний узел в списке указывает на нулевое значение. Существуют альтернативные, более сложные реализации связанного списка, называемые двусвязным списком, где каждый узел имеет две опорные точки (одну на предыдущий узел, а другую на следующий узел). Это позволяет выполнять двунаправленное перемещение вверх и вниз по списку. Если последний узел в списке имеет ссылку, указывающую на первый узел в списке, то это список с циклической связью.
Звучит ужасно похоже на массив, не так ли? Действительно, концептуально они тесно связаны. Однако у них действительно есть определенные отличия. Связанные списки не хранятся в последовательных ячейках памяти, как массивы, что означает, что первый узел может находиться в памяти очень далеко от второго узла и так далее. Это дает практическую выгоду, заключающуюся в том, что связанные списки не нуждаются в памяти, заранее выделенной для них при создании. Это сразу решает проблему дорогостоящих вставок, поскольку вам больше не нужно перемещать элементы, чтобы приспособить вставку. Просто установите узел непосредственно перед точкой вставки на новый узел, а вставленный узел должен указывать на узел, на который указывал предыдущий узел. Очень просто.
В обычных массивах, когда вы хотите вставить элемент где-нибудь внутри, вам нужно будет переместить все элементы после точки вставки. Это делает временную сложность для вставки в начало массива равной O (N) или линейной временной сложности. Для связанного списка сложность времени для добавления элемента в начало имеет O (1) или постоянную сложность времени, потому что вам не нужно сдвигать какие-либо элементы. Все, что вам нужно сделать, это создать новый узел со ссылкой на первый элемент в вашем существующем связанном списке. К сожалению, скорость связанного списка при вставке и удалении не влияет на скорость индексации. Поскольку каждый узел в связанном списке содержит только ссылку на следующий узел в списке, он фактически не содержит ссылки на то, где он находится. С другой стороны, массивы индексируются. Если вы хотите просмотреть третий, пятый или двадцать седьмой индекс, вы можете выполнить этот поиск за постоянное время, без необходимости rolodex через каждый предыдущий элемент в массиве. Из-за этих различий во временной сложности для индексации и вставки связанные списки могут быть более полезными, чем массивы в определенных ситуациях. В частности, связанные списки могут выступать в качестве строительных блоков для стеков и очередей, других специализированных сложных структур данных.
Массивы и связанные списки - две стороны одной медали. Каждый имеет свои практические преимущества. Оба являются списками элементов, но, хотя изменение массива сложнее, чем изменение связанного списка, доступ к каждому элементу в массиве проще, чем в связанном списке. Используя метафору, вы можете представить себе массив как поезд с пронумерованными вагонами, а связанный список как несвязанный караван тележек.
Они имеют схожую функциональность, как перемещение предметов, так и людей, но их легче добавить или убрать спереди, сзади или посередине фургона. Менять железнодорожные вагоны сложнее, поскольку добавление вагона требует, чтобы вы сдвигали все остальные вниз, изменяя номер вагона (индекс), как и вы. С нашим караваном мы можем без проблем вставлять, удалять, динамически увеличивать или уменьшать размер или даже разделять сегменты на их собственные караваны, поскольку они не связаны явно. Только не так быстро. Именно из-за гибкости каравана найти в нем определенную тележку так сложно. С нашим набором вагонов вы точно знаете, где находится каждый вагон по отношению к другим. Хочешь попасть в первый класс? Моисей переходит к машине 1. С караваном связанного списка положение более шаткое. Расстояние между первым и вторым караваном может быть разным, и, чтобы найти человека, продающего воду, вам придется начинать с головы и продвигаться от одной тележки к другой, пока не найдете ее. При этом все модификации связанного списка в реальном времени также требуют поиска. Если вы хотите добавить новую голову каравана, не проблема. Просто поставьте его впереди. Однако, если вы хотите добавить его где-то посередине, вам нужно будет пройти по линии, пока не найдете место, куда вы хотите его вставить.
Каждая структура данных имеет свои преимущества и недостатки. Вам как разработчику решать, что лучше всего подходит для конкретной проблемы, с которой вы сталкиваетесь.
использованная литература
