Связанный список с быстрым запросом порядка узлов

Question

Мы используем структуру данных Doubly Linked List для хранения неупорядоченных данных (данные как таковые неупорядочены, однако порядок узлов в списке ссылок важен).Обычной операцией над этой структурой данных является NodeBeforeNode (Node N1, Node N2), которому присваиваются два указателя узлов в списке и определяется, какой из них предшествует другому.

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

Я ищу предложения по ускорению этого поведения.Мне в основном нужна структура данных, которая позволяет выполнять все следующие операции в постоянном или логарифмическом времени:

1. Вставка (после или перед узлом)
2. Удаление узла
3. NodeBeforeNode

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

Спасибо!

Answer 1

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

Так в основном:

• каждый новый элемент, вставленный в конец, должен иметь index = last_index + CONST
• каждый новый элемент, вставленный в список, должен иметь индекс = среднее арифметическое соседей

Это, конечно, работает, только если заданные два узла находятся в одном списке. Сравнение их было бы простым сравнением индекса.

Обратите внимание, что индекс должен быть числом с плавающей запятой. Этот простой сценарий предполагает, что существуют бесконечно делимые. Если ваша программа будет работать долгое время, возможно, следует запустить какой-нибудь периодический рабочий, который умножает значения индексов?

Answer 2

Реализация модифицированного дерева двоичного поиска,

struct node {
   /*add your data*/
   node *parent;
   node *left;
   node *right;
}

, в котором вы можете получить доступ к предыдущему элементу через родительский указатель, а время вставки, поиска и удаления указывается в O (logn)