Лучший способ объяснить связанный список - сначала описать массив в стиле C: массив в стиле C создается путем определения емкости массива или общего количества элементов, которые вы используете. можно хранить и какой тип элементов вы хотите сохранить. Затем вы можете добавить значения в этот массив того же типа, чтобы позже прочитать или удалить их.
С учетом сказанного, связанный список имеет ту же цель; создать связанный список, указав только тип, который вы хотите сохранить, и все. Вы по-прежнему можете добавлять, читать и удалять элементы, аналогичные массиву.
Давайте подумаем об этом примере при использовании массива: я создаю массив размером 5 для хранения целых чисел. Я добавляю к этому массиву два числа, затем еще два.
Что, если бы я хотел добавить в массив еще два числа? Я не могу, я достиг емкости этого массива, равной 5. Единственное решение - создать массив большего размера, скопировать старые числа из исходного массива в новый массив и тогда я могу добавить еще два числа.
В нашем случае это было не так уж и плохо, но что, если бы я хотел добавить один дополнительный элемент в массив из 1 000 000 элементов !? Мне пришлось бы скопировать весь массив в другой, чтобы добавить еще один элемент. Это медленно для компьютера.
Связанные списки спешат на помощь!
Связанные списки работают так же, как массивы, хранят элементы в упорядоченной последовательности, вы можете читать и изменять существующие значения и добавлять новые значения. Но когда связанный список становится лучше, чем массив, это когда вы хотите добавить больше элементов. Разрешите пояснить картинкой :)
Вот как массив хранится в памяти
А вот связанный список
У нас есть экземпляр связанного списка, который содержит ссылку или указатель на цепочку элементов, таким образом создавая то же использование, что и массив.
Но вы уловили разницу? Экземпляр нашего связанного списка имеет элементы, разбросанные по всей микросхеме ОЗУ, в отличие от массива! Благодаря этому мы можем добавить столько элементов в наш список без изменения размера, как это сделал бы массив.
Компромиссы
Прежде чем обсуждать каждый компромисс, давайте упомянем использование как наших массивов, так и связанных списков:
Добавление элементов
Элементы чтения
Изменение элементов
Удаление элементов: сохраним для другого поста
Поскольку чтение и изменение элементов в каждом связанном списке и массиве одинаковы, хорошо комбинируйте эти случаи.
Добавление элементов
Добавить элементы так же просто, как добавить новое звено в конец металлической цепи или пассажирскую тележку в очень длинный поезд. Для этого требуется один шаг или операция. Давайте сложим числа 5, 12 и 6 и посмотрим, как связанные списки удерживают цепочку элементов:
Эти пустые места в памяти будут там, где мы будем хранить класс связанного списка и его элементы, когда мы добавляем числа в список.
Сначала мы создаем наш пустой класс связанного списка. Head, или start, и tail, или end, являются свойствами свойств класса LinkedList и не указывают ни на что, или на nullptr. Позже мы обсудим, почему каждое из этих свойств важно. Давайте добавим 5 в наш связанный список:
Здесь произошли две вещи; во-первых, число 5 сохраняется где-то в памяти внутри класса узла. Этот класс имеет два свойства: data, в котором в нашем случае хранится число 5, и указатель next, который ссылается только на одно другое звено в нашей цепочке элементов.
Во-вторых, указатели головы и хвоста из связанного списка теперь указывают на узел 5 (поскольку в нашем связанном списке есть только один элемент, голова и хвост указывают на одно и то же место). Теперь добавим 12 и посмотрим, что получится:
Как и раньше, мы добавляем 12 и обновляем некоторые указатели в нашем связанном списке. Сначала мы обновляем свойство next для узла, на который указывает хвост (узел, содержащий число 5), чтобы он указывал на новый узел. содержащий число 12. Теперь узел 5 указывает на узел 12.
Наконец, поскольку 5 больше не является концом нашей цепочки, мы обновляем указатель tail из нашего класса связанного списка, чтобы он указывал на узел 12.
Обратите внимание, как мы не обновляем указатель head. Это потому, что свойство head указывает на первый элемент в нашем связанном списке, которым всегда будет узел 5. Давайте продолжим:
Давайте посмотрим, что мы показываем зеленым цветом: свойство head указывает на начало нашей цепочки элементов, то есть на узел 5. Затем свойство next узла 5 указывает на следующий элемент, который мы добавили, это узел 12. И то, что происходит с этим узлом, - это узел 6, который является последним элементом в нашем связанном списке. Из этого следует, почему свойство tail указывает на этот узел.
Обратите внимание: если мы еще не знали, где находится конец нашей цепочки, и хотели бы добавить новый элемент, нам пришлось бы начинать с передней части нашей цепочки и идти вниз, или traverse до конца цепочки, а затем мы можем подключить наш новый узел к связанному списку. Это может быть очень медленным, поэтому наличие хвостового указателя всегда делает добавление элемента за одну операцию!
В этом раунде побеждают связанные списки, поскольку массив может достичь своей емкости и придется изменять размер, что в большинстве случаев делает добавление очень дорогостоящим.
Чтение и изменение значений
Этот немного другой. Давайте еще раз посмотрим, как массив и связанный список сохраняются в памяти:
Вспомните, как массив хранится в памяти как единая группа? Что ж, это огромное преимущество при чтении и обновлении значений для массивов. Взгляните на наш пример:
Мы хотим посетить дом нашего друга в районе 1, множество домов, хранящихся в нашем городе, или ОЗУ 8 ГБ DDR5000 (шутка задумана):
Наш друг только сказал нам, где начинается район и через сколько домов можно добраться до их дома. Мы прибыли в начало квартала:
Поскольку мы знаем, как далеко находится их дом, мы пропускаем все дома и едем прямо к дому, который ищем.
Бум, вот и все. «Езда» и «пропуск» прохода для каждого дома занимали одну операцию, или O (1), что мы и хотим! Это возможно, потому что массив хранился как группа, все дома в нашем городе примыкают друг к другу (таран), что ускоряет чтение!
Честно говоря, для связанного списка домов чтение обходится дорого по сравнению с массивом. Давайте посмотрим, почему это так.
Тот же пример, что и раньше, мы хотим попасть в дом нашего друга, но теперь район хранится в связанном списке. Когда мы подъезжаем к окрестностям, это выглядит примерно так:
Поскольку каждый дом хранится в разных частях города (барана), единственный способ добраться до дома нашего друга - это «постучать» по первому дому и спросить хозяина: «Эй, а где следующий дом в этом районе? мы пытаемся найти пятый дом? » Затем они отвечали: «Следующий дом находится по этому« адресу »».
Итак, вот что мы делаем! Мы «едем» по следующему адресу в городе и задаем хозяину тот же вопрос: «Какой адрес у следующего дома?»
И когда мы едем к следующему дому, мы подсчитываем, сколько домов до дома нашего друга, чтобы случайно не пройти мимо их дома. Но обратите внимание, что каждый владелец дома знает только адрес следующего дома, а не любого другого дома.
Наконец, спросив, кто знает, сколько домовладельцев, мы наконец приехали в дом нашего друга!
К сожалению, для проезда всех домов требуется больше, чем O (1), в отличие от нашего массива домов, где мы могли проезжать до дома, который мы хотели, в O (1).
Каждый раз, когда мы посещаем дом и просим нас переехать в следующий дом, этот процесс занимает одну операцию. Итак, что, если бы дом, который мы хотели проехать, дошел до самого конца нашего связанного списка? Чтобы пройти до конца, потребуется O (n) операций, где n будет количеством элементов в связанном списке. В этом примере звучит не так плохо, но что, если бы у нас в районе 1000 домов !? Это будет довольно медленно.
Мы сразу знаем, кто выиграл этот раунд; массивы.
Какой мне использовать?
Мы внимательно изучили, что описывает связанный список, и поняли, что и массивы, и связанные списки имеют свои компромиссы. Ниже представлена таблица, в которой мы сделали выводы о каждом случае и каждой структуре данных (поскольку каждый случай в реальном мире особенный, это средние значения):
Итак, выбирайте инструмент с умом, лучше понимая, чего вы надеетесь достичь в каждой ситуации, и, возможно, вам понадобится нечто большее, чем просто массив или связанный список (подробнее о структурах данных в другом посте).
