Данные повсюду, и они лежат в основе всего, что мы делаем, но как мы их организуем, обработаем и получим? Здесь на помощь приходят структуры данных, специализированный формат для организации и обработки данных. Выбор правильной структуры важен, так как существует множество вариантов. Поскольку у каждого из них есть свои плюсы и минусы, неплохо иметь общее представление о том, как они реализованы, чтобы принять правильное решение для вашего проекта.
Типы структур данных
Существует два типа структур данных: линейные и нелинейные. Линейные структуры упорядочивают данные на одном уровне, каждый элемент связан со своим предыдущим и последующим элементом, представьте себе музыкальный проигрыватель, просматривающий песни по порядку. В то время как нелинейные структуры содержат несколько уровней и не соединяют элементы последовательно, подумайте об исполнителе, у которого есть несколько альбомов, и в каждом альбоме есть несколько песен. Мы собираемся погрузиться в общую линейную структуру данных, называемую связанными списками.
Что такое связанный список?
Подобно массиву, связанный список представляет собой упорядоченную линейную структуру. Но в отличие от массива элементы связанного списка хранятся в отдельных узлах, которые связаны с помощью указателей, у них нет индекса.
Взгляните на массив выше, мы видим, что он хранится в ячейке 1407 и расположен в непрерывной памяти. Но что, если мы позже захотим добавить в этот массив больше, а в памяти нет места? Мы не можем изменить размер массива или рискуем перезаписать другие данные. Что, если бы у нас был способ сказать компьютеру, где искать следующий элемент, это связанный список.
Каждый узел в связанном списке хранит данные и адрес следующего узла. Например, мы начинаем с головы, извлекая данные из первого узла, который равен 2, затем мы можем использовать адрес указателя (1408) для перехода к следующему узлу и так далее. Как только мы достигаем последнего узла, его указатель указывает на ноль, что является простым способом определения конца связанного списка.
Типы связанных списков
Теперь, когда мы лучше понимаем, как работают связанные списки, давайте рассмотрим различные типы. Приведенный выше пример — один из самых распространенных, он называется Односвязный список. Это самый простой тип, поскольку его узлы содержат только некоторые данные и указатель на следующий узел, что означает, что обход может быть выполнен только в одном направлении.
Подобно односвязному списку, у нас есть двухсвязный список, который содержит указатель на следующий узел, а также на предыдущий узел. Это означает, что узел состоит из 3 частей вместо 2. Это позволяет нам перемещаться по списку в любом направлении.
Круговой связанный список подобен односвязному списку, за исключением того, что последний узел указывает на первый узел списка, а NULL отсутствует.
Циклический двусвязный список — это сочетание двусвязного списка и циклического связанного списка, где указатель last (next) указывает на первый узел, а указатель prev первого узла указывает на последний узел. .
И последнее, но не менее важное: у нас есть связанный список заголовков, который включает в себя специальный узел заголовка, который позволяет хранить важную информацию о списке, которая в противном случае не хранилась бы в каждом узле. Например, у вас может быть количество узлов в списке, чтобы вам не приходилось каждый раз проходить и находить общее количество. Связанные с заголовком списки могут быть Основными или Круговыми, что означает, что последний узел указывает на ноль, тогда как в циклическом указатель последнего узла указывает на заголовок.
Зачем использовать связанный список?
Мы знаем, что такое связанные списки, и знаем, как они переходят от узла к узлу, но зачем нам их использовать? Что ж, мы можем искать, добавлять, удалять, обновлять и делать практически все, что можно делать с массивом. Так почему бы не использовать массив? Причин много, давайте разберемся…
Размер
Массивы не могут быть изменены во время выполнения, поскольку они хранятся в смежных блоках памяти и могут привести к перезаписи других данных. Если вы знаете, что размер ваших данных будет меняться, связанный список позволит использовать динамический размер, поскольку каждый узел указывает на следующий.
Время исполнения
Когда дело доходит до вставки и удаления, связанный список работает быстрее, потому что ему не нужно реорганизовывать данные, в то время как массив должен освобождать место и сдвигать каждый элемент.
Зачем избегать связанного списка?
Теперь, когда мы знаем, зачем использовать связанные списки, давайте рассмотрим случаи, когда может быть проще придерживаться массива или какой-либо другой структуры данных.
Эффективность памяти
Связанный список с тем же количеством элементов, что и массив, займет больше памяти, так как ему нужно хранить указатель на следующий узел.
Нет произвольного доступа
Поскольку в связанном списке нет индекса, мы должны начать обход с первого узла, пока не найдем искомый элемент, это становится более медленным процессом, чем массив. Использование связанного списка при частом доступе/поиске данных, вероятно, не лучший вариант.
Примеры связанных списков
Вам может быть интересно, какое приложение/функция будет реализовывать связанный список, давайте посмотрим несколько раз, когда его использование принесло бы нам большую пользу.
Приложение для заказа еды
Клиенты добавляются в связанный список после размещения заказа и удаляются после его выполнения.
Музыкальный проигрыватель
Каждая песня связана с предыдущей и следующей песней, чтобы обеспечить легкий доступ для пользователя. Добавление/удаление песен в/из плейлиста или очереди также может использовать эту реализацию.
GPS-навигатор
При поиске пункта назначения вам будут показаны разные маршруты, это будут связанные списки. После выбора маршрута первый узел является вашим первым направлением, по достижении которого он переходит к следующему и так далее. При необходимости пит-стопы можно добавить в связанный список вставкой.
Я надеюсь, что это введение в связанные списки поможет вам принять лучшее решение, когда придет время выбирать структуры данных для вашего проекта. Как видите, это лишь одна из многих существующих структур данных, каждая из которых имеет свои плюсы и минусы, нужно просто найти ту, которая подходит для ваших нужд.
Ресурсы:
