¿Cómo implementar una lista de doble enlace con solo un puntero?

Question

¿Cómo implementar una lista de doble enlace con solo un puntero?

Toma O (1) vez para encontrar el anterior y el siguiente nodo.

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

Answer 1

Esto suena como si fuera imposible, como se dice. No puede implementar dos punteros usando solo uno, en general.

Es posible que pueda comprimir dos desplazamientos de 16 bits en el espacio utilizado por el puntero único (supuesto 32 bits), o algún otro "corte inteligente", pero en general esto parece imposible.

This article describe un truco basado en XOR: ing los valores del puntero, pero yo consideraría que es un truco (hace una aritmética bit a bit en los valores del puntero).

Answer 2

¿Quizás usando un XOR linked list?

Answer 3

Si sizeof(int) == sizeof(Node *) tiene un nodo intermedio que contiene un puntero hacia atrás.

E.g.

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

donde (real node) contiene un valor y un puntero a la siguiente (intermediate node), y (intermediate node) contiene en val un puntero de nuevo al nodo intermedio anterior y en p un puntero hacia adelante a la siguiente (read node).

Por cierto, es una pregunta estúpida y estúpida. No puedo ver que enseña nada de valor.

Answer 4

Hay un truco clásico: almacene el XOR de los 2 punteros (Anterior y Siguiente) y al viajar en la lista siempre tiene uno de los que tiene a mano (acaba de llegar de allí) y puede XOR con el almacenado valor para obtener el otro puntero.

Huelga decir que esto no funcionará en un entorno de GC.

Answer 5

Una solución que ya se ha sugerido es XOR solution.

Otra solución es la solución "lados mover de un tirón": Si su problema está redactada de la siguiente manera:

Se le da un puntero al primer elemento, y que le gustaría a:

1. avanzar en la lista enlazada i pasos en o (i)
2. ir atrás en la lista enlazada i pasos en o (i)
3. añadir o eliminar elementos en la ubicación actual en o (1)

Así que siempre hay único puntero a la lista enlazada, y sólo hay un punto de entrada (sólo ir hacia atrás y hacia adelante, como en 1 y 2), se puede hacer lo siguiente:

• salvar a dos punteros: p1 p2,
• desde el primer puntero p1 se puede volver atrás, a partir del segundo puntero p2 de ir hacia adelante.
• Los elementos de la lista vinculada que están antes de p1 apuntan hacia atrás, mientras que los elementos después de p2 apuntan hacia adelante.

Así que su lista se vería así:

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

puntos P1 al elemento actual, P2 apunta al siguiente elemento, i1 ... i7 son los elementos de la lista

en el futuro se hace en O (1), y así se va hacia atrás, por punteros mover de un tirón:

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 

esta solución es mejor que la solución XOR en su legibilidad y que es más comprensible para los humanos. La desventaja es que no puede tener varios puntos de entrada a su lista vinculada.

Answer 6

Recientemente me topé con un enfoque agradable para este problema en un libro de Niklaus Wirth ("Algoritmos + Estructuras de Datos = Programas"). Funciona así ... Tienes un nodo, similar al que sugeriste, excepto que no agrega un puntero al siguiente (ni al anterior) Node. En cambio, tiene un único miembro link que representa la distancia (p.en unidades de sizeof(Node)) desde el nodo anterior (apuntado por Node* pPrev) en la cadena al siguiente nodo (apuntado por Node* pNext) en la cadena:

size_t link = pNext - pPrev; 

Así el nodo podría ser algo como esto:

struct Node { 
    int val; 
    size_t link; 
} 

Luego, para proceder desde el nodo actual, pCurrent, combinado con el nodo anterior pPrev, a la siguiente Node* pNext por escrito:

pNext = pPrev + pCurrent->link; 

Del mismo modo, se puede recorrer en la dirección opuesta reordenando esta ecuación:

pPrev = pNext - pCurrent->link; 

Sin embargo, este enfoque es algo restringido por C/C++ aritmética de punteros porque la diferencia de dos punteros sólo está bien definido si ambos punto dentro del mismo bloque de memoria. Entonces, esencialmente, todos sus nodos deberán estar contenidos dentro de una enorme matriz de Node s.