Структуры данных и алгоритмы являются основой программирования. Для каждого интервьюера стало нормой проверять эти основы, поскольку они предоставляют методы для эффективной обработки данных. Программист, не разбирающийся в этих методах, может создать неэффективное решение или потребует больше времени для решения проблемы. Эта статья знакомит вас с одной из часто используемых линейных структур данных, называемой связными списками.
Линейная структура данных
Структура данных - это контейнер, в котором хранятся данные в определенном макете, который обеспечивает эффективный доступ и изменение. Структура данных может быть линейной или нелинейной. В то время как линейная структура данных имеет элементы, расположенные последовательно, нелинейная структура содержит элементы в иерархическом порядке.
Характеристики линейной структуры данных
- Расположение элементов данных: Последовательный
- Уровни. Все элементы данных представлены на одном уровне.
- Обход: можно полностью пройти за один проход
- Сложность реализации: проще реализовать
- Использование памяти: неэффективно
- Сложность времени: увеличивается с увеличением размера
Связанный список
связанный список - это набор элементов, называемых узлами, расположенных линейно. Каждый узел содержит поле данных и указатель на следующий узел в списке под названием следующий. Первый и последний узел связанного списка обычно называют заголовком и хвостом списка. Указатель заголовка указывает на первый узел, а последний узел будет указывать на нулевое значение. Обратите внимание, что голова - это не отдельный узел, а ссылка на первый узел. Когда список пуст, указатель заголовка указывает на нуль.
Связанные списки динамичны и гибки, их размер может увеличиваться и уменьшаться. Память для связанных списков выделяется во время выполнения или во время выполнения.
Типы связанных списков
- Односвязный список. Поскольку узел является однонаправленным, обход узла может выполняться только в прямом направлении (см. рис. выше).
- Двусвязный список. Будучи двунаправленным, обход узла может выполняться как в прямом, так и в обратном направлении. Каждый узел имеет дополнительный указатель prev, указывающий на предыдущий узел.
- Круговой связанный список. Вариант связного списка, в котором последний элемент связан с первым элементом, образующим круговой цикл. Он может принимать любую из двух вышеупомянутых форм. В круговом двусвязном списке указатель prev головы указывает на хвост, а указатель next хвоста указывает на голову.
Операции со связанными списками
- Поиск: найти первый элемент с заданным значением в связанном списке с помощью простого линейного поиска и вернуть указатель на этот элемент.
- Вставка. Чтобы вставить элемент «x» в связанный список, необходимо выполнить несколько шагов. Вставку можно выполнить тремя способами: вставить в начало списка, вставить в конец списка и вставить в середину списка.
- Удаление. Удаление элемента «x» из связанного списка - это многоэтапный процесс. Удаление может быть выполнено 3 разными способами: удалить из начала списка, удалить из конца списка и удалить из середины списка.
- Обход: для обхода всех узлов один за другим.
- Обновление: чтобы обновить данный узел.
- Сортировка: чтобы расположить узлы в связанном списке в определенном порядке.
- Объединение: объединение двух связанных списков в один.
Вставка узла
Ниже показана операция вставки в середину односвязного списка:
Удаление узла
Ниже показана операция удаления из середины односвязного списка:
Сложность времени
- Доступ к связанному списку осуществляется через его головной узел. Чтобы достичь целевого узла, нужно только пройти через каждый узел. Таким образом, доступ O (n).
- Аналогичным образом для поиска заданного значения в связанном списке необходимо просмотреть все элементы, пока вы не найдете это значение. Таким образом, поиск - O (n).
- Вставка в связанный список требует повторного указания предыдущего узла на вставленный узел и указания вновь вставленного узла на следующий узел. Таким образом, вставка - O (1).
- Удаление из связанного списка требует повторного указания предыдущего узла (узла перед удаленным узлом) на следующий узел (узел после удаленного узла). Таким образом, удаление равно O (1).
Преимущества
- Легкость вставки и удаления, которая занимает O (1) раз
- Меньше потерь памяти за счет динамического выделения памяти
Недостатки
- Произвольный доступ не разрешен
- Требуется дополнительное пространство в памяти для хранения ссылки на следующий узел
Приложения
- Реализация стеков, очередей и графиков и в областях, требующих динамического распределения памяти
- Используется для управления таблицей символов в конструкции компилятора
- Используется при переключении между программами с помощью Alt + Tab (реализовано с помощью кругового связанного списка)
- Манипулирование многочленами путем сохранения констант в узле связанного списка
- Используется в музыкальном проигрывателе, где песни связаны с предыдущими и следующими песнями
- Используется браузерами для реализации прямой и обратной навигации по посещенным веб-страницам, то есть кнопки назад и вперед
- Многие современные операционные системы используют двусвязные списки для поддержки ссылок на активные процессы, потоки и другие динамические объекты.
Подведение итогов
Хотя у связанных списков есть свои плюсы и минусы, они все еще широко используются сегодня в большинстве структур данных и приложений. Поскольку это основополагающая тема, для каждого разработчика важно иметь представление об этой линейной структуре данных. Я надеюсь, что эта статья поможет в достижении поставленной цели. Не стесняйтесь делиться своими взглядами в разделе комментариев ниже.
Ссылки:
Общие структуры данных, которые должен знать каждый программист
