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

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

Розгонутий список. Має 3 блока, кожен блок має 4 елемента.

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

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

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

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

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