Связанные списки являются одними из самых простых и наиболее часто используемых структур данных. В этой статье мы кратко обсудим, что такое связанные списки, типы связанных списков и почему мы их используем. Это мой самый первый пост в блоге в качестве разработчика, пожалуйста, не стесняйтесь оставлять комментарии и отзывы 😊

Что такое связанные списки?

Если вы ищете определение связанного списка в Википедии, результат довольно многословен:

В информатике связанный список — это линейный набор элементов данных, порядок которых не определяется их физическим размещением в памяти. Вместо этого каждый элемент указывает на следующий. Это структура данных, состоящая из набора узлов, которые вместе представляют собой последовательность.

Хорошо… но что это вообще значит? Давайте упростим это.

Связанный список — это не что иное, какпоследовательность элементов данных, где каждый элемент связан с элементом, который связан с другим элементом и т. д. Связанный список выглядит примерно так:

Как показано в приведенном выше примере, Данные 1 содержат «ссылку» на Данные 2, которая в основном является адресом Данных 2. Следовательно, Данные 1 знают, где найти Данные 2. Точно так же Данные 2 знают, где найти Данные 3, и так далее и тому подобное… Вот несколько основных, но важных понятий:

  • Каждый элемент данных может содержать данные любого типа, такие как строка, число, объект и т. д.
  • В этом случае данные 1 называются «головой» связанного списка, а данные 4 — «хвостом».
  • Данные 2 — это «следующий» элемент Данных 1, а Данные 1 — «предыдущий» элемент Данных 2.
  • «Длина» связанного списка равна количеству элементов в списке. В нашем случае длина равна 4.
  • Индекс связанного списка начинается с 0, как и массив.
  • Мы не можем получить Данные 3 напрямую из Данных 1, так как только Данные 2 знают, где живут Данные 3. Нам нужно сначала получить данные 2 из данных 1 и получить данные 3 из данных 2.
  • Если вы знаете заголовок (Данные 1), у вас есть доступ ко всем остальным элементам (Данные 2–4) в этом связанном списке.

Тип связанных списков

Пример ссылки, приведенный выше, на самом деле относится к типу, называемому «Односвязный список». Правило состоит в том, что ссылка является только односторонней, то есть Данные 1 знают о Данных 2, но Данные 2 ничего не знают о существовании Данных 1. Существует еще один тип связанного списка, называемый «двухсвязный список», он выглядит так:

Очень похоже на предыдущий пример, не так ли? Все верно, разница только в том, что в двусвязном списке следующий элемент тоже знает, где найти предыдущий элемент. Поэтому, если вы знаете какой-либо один элемент (например, данные 3), вы можете получить доступ ко всем другим элементам в этом связанном списке.

Существуют также типы, называемые «круговые связанные списки» и «круговые двусвязные списки». Погуглите, как они выглядят.

Почему связные списки (связанный список или массив)?

Теперь вы можете подумать, подождите минутку, разве это не похоже на массив? Почему мы не можем просто использовать массив для выполнения той же работы? И зачем нам вообще нужен связанный список?»

Чтобы ответить на эти вопросы, нам сначала нужно узнать, как массивы и связанные списки размещаются в памяти нашего компьютера. Допустим, у нас в памяти есть массив длиной 4, компьютер найдет кусок непрерывной памяти достаточной длины, чтобы сохранить там массив, как показано ниже:

Все элементы массива должны быть сохранены в последовательности непрерывных адресов памяти и в том же порядке, что и в массиве. Даже если во второй и третьей строках много пустых адресов, их длины недостаточно для сохранения массива.

Между тем, это пример того, как связанный список размещается в памяти:

Элементы связанного списка могут храниться в любом месте и в любом порядке внутри памяти. Поскольку каждый элемент данных содержит адрес следующего элемента, перечисленной ссылке не требуется целый кусок памяти, чтобы сохранить их все вместе в одном фрагменте.

А что, если мы хотим добавить новый элемент в примерный массив? Длина массива становится равной 5, и в его текущем адресе памяти недостаточно места для нового массива. Он должен найти новый кусок памяти, в котором достаточно места для сохранения нового массива. С другой стороны, связный список не требует перемещения адреса, памяти нужно только выделить новый элемент по любому пустому адресу. Работы гораздо меньше!

Вот еще один сценарий, мы хотим удалить какой-то случайный элемент из середины массива. Что будет происходить внутри памяти? Давайте взглянем:

Допустим, мы удалили элемент 3, теперь элемент 4 нужно сдвинуть влево, а элемент 5 тоже нужно сместить. Если после 3 осталось 100 элементов, то операцию нужно будет повторить 100 раз. Временная сложность O(n).

В то время как связанный список требует только изменения предыдущего элемента, чтобы он указывал на элемент после удаленного:

Таким образом, временная сложность составляет O (1). Представьте, если у вас есть массив/список из 1 млн элементов, это может быть огромным преимуществом по сравнению с массивом. Выбор правильной структуры данных важен с точки зрения работы с большими наборами данных.

Краткое содержание

Связанный список — это тип структуры данных, который включает ряд связанных элементов. Каждый элемент хранит данные и адрес следующего элемента. В отличие от списка массивов, они хранятся в отдельных местах памяти. Связанный список имеет значительное преимущество перед массивом при попытке добавить или удалить элементы из середины массива/списка.