Несколько месяцев назад я был в блаженном неведении о связанных списках, структурах данных и алгоритмах. Однако по мере приближения моего окончания курса веб-разработки я знаю, что они будут важным фактором в определении направления моей карьеры. Если вы подумываете о карьере в разработке программного обеспечения или даже хотите повысить свой уровень в своей карьере, то эта статья для вас.
Что такое связанные списки и структуры данных?
В компьютерных науках связный список — это линейный набор элементов данных, порядок которых не определяется их физическим размещением в памяти. Вместо этого каждый элемент указывает на следующий. Это структура данных, состоящая из набора узлов, которые вместе представляют собой последовательность. — Википедия
Итак, что именно это означает? В основе информатики лежат концепции структур данных и алгоритмов. Структуры данных описывают, как информация организована и хранится в компьютерной системе, с целью ее структурирования таким образом, чтобы к ней можно было получить доступ и манипулировать ею максимально эффективно.
Алгоритм, относящийся к структурам данных, представляет собой набор инструкций, которые мы предоставляем компьютеру для работы с этими данными. Структуры данных бывают разных форм и размеров, каждая из которых имеет свои варианты использования, но основными формами являются линейная, хэш-структура, дерево и график. В этой статье мы сосредоточимся в основном на линейной форме и, в частности, на связанных списках.
Связанные списки — цепочка другого вида
Естественно, впервые услышав термин «связанный список», представить себе цепочку. В нашей повседневной жизни цепи, с которыми мы сталкиваемся, состоят из смежных звеньев, которые крепко держатся друг за друга. В информатике у этих цепей есть начало и конец, называемые головой и хвостом соответственно (хвост также может относиться ко всем звеньям, следующим за головой). Однако эти связи, называемые узлами, не связаны ни в каком физическом или пространственном смысле и действуют скорее как подсказки в охоте за мусором, где каждый узел указывает нам на следующий и содержит свой собственный набор данных.
В случае односвязного списка нас указывают только в направлении следующего узла, и если вы не отслеживали, где вы нашли предыдущие узлы, мы можем двигаться только вперед. Каждый узел не предлагает никакой информации о других, кроме того, где найти следующий, и мы никогда не можем быть уверены, что нашли все узлы, которые ищем, пока не найдем последний, и он не скажет нам, что больше нет. после этого.
Двусвязные списки почти такие же, за исключением того, что они указывают как на предыдущий, так и на следующий узлы, что позволяет нам перемещаться вперед или назад по цепочке. Многосвязные списки больше похожи на выбор собственного приключенческого романа, где каждый узел дает нам несколько вариантов того, как мы перемещаемся по списку, что может действовать как внутренний механизм упорядочения. Существуют также циклически связанные списки, в которых «последний» узел указывает на «первый» (и наоборот в случае двусвязных списков), и, подобно змее, проглатывающей собственный хвост, возникают некоторые вопросы о том, где находится циклический список. начинается и заканчивается.
Другими типами связанных списков являются стеки и очереди. Стеки работают по принципу LIFO (последний пришел, первый ушел) и очереди по принципу FIFO (первым пришел, первым ушел). Это означает, что они ограничивают свои операции элементами только в начале или конце списка. Стеки используют операции «push» и «pop» для добавления или удаления элементов из вершины стека, а очереди «ставят в очередь» и «извлекают» элементы из их соответствующих концов. Повседневными примерами этого могут быть стопка тарелок или очередь в банке. Подобно стопке тарелок или очереди людей, сразу видно, какое блюдо находится наверху, или кто идет следующим в очереди и с чего начать выстраиваться в очередь.
Когда вы стоите в очереди, вы можете не знать точно, когда будет ваша очередь, но вы точно знаете, что она будет после человека перед вами и перед человеком позади вас. В этих случаях прерывание очереди считается очень грубым, и вы, скорее всего, получите немедленный негативный отзыв. То же самое и со стопкой тарелок, очень легко взять одну сверху, но если вы попытаетесь взять одну из середины, все рухнет.
Компромиссы
Основным недостатком связанных списков является то, что для извлечения данных из определенного узла список всегда должен проходиться, начиная с одного из концов. Это позволяет быстро получить доступ к началу или концу списка, но создает потенциальную проблему для узлов в середине. В худшем случае данные, которые вы ищете, будут на противоположном конце от того, где вы начали, или вообще не будут представлены, но каждый узел все равно должен быть проверен. Это означает, что к узлам нельзя обращаться вне очереди. Для очень больших наборов данных может потребоваться много времени, чтобы найти то, что вы ищете, по сравнению с чем-то вроде динамического массива или хэш-таблицы, которая напрямую предоставляет адреса для поиска определенного узла. Однако компромисс, связанный с более медленным поиском, дает нам гораздо более эффективный метод добавления или удаления узлов.
Как и в случае с цепочкой, процесс добавления или удаления узла включает в себя только разрыв связей между двумя звеньями и добавление или удаление любой желаемой длины цепи. Более того, односвязные списки могут даже иметь общий хвост другого списка без внесения каких-либо изменений в исходный список. Количество требуемых изменений варьируется в зависимости от разновидности связанных списков, но масштабируется линейно с размером набора данных.
Сравните это с чем-то вроде динамического массива или хеш-таблицы, которые больше похожи на вязаную одежду, где даже небольшое изменение требует распутывания всей структуры и последующей ее сборки.
В конце концов, существует множество различных структур данных, каждая из которых имеет свои сильные и слабые стороны, но единого решения, подходящего для всех, не существует. В основе нашего цифрового мира лежит постоянно растущая масса данных. По мере того, как эти данные раздуваются до монументальных размеров, нам необходимо организовать их таким образом, чтобы мы могли эффективно их использовать. Мы используем технологии, чтобы общаться с окружающими нас людьми, находить товары и услуги, а теперь еще больше, чем когда-либо, для работы.
Во время написания и исследования этой статьи я узнал несколько новых концепций, и я надеюсь, что вы тоже узнали или, по крайней мере, получили новый взгляд на структуры данных.
