Развёрнутый связанный список

Материал из Википедии — свободной энциклопедии

Развёрнутый связанный список — список, каждый физический элемент которого содержит несколько логических (обычно в виде массива, что позволяет ускорить доступ к отдельным элементам).

Позволяет значительно уменьшить размер памяти и увеличить производительность по сравнению с обычным списком. Особенно большая экономия памяти достигается при очень малом размере логических элементов и большом их количестве — так, односвязный список из 10000 четырёхбайтовых целых чисел при четырёхбайтовой же адресации памяти занимает 10000 дополнительных байт под адреса, если же обьединить числа в массивы по 100, расход памяти упадёт до 100 байт.

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