Почему бы не использовать массив указателей для оптимизации связанного списка, а использовать список с пропуском?

Недавно я узнал о списке пропуска и узнал, что он предназначен для ускорения поиска связанного списка. Но мне интересно, почему бы не использовать структуру данных, которая добавляет массив указателей всех узлов на основе структуры связанного списка? Для списка из 2^n узлов, если на каждом уровне у нас есть половина количества указателей нижнего уровня, мы добавим 2^n-1 понтеров, это почти столько же добавлений списка указателей каждого узла, и в то же время это O (1) для доступа по индексу.

Должны быть какие-то причины, чтобы не реализовать мою идею, кто-нибудь может мне сказать?


lookup algorithm data-structures linked-list skip-lists
person Elio    schedule 01.07.2020    source источник
comment
Как вы обновляете массив указателей (который в основном является стандартным массивом), когда появляется новый элемент?   -  person libik    schedule 01.07.2020
comment
Как вы думаете, почему предложенная вами структура данных допускает произвольный доступ за время O(1)?   -  person kaya3    schedule 01.07.2020
comment
Идея аналогична базам данных, которые обычно сортируются по первичному ключу, но имеют многоуровневые массивы ключей для ускорения поиска по значению ключа. Например, ключ первого уровня для записи индексной карты для каждых 256 записей. Для каждых 256 записей 1-го уровня может существовать ключ второго уровня к индексу первого уровня. Может быть и третий уровень, в зависимости от размера базы данных. Список пропуска — аналогичная идея, и у вас может быть список пропуска к списку пропуска к связанному списку.   -  person rcgldr    schedule 01.07.2020
comment
Не могли бы вы подробнее рассказать о том, что представляют собой эти массивы и как они будут представлены?   -  person templatetypedef    schedule 02.07.2020
comment
@ kaya3 Если вы хотите получить доступ к n-му узлу, просто получите доступ к n-му элементу массива, чтобы получить его указатель   -  person Elio    schedule 02.07.2020
comment
@libik Вставка нового элемента выполняется точно так же, как связанный список и массив, временная сложность которых составляет O(1) и O(n) соответственно.   -  person Elio    schedule 02.07.2020
comment
Если у вас есть массив, содержащий ссылки на каждый узел, то вряд ли это связанный список, не так ли? Это был бы арралист. Если вы собираетесь иметь массив, достаточно длинный, чтобы содержать одну вещь для каждого элемента списка, массив также может хранить элементы списка напрямую.   -  person kaya3    schedule 02.07.2020

Ответы (1)


arrow_upward
0
arrow_downward

Список пропуска предлагает среднюю производительность O(log(n)) для чтения, вставки, обновления и удаления элемента в любом индексе.

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

Обе структуры данных используются на практике. Они просто используются для разных ситуаций.

person btilly    schedule 01.07.2020
comment
Спасибо, я только что искал механизм перестроения индекса при добавлении элемента и понял, что это O(log(n)). Можете ли вы привести пример использования идеи массива указателей на практике? - person Elio; 02.07.2020
comment
Массивы указателей используются повсеместно. Чтобы выбрать совершенно случайный пример, строка 26 docs.huihoo.com/ doxygen/linux/kernel/3.7/fdtable_8h_source.html объявляет, что fd в fd_table является указателем на массив указателей на объекты файлового дескриптора. - person btilly; 02.07.2020