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

В этой модели максимальное количество элементов составляет 4 для каждого узла.

В компьютерном программировании развернутый связанный список - это вариант связанного списка, в котором хранится несколько элементов в каждом узле. Это может значительно увеличить производительность кэша , одновременно уменьшив накладные расходы памяти, связанные с хранением метаданных списка, таких как ссылки. Это связано с B-деревом.

• 1 Обзор
• 2 Производительность
• 3 См. Также
• 4 Ссылки
• 5 Внешние ссылки

Типичный узел развернутого связанного списка выглядит так:

record node {node next // ссылка на следующий узел в списке int numElements // количество элементов в этом узле, вплоть до элементов массива maxElements // массив элементов numElements, // с пространством, выделенным для элементов maxElements}

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

Чтобы вставить новый элемент, мы просто находим узел, в котором должен находиться элемент, и вставляем элемент в элементымассив, увеличивающий numElements. Если массив уже заполнен, мы сначала вставляем новый узел, предшествующий или следующий за текущим, и перемещаем в него половину элементов текущего узла.

Чтобы удалить элемент, мы просто находим узел, в котором он находится, и удаляем его из массива elements, уменьшая numElements. Если это уменьшает узел до менее чем наполовину полного, мы перемещаем элементы из следующего узла, чтобы заполнить его снова выше половины. Если в результате следующий узел остается заполненным менее чем наполовину, мы перемещаем все его оставшиеся элементы в текущий узел, затем пропускаем и удаляем его.

Одним из основных преимуществ развернутых связанных списков является уменьшение требований к хранилищу. Все узлы (кроме одного) заполнены как минимум наполовину. Если выполняется много случайных вставок и удалений, средний узел будет заполнен примерно на три четверти, а если вставки и удаления выполняются только в начале и в конце, почти все узлы будут заполнены. Предположим, что:

• m = maxElements, максимальное количество элементов в каждом elementsarray ;
• v = накладные расходы на узел для ссылок и количества элементов;
• s = размер одного элемента.

Тогда пространство, используемое для n элементов, варьируется в пределах $(v\; /\; m\; +\; s)\; n\; \{\backslash \; displaystyle\; (v\; /\; m\; +\; s)\; n\; \}$и $(2\; об\; /\; м\; +\; с)\; n\; \{\backslash \; displaystyle\; (2v\; /\; m\; +\; s)\; n\}$. Для сравнения, обычные связанные списки требуют $(v\; +\; s)\; n\; \{\backslash \; displaystyle\; (v\; +\; s)\; n\}$пробела, хотя v может быть меньше, а массивов - один Для наиболее компактных структур данных требуется $sn\; \{\backslash \; displaystyle\; sn\}$пробел. Развернутые связанные списки эффективно распределяют накладные расходы v на несколько элементов списка. Таким образом, мы видим наиболее значительный прирост пространства, когда накладные расходы велики, maxElementsвелико, или элементы маленькие.

Если элементы особенно малы, например биты, накладные расходы могут быть в 64 раза больше, чем данные на многих машинах. Более того, многие популярные распределители памяти будут хранить небольшой объем метаданных для каждого выделенного узла, увеличивая эффективные накладные расходы v. Оба эти фактора делают развернутые связанные списки более привлекательными.

Поскольку каждый узел развернутого связанного списка хранит счетчик рядом со следующим полем, получение k-го элемента развернутого связанного списка (индексация) может выполняться за n / m + 1 промахов в кэш с коэффициентом м лучше обычных связанных списков. Кроме того, если размер каждого элемента мал по сравнению с размером строки кэша, список может быть перемещен в порядке с меньшим количеством промахов в кэше, чем обычные связанные списки. В любом случае время операции по-прежнему линейно увеличивается с размером списка.

• CDR-кодирование, еще один метод уменьшения накладных расходов и улучшения локальности кэша в связанных списках, подобных развернутым связанным спискам.
• список пропуска, аналогичный вариант связанного списка, предлагает быстрый поиск и вредит преимуществам связанных списков (быстрая вставка / удаление) меньше, чем развернутый связанный список
• B-дерево и T-tree, структуры данных, похожие на развернутые связанные списки в том смысле, что каждая из них может рассматриваться как «развернутое двоичное дерево»
• связанный список XOR, двусвязный список, который использует один указатель XOR на узел вместо двух обычных указателей.
• Дерево хэшированных массивов, где указатели на блоки данных хранятся в отдельном массиве более высокого уровня.

• Shao, Z. ; Реппи, Дж. Х.; Аппель, А.В. (1994), «Развертывание списков», Протокол конференции ACM 1994 года по Лиспу и функциональному программированию: 185–191, doi : 10.1145 / 182409.182453, ISBN 978-0897916431 CS1 maint: ref = harv (ссылка )

• Реализация написана на C
• Другая реализация, написанная на Java
• Структуры открытых данных - раздел 3.3 - SEList: компактный связанный список, Пэт Морин