Он же просто «список», самая простая после массива структура данных. Каждый элемент данных хранится в ячейке вместе со ссылкой на следующую. Таким образом, ячейки данных выстраиваются в цепочку.
В пользовательском коде сохраняется адрес «головы» списка – первой ячейки. От нее по ссылкам можно дойти до любого элемента «хвоста».
В отличие от простого массива, информация в списке разрозненна в памяти, что делает кэширование процессора менее эффективным. На хранение ссылок тратится дополнительная память. Взамен, список дает возможность вставки/удаления элемента в середине без перезаписывания остальных элементов.
Для ускорения доступа к последним элементам, а также для обхода данных с конца существует модификация, которая называется двусвязный список. В нём каждая ячейка хранит ссылку и на следующую, и на предыдущую.
Сложность поиска по значению и по индексу так же как и модификации в середине – линейная; любых действий с головным элементом – константная.
