- Связный список
-
В информатике, свя́зный спи́сок — базовая динамическая структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка.[1] Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.
Содержание
Виды связных списков
Линейный связный список
Односвязный список (Однонаправленный связный список)
Здесь ссылка в каждом узле указывает на следующий узел в списке. В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое текущего узла, невозможно.
Двусвязный список (Двунаправленный связный список)
Здесь ссылки в каждом узле указывают на предыдущий и на последующий узел в списке. По двусвязному списку можно передвигаться в любом направлении — как к началу, так и к концу. В этом списке проще производить удаление и перестановку элементов, так как всегда известны адреса тех элементов списка, указатели которых направлены на изменяемый элемент.
XOR-связный список
Кольцевой связный список
Разновидностью связных списков является кольцевой (циклический, замкнутый) список. Он тоже может быть односвязным или двусвязным. Последний элемент кольцевого списка содержит указатель на первый, а первый (в случае двусвязного списка) — на последний.
Реализация такой структуры происходит на базе линейного списка. В каждом кольцевом списке есть указатель на первый элемент. В этом списке константы NULL не существует.
Также существуют циклические списки с выделенным головным элементом, облегчающие полный проход через список.
Список с пропусками
Развёрнутый связный список
Пример реализации на Java
public class Node { private int element; private Node next; public int getElement(){ return element; } public void setElement(int e){ element = e; } public Node getNext() { return next; } public void setNext(Node n) { next = n; } }
Достоинства
- лёгкость добавления и удаления элементов
- размер ограничен только объёмом памяти компьютера и разрядностью указателей
- динамическое добавление и удаление элементов
Недостатки
- сложность определения адреса элемента по его индексу (номеру) в списке
- на поля-указатели (указатели на следующий и предыдущий элемент) расходуется дополнительная память (в массивах, например, указатели не нужны)
- работа со списком медленнее, чем с массивами, так как к любому элементу списка можно обратиться, только пройдя все предшествующие ему элементы
- элементы списка могут быть расположены в памяти разреженно, что окажет негативный эффект на кэширование процессора
- над связными списками гораздо труднее (хотя и в принципе возможно) производить параллельные векторные операции, такие как вычисление суммы
- кэш-промахи при обходе списка
Примечания
- ↑ Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, 2nd edition. The MIT Press, 2001. ISBN 0-262-03293-7
См. также
Структуры данных (список) Типы Массивы Ассоциативный массив • Multimap • Множество • Мультимножество • Хеш-таблица
Списки Связный список • Очередь (Кольцевой буфер • Двусвязная) • Стек • Список с пропусками
Деревья Графы Категория:- Связные списки
Wikimedia Foundation. 2010.