- Развёрнутый связанный список
-
Развёрнутый связанный список — список, каждый физический элемент которого содержит несколько логических (обычно в виде массива, что позволяет ускорить доступ к отдельным элементам).
Позволяет значительно уменьшить размер памяти и увеличить производительность по сравнению с обычным списком. Особенно большая экономия памяти достигается при очень малом размере логических элементов и большом их количестве — так, односвязный список из 10000 четырёхбайтовых целых чисел при четырёхбайтовой же адресации памяти занимает 40000 дополнительных байт под адреса, если же объединить числа в массивы по 100, расход памяти упадёт до 400 байт.
Прирост производительности достигается за счёт того, что большая часть операций проводится над относительно небольшими массивами данных, которые обычно целиком помещаются в кэш-памяти. Благодаря этому быстродействие программы может быть даже выше, чем при работе с обычными массивами. В развёрнутый список легко можно добавлять новые элементы, без необходимости переписывать весь массив, что является большой проблемой при работе с обычными массивами.
При реализации необходимо тщательно выбирать размер "блока" (количество логических элементов в физическом). При слишком большом размере блока список начинает страдать от тех же проблем, что и обыкновенный массив: долгая вставка элементов в начало или середину, долгое удаление элементов оттуда же, и т.п.
Ссылки
Wikimedia Foundation. 2010.
