Описание тега linked-list

Описание тега Вопросы с тегом
Связанный список - это структура данных, в которой элементы списка не обязательно хранятся последовательно, а скорее каждый элемент содержит ссылку на следующий (и, возможно, предыдущий) элемент в списке. Этот тег следует использовать с дополнительными тегами, указывающими используемый язык программирования ([c], [C++], [java] и т. Д.) И любые используемые библиотеки или надстройки, такие как [C++-standard-library]. Сама запись должна содержать исходный код проблемы.

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

Типы

Списки - это канонический рекурсивный (или индуктивный) тип данных.

Конкретные реализации

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

Как они работают

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

Спектакль

Гибкость связанных списков несколько компенсируется сложностью некоторых операций со списками (доступ к элементу с индексом n в списке составляет O(n), а для массивов - O(1)). На практике они представляют собой очень невыгодную структуру для алгоритмов на основе произвольного доступа. Производительность списков и массивов одинакова (O) для операций, которые обрабатывают каждый элемент списка по порядку.

Однако они обладают хорошей производительностью при работе с большими списками, в которых произвольный доступ на основе индексов не требуется, но требуется удаление элементов в известных позициях в памяти.

Смотрите также