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

Он же просто «список», самая простая после массива структура данных. Каждый элемент данных хранится в ячейке вместе со ссылкой на следующую. Таким образом, ячейки данных выстраиваются в цепочку.

В пользовательском коде сохраняется адрес «головы» списка – первой ячейки. От нее по ссылкам можно дойти до любого элемента «хвоста».

В отличие от простого массива, информация в списке разрозненна в памяти, что делает кэширование процессора менее эффективным. На хранение ссылок тратится дополнительная память. Взамен, список дает возможность вставки/удаления элемента в середине без перезаписывания остальных элементов.

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

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