Розгорнутий зв'язний список

Розгорнутий зв'язний список — це зв'язаний список, який складається з однозв'язного списку чи двозв'язного списку блоків. Кожен з блоків містить кілька логічних елементів списка, зазвичай у вигляді масиву.

Для великої кількості елементів, дозволяє суттєво зекономити пам'ять на вказівниках, об'єднуючи логічні елементи двозв'язного списку в блоки.

Приріст продуктивності може досягатись також за рахунок того, що операції проводиться над відносно невеликими масивами, які зазвичай повністю містяться в кеш-пам'яті.

Гнучкість роботи з елементами в середині списку залишається. Наприклад операція по вставці елемента в блок залежить від розміру блока, а операції з блоками впливає лише на поточний та два суміжних блока. Але ця величина є завчасно відома, і не залежить від загальної кількості елементів списку. Таким чином складність збільшується, але не залежить від розміру списку, тобто це складність O(1) по відношенню до розміру списку.

При реалізації є проблема вибору розмір блоку (кількість елементів в масивах). При занадто великому розмірі блоку список починає страждати від тих же проблем, що й звичайний масив: довга вставка елементів на початок або середину, довге видалення елементів звідти, тощо. При занадто маленькому збільшується витрата пам'яті.

Така структура часто використовується в базах даних, розмір блока диктується розміром фізичної сторінки. Наприклад в Microsoft SQL Server 8 кілобайт. Блоки-сторінки представляють собою двозв'язний список що належать одній таблиці, елементи - рядки, або структури індекса.

• Дональд Кнут. Fundamental Algorithms // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1997. — Т. 1. — 650 с. — ISBN 0-201-89683-4.(англ.)
• Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 10.2 Зв'язані списки. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.