Информация повсюду вокруг нас.
В мире программного обеспечения способы, которые мы выбираем для организации нашей информации, - это половина дела. Но вот в чем дело: существует так много способов решить проблему. А когда дело доходит до организации данных, есть множество инструментов, которые могут сработать. Хитрость заключается в том, чтобы знать, какой инструмент правильный использовать.
Независимо от того, на каком языке мы начинаем кодировать, в первую очередь мы сталкиваемся с структурами данных, которые представляют собой различные способы организации наших данных; переменные, массивы , хэши, и объекты - это все типы структур данных. Но это все еще лишь верхушка айсберга, когда дело доходит до структур данных; есть намного больше, некоторые из которых начинают казаться сверхсложными, чем больше вы о них слышите.
Одной из таких сложных вещей для меня всегда были связанные списки. Я знаю о связанных списках уже несколько лет, но никогда не могу держать их в голове. Я думаю о них только тогда, когда готовлюсь к техническому собеседованию (а иногда и во время его проведения), и кто-то спрашивает меня о них. Я проведу небольшое исследование и думаю, что понимаю, о чем они, но через несколько недель я снова их забываю. Все это довольно неэффективно, и все это связано с тем, что я знаю, что они существуют, но принципиально не понимаю их! Итак, пришло время изменить это и ответить на вопрос: что вообще такое связанный список?
Линейные структуры данных
Если мы действительно хотим понять основы связанных списков, важно поговорить о том, тип их структуры данных.
Одной из характеристик связанных списков является то, что они являются линейными структурами данных, что означает, что существует последовательность и порядок их построения и обхода. Мы можем думать о линейной структуре данных как о игре в классики: чтобы добраться до конца списка, мы должны пройти все элементы в списке по порядку или последовательно . Однако линейные структуры противоположны нелинейным структурам. В нелинейных структурах данных элементы не должны располагаться по порядку, что означает, что мы можем перемещаться по структуре данных непоследовательно.
Возможно, мы не всегда осознаем это, но все мы ежедневно работаем с линейными и нелинейными структурами данных! Когда мы организуем наши данные в хэши (иногда называемые словарями), мы реализуем нелинейную структуру данных. Деревья и графики также являются нелинейными структурами данных, которые мы просматриваем по-разному, но мы поговорим о них более подробно позже в этом году.
Точно так же, когда мы используем массивы в нашем коде, мы реализуем линейную структуру данных! Может быть полезно думать о массивах и связанных списках как о схожих способах упорядочивания данных. В обеих этих структурах порядок. Но чем отличаются массивы и связанные списки?
Управление памятью
Самым большим отличием массивов от связанных списков является то, как они используют память на наших машинах. Тем из нас, кто работает с динамически типизированными языками, такими как Ruby, JavaScript или Python, не нужно думать о том, сколько памяти использует массив, когда мы пишем наш код на повседневной основе, потому что есть несколько уровней абстракции, которые в конечном итоге нам совсем не нужно беспокоиться о выделении памяти.
Но это не значит, что выделения памяти не происходит! Абстракция - это не волшебство, это просто скрытие вещей, которые вам не нужно постоянно видеть или с которыми не нужно иметь дело. Даже если нам не нужно думать о распределении памяти при написании кода, если мы хотим по-настоящему понять, что происходит в связном списке и что делает его мощным, мы должны перейти к элементарному уровню.
Мы уже узнали о двоичном формате и о том, как данные можно разбить на биты и байты. Как символы, числа, слова, предложения требуют байтов памяти для их представления, так и структуры данных.
Когда создается массив, ему требуется определенный объем памяти. Если бы у нас было 7 букв, которые нам нужно было сохранить в массиве, нам потребовалось бы 7 байтов памяти для представления этого массива. Но нам понадобится вся эта память в одном непрерывном блоке. Другими словами, нашему компьютеру необходимо найти 7 свободных байтов памяти, один байт рядом с другим, все вместе, в одном месте.
С другой стороны, когда создается связанный список, ему не нужны 7 байтов памяти в одном месте. Один байт мог где-то жить, а следующий байт мог вообще храниться в другом месте памяти! Связанные списки не должны занимать ни одного блока памяти; вместо этого память, которую они используют, может быть разбросана по всему.
Фундаментальное различие между массивами и связанными списками заключается в том, что массивы являются статическими структурами данных, а связанные списки являются динамические структуры данных. Статическая структура данных требует, чтобы все ее ресурсы были выделены при создании структуры; это означает, что даже если структура должна была увеличиваться или уменьшаться в размере, а элементы должны были быть добавлены или удалены, она все равно всегда нуждается в заданном размере и объеме памяти. Если необходимо добавить дополнительные элементы в статическая структура данных и у нее недостаточно памяти, вам нужно будет скопировать данные этого массива, например, и воссоздать его с большим объемом памяти, чтобы вы могли добавлять в него элементы.
С другой стороны, динамическая структура данных может уменьшаться и увеличиваться в памяти. Ему не нужно выделять определенный объем памяти, чтобы существовать, его размер и форма могут изменяться, а также может изменяться объем памяти, который ему необходим.
К настоящему времени мы уже можем начать видеть некоторые важные различия между массивами и связанными списками. Но возникает вопрос: что позволяет связному списку иметь разбросанную повсюду память? Чтобы ответить на этот вопрос, нам нужно посмотреть, как структурирован связанный список.
Части связанного списка
Связанный список может быть маленьким или огромным, но независимо от размера составляющие его части на самом деле довольно просты. Связанный список состоит из серии узлов, которые являются элементами списка.
Отправной точкой списка является ссылка на первый узел, который называется заголовком. Почти все связанные списки должны иметь заголовок, потому что это фактически единственная точка входа в список и все его элементы, и без него вы бы не знали, с чего начать! Конец списка - это не узел, а узел, указывающий на null или на пустое значение.
С одним узлом тоже довольно просто. Он состоит всего из двух частей: данных или информации, содержащейся в узле, и ссылки на следующий узел.
Если мы сможем осмыслить это, то мы на полпути. То, как работают узлы, очень важно и очень мощно, и его можно резюмировать следующим образом:
Узел знает только о том, какие данные он содержит и кто его сосед.
Отдельный узел не знает длины связанного списка и может даже не знать, где он начинается или где заканчивается. Все, что касается узла, - это данные, которые он содержит, и на какой узел ссылается его указатель - следующий узел в списке.
И именно по этой причине почему связному списку не нужен непрерывный блок памяти. Поскольку один узел имеет «адрес» или ссылку на следующий узел, им не нужно жить рядом друг с другом, как элементы в массиве. Вместо этого мы можем просто полагаться на тот факт, что мы можем перемещаться по нашему списку, опираясь на ссылки указателя на следующий узел, а это означает, что нашим машинам не нужно блокировать один кусок памяти, чтобы представить наш список.
Это также объясняет, почему связанные списки могут динамически увеличиваться и уменьшаться во время выполнения программы. Добавление или удаление узла со связанным списком становится таким же простым, как перестановка некоторых указателей, а не копирование элементов массива! Тем не менее, у связанных списков есть и некоторые недостатки, о которых я пока не упоминаю, но о них мы поговорим на следующей неделе.
А пока мы просто насладимся славой того, насколько круты связанные списки!
Списки для всех форм и размеров
Несмотря на то, что части связанного списка не меняются, способ структурирования связанных списков может сильно отличаться. Как и большинство вещей в программном обеспечении, в зависимости от проблемы, которую мы пытаемся решить, один тип связанных списков может быть лучшим инструментом для работы, чем другой.
Односвязные списки - это простейший тип связного списка, основанный исключительно на том факте, что они действуют только в одном направлении. Есть одиночный трек, по которому мы можем перемещаться по списку; мы начинаем с узла head и проходим от корня до последнего узла, который заканчивается пустым значением null.
Но точно так же, как узел может ссылаться на свой последующий соседний узел, он также может иметь указатель ссылки на свой предыдущий узел! Это то, что мы называем двусвязным списком, потому что в каждом узле содержится две ссылки: ссылка на следующий , а также предыдущий узел. Это может быть полезно, если мы хотим иметь возможность перемещаться по нашей структуре данных не только в одном направлении или в одном направлении, но и в обратном направлении.
Например, если бы мы хотели иметь возможность переключаться между одним узлом и предыдущим узлом без необходимости возвращаться к самому началу списка, двусвязный список был бы лучшей структурой данных, чем односвязный список. Однако для всего требуется пространство и память, поэтому, если бы нашему узлу пришлось хранить два ссылочных указателя вместо одного, это было бы еще одним вопросом.
Циклический связанный список немного странен тем, что он не заканчивается узлом, указывающим на нулевое значение. Вместо этого у него есть узел, который действует как хвост списка (а не обычный головной узел), а узел после хвостового узла является началом списка. Эта организационная структура позволяет очень легко добавить что-то в конец списка, потому что вы можете начать обходить его с узла tail , как с первого элемента, так и с точки последнего элемента. для другого. Списки с круговой связью могут стать просто сумасшедшими, потому что мы можем превратить как односвязный, так и двусвязный список в круговой связанный список!
Но независимо от того, насколько сложен связанный список, если мы можем вспомнить основы узла и то, как он работает, и как структурированы различные ссылки на указатели в нашем списке, связанного списка мы не сможем решить!
На следующей неделе, во второй части этой серии статей, мы подробно рассмотрим пространственно-временную сложность связанных списков и то, как они сравниваются со своим двоюродным братом, массивом. Обещаю, что на самом деле это намного веселее, чем кажется!
Ресурсы
Если вы думаете, что связанные списки - это здорово, ознакомьтесь с этими полезными ресурсами.
- Различия между массивами и связанными списками, Дэмиен Винтур
- Структуры данных: массивы против связанных списков, mycodeschool
- Связанные списки: основы, д-р Эдвард Герингер
- Введение в связанные списки, Виктор Адамчик
- Структуры данных и реализации, д-р Дженнифер Велч
- Статические структуры данных против динамических структур данных, Айома Гаян Виджетунга
