Как работает разворачиваемый связанный список

Может ли кто-нибудь объяснить мне, что такое развернутый связанный список. По моим сведениям, это связанный список, в котором каждый узел имеет массив элементов. И, конечно, это ускоряет поиск.Как работает разворачиваемый связанный список

На этой диаграмме, добавив 1,2,3 данных в этой картине не ясно, никаких осложнений ... но почему они добавили 4 во втором узле? Почему не в 4-м элементе первого узла? Какая польза от этого? И какова стратегия, которую они использовали для разделения?

источник

2013-05-09 Prabhakaran

Выгода заключается в том, что они могут вставлять данные впоследствии, не перемещая каждый элемент в списке. Также вам решать, хотите ли вы фрагментировать или нет. Вы можете сделать функцию добавления, если последний узел заполнен 3/4 и в этом случае создать новый узел. Или, что они, вероятно, сделали:

Если массив уже заполнен, мы сначала вставляем новый узел, предшествующий или следующий за текущим, и переместите половину элементов в текущем узле. (http://en.wikipedia.org/wiki/Unrolled_linked_list))

источник

2013-05-09 10:37:33 Philip

Большое спасибо .... Но как это полезно в кэш-памяти ??? Мы будем использовать кеш для быстрого восстановления! как эта быстрая вставка будет полезна ???? – Prabhakaran

Теоретически развернутые связанные списки быстрее, чем «нормальные» связанные списки, потому что узлы последнего могут быть более фрагментированы в памяти, что заставляет процессор загружать больше страниц памяти. Более того, развернутые связанные списки меньше, поскольку им не нужно сохранять указатели для каждого узла. Фактически, когда вы просто хотите хранить небольшие объекты или указатели/ссылки в своем списке, подумайте об использовании динамического массива (вектора), так как он является наиболее эффективным контейнером, см. Http://stackoverflow.com/questions/9764452/complete-vector-vs-linked-list-benchmark-for-randomized-insertions-deletion – Philip

Спасибо большое :) :) было действительно полезно :) – Prabhakaran

Номер 4 добавлен к четвертому элементу первого узла. Когда добавляется 5, он разбивает этот узел с 1, 2, 3 в узле 1 и 4, 5 в узле 2.

источник

2013-05-09 10:39:10 SpacedMonkey

Но друг, почему пустое пустое место? В чем цель ... Хорошо, по словам Филиппа Даэна, это будет быстрее при вставке данных. но как это будет полезно в кеше. – Prabhakaran

Предположим, что у вас есть элементы не более, чем «n» (теперь вы можете добавлять элементы позже), и вы хотите создать связанный список, лучшим способом с точки зрения производительности кеша является выбор Unrolled linked список. Вы создаете блоки размера ceil square root на n, а затем начинаете добавлять элементы в блок, если его размер меньше, чем ceil из квадратного корня n. Таким образом, у вас есть пол квадратного корня на n блоков. Это полезно при поиске k-го узла в связанном списке, поскольку его сложность теперь уменьшена с n до квадратного корня из n.

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

В каждом блоке поддерживается только круговой список, а не простой связанный список.

Надеюсь, это поможет .. :)

источник

2014-09-11 12:43:02 phaigeim

Как работает разворачиваемый связанный список

ответ

Смежные вопросы