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

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

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

Связанный список

Каждый узел содержит значение — в данном случае целое число — и ссылку (также известную как указатель) на следующий узел. Последний узел, в данном случае 2, указывает на узел null. Это означает, что список подходит к концу.

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

Однако у связанных списков есть некоторые недостатки. В отличие от массивов, связанные списки не так быстро находят n^\text{th}n-й элемент. Чтобы найти узел в позиции nn, нужно начать поиск с первого узла в связанном списке, пройдя по пути ссылок nn раз. Кроме того, поскольку связанные списки по своей природе последовательны в прямом направлении, такие операции, как обход в обратном направлении — посещение каждого узла, начиная с конца и заканчивая впереди, — особенно громоздки.

Кроме того, связанные списки занимают больше памяти, чем массив, из-за их свойства ссылаться на следующий узел в связанном списке.

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

Сложность времени и пространства

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

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

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

Основные операции

Ниже приведены основные операции, поддерживаемые списком:

Вставка — добавляет элемент в начало списка.

Удаление — удаляет элемент в начале списка.

Вставить последним — добавляет элемент в конец списка.

Удалить последний — удаляет элемент из конца списка.

Вставить после — добавляет элемент после элемента списка.

Удалить — удаляет элемент из списка с помощью ключа.

Отображать вперед — отображает полный список в прямом порядке.

Отображать назад — отображает весь список в обратном порядке.

Надеюсь, это поможет вам немного покопаться в связанном списке и получить краткое представление.