Как реализовать двойной связанный список только с одним указателем?

Question

Как реализовать двойной связанный список только с одним указателем?

Требуется O (1) время, чтобы найти предыдущий и следующий узел.

struct Node
{
   int val;
   Node* p;
};

Answer 1

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

Возможно, вы сможете втиснуть два 16-разрядных смещения в пространство, используемое одним (предполагаемым 32-разрядным) указателем или каким-либо другим «умным взломом», но в целом это звучит невозможно.

Эта статья описывает трюк, основанный на XOR: ввод значений указателя, но я бы посчитал это хаком (он выполняет побитовую арифметику со значениями указателя).

Answer 2

Существует классический хак: сохраняйте XOR 2 указателей (Prev и Next), и при перемещении по списку у вас всегда есть 1 из них (вы только что пришли оттуда), и вы можете XOR с сохраненным значением чтобы получить другой указатель.

Само собой разумеется, что это не будет работать в среде GC.

Answer 3

Может быть, с помощью связанного списка XOR ?

Answer 4

Одним из решений, которое уже было предложено, является решение XOR .

Другим решением является решение "перевернутые стороны": Если ваша проблема сформулирована следующим образом:

Вам дан указатель на первый элемент, и вы хотели бы:

1. Перейти в связанном списке i шаги в O (i)
2. Вернитесь в связанный список i, войдите в O (i)
3. Добавить или удалить элементы в текущем местоположении в O (1)

Так что всегда есть только один указатель на связанный список, и есть только одна точка входа (просто переход вперед и назад, как в 1 и 2), вы можете сделать следующее:

• Сохранить два указателя: p1 , p2
• От первого указателя p1 вы можете вернуться назад, от второго указателя p2 вы идете вперед.
• Элементы связанного списка, предшествующие p1 , указывают назад, а элементы после p2 указывают вперед.

Итак, ваш список будет выглядеть так:

                  p1 p2
                  |  |
                  V  V
i1 <- i2 <- i3 <- i4 i5 -> i6 -> i7

p1 указывает на текущий элемент, p2 указывает на следующий элемент, i1 ... i7 - элементы в списке

Движение вперед выполняется в O (1), и то же самое происходит назад, переключая указатели:

Forward one step:
                        p1 p2
                        |  |
                        V  V
i1 <- i2 <- i3 <- i4 <- i5 i6 -> i7


Backward one step: 
            p1 p2
            |  |
            V  V
i1 <- i2 <- i3 i4 -> i5 -> i6 -> i7

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

Answer 5

Недавно я наткнулся на хороший подход к этой проблеме в книге Никлауса Вирта («Алгоритмы + Структуры данных = Программы»). Это выглядит так ... У вас есть узел, похожий на тот, который вы предложили, за исключением того, что он не агрегирует указатель на следующий (или на предыдущий) Node. Вместо этого у вас есть один элемент link, который представляет расстояние (например, в единицах sizeof(Node)) от предыдущего узла (на которое указывает Node* pPrev) в цепочке до следующего узла (на который указывает Node* pNext) в цепочке:

size_t link = pNext - pPrev;

Таким образом, узел может выглядеть примерно так:

struct Node {
    int val;
    size_t link;
}

Затем, чтобы перейти от текущего узла pCurrent в сочетании с предыдущим узлом pPrev к следующему Node* pNext, написав:

pNext = pPrev + pCurrent->link;

Аналогично, вы можете пройти в противоположном направлении, переставив это уравнение:

pPrev = pNext - pCurrent->link;

Однако этот подход несколько ограничен арифметикой указателей C / C ++, поскольку различие двух указателей четко определено только в том случае, если обе точки находятся внутри одного и того же блока памяти. По сути, все ваши узлы должны будут содержаться в одном огромном массиве Node s.

Answer 6

Если sizeof(int) == sizeof(Node *), то иметь промежуточный узел, который содержит обратный указатель.

Е.Г.

(real node) -> (intermediate node) -> (read node) -> (etc)

, где (real node) содержит значение и указатель на следующий (intermediate node), а (intermediate node) содержит в val обратный указатель на предыдущий промежуточный узел и в p прямой указатель на следующий (read node).

Кстати, это глупый, глупый вопрос. Я не вижу, что это учит чему-то ценному.