Связный список — это, наверное, первое, о чем могут спросить при разговоре на тему структур данных. Как бинарный поиск в разделе алгоритмов. И первый же вопрос, который задают люди, впервые про него услышавшие, это «А зачем он нужен, если есть массив?».
Для начала стоит ответить на вопрос… Что такое «переменная». Да, это фундаментальная часть, которую нужно понимать прежде чем приступать к осознанию массива. Процитирую Википедию:
Переменная — именованная, либо адресуемая иным способом абстрактная/виртуальная или физическая память. Адрес, на который указывает переменная используется для доступа к данным, а данные , находящиеся в переменной, называются значением этой переменной. Свойства значений в переменной явно или неявно определяются типом переменной.
Итак, переменная, это некоторая область в памяти (той самой ОЗУ, которой все так привыкли меряться, когда обсуждают мощность ПК). Она имеет адрес, по которому к ней можно обратиться, а также содержмое, соответствующее какому-то их существующих типов. Это может быть числовое значение, текстовый символ или что либо еще.
Несколько переменных одного типа, объединенные в одну группу, называются массивом. Основная особенность массива — все его элементы располагаются в памяти физически рядом. Как-то так:
Это одна из причин, почему в языках программирования нельзя просто взять и изменить размерность массива. Посмотрим на это более глобально:
Здесь представлена часть оперативной памяти системы, состоящая из нескольких рядов ячеек от 1 до 10. В них расположено массив данных из четырех ячеек, он обозначен белым цветом. А вот все то, что закрашено серым — это остальная память, которая занята данными от других программ.
Представим, что нам нужно увеличить размерность этого массива до пяти элементов. Что для этого понадобится?
Правильно! Сначала нужно будет выделить в области памяти новые ячейки в количестке пяти штук, обозначить их как массив и перенести туда все данные из оригинального массива. В итоге получится уже как-то так:
Последняя ячейка памяти при этом пока что свободна, но в нее можно записать какие-то данные. Обратите внимание, что место, где был расположен изначальный массив, теперь стало серым — оно теперь может быть занято данными от других программ.
Что плохого в такой простой структуре данных? На самом деле ничего плохого в ней нет, т.к. все структуры данных годны для тех или иных случаев. Она предоставляет мгновенный ответ на запрос к ячейке массива, т.к. заранее известно, где она расположена (адрес ячейки). Но в случаях, когда нужно оперативно менять размерность и добавлять или удалять элементы, массив начинает довольно сильно проседать по скорости из-за вот неободимости копирования самого себя в новое место.
Пример: чтобы удалить ячейку 3 в массиве из примера выше, нужно создать новый массив размерностью 4 и переместить туда данные из исходного, сдвинув содержимое на 1.
В таких задачах на помощь приходит связный список.
Его отличие от массива в том, что в памяти он расположен не в соседних ячейках. У каждого из элементов списка есть ссылка на следующий:
Переходя по ссылкам можно передвигаться по всему списку от начала до конца.
Список бывает нескольких видов:
- Однонаправленный — показан на примере выше. Элементы начиная с первого имеют ссылку только на следующий элемент.
- Двунаправленный — элементы имеют также и обратный ссылки.
- Закольцованный — последний элемент списка имеет ссылку на первый элемент. Может быть закольцован в обе стороны.
Пример двунаправленного списка:
Пример закольцованного списка:
Пример закольцованного двунаправленного списка:
Теперь представим все это в рамках оперативной памяти. Поскольку в каждом элементе хранится ссылка на следующий (и на предыдущий) элемент, нет необходимости хранить их в едином пространстве памяти, как в случае с массивом. Элементы могут быть разбросаны по всем свободным ячейкам памяти, но при этом оставаться связанными. Именно поэтому такую структуру данных и называют «связный список».
Как видно на схеме, все элементы связного списка расположены в совершенно разных местах. Но поскольку в каждом элементе хранится адрес следующего, передвигаться по ним несложно.
Какие положительные особенности такое хранение данных имеет в сравнении с массивом?
Связный список позволяет очень быстро производить операци добавления или удаления элементов. Там, где в массиве пришлось бы копировать все содержимое в новое место, здесь достаточно просто заменить ссылку в одном из элементов на ссылку из следующего, чтобы удалить элемент в центре списка, либо же просто добавить ссылку на еще один элемент к последнему, чтобы расширить список.
Когда стоит использовать связный список?
Выбор структуры данных вседа зависит от того, какую задачу вы хотите решить. Если для ее решения нужно просто иметь группу данных в памяти, которую не придется часто менять — выбор за массивом. Если же требуется постоянно что-то добавлять или удалять — выбор за связным списком.