c++ - studio - ¿Podemos implementar una lista con doble enlace usando un solo puntero?

solidity español

Question

Esta pregunta ya tiene una respuesta aquí:

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

Quiero usar una estructura como:

struct node {
   char[10] tag;
   struct node *next;
};

Quiero usar la estructura anterior para crear una lista con doble enlace. ¿Es eso posible y si es así, entonces cómo puedo lograrlo?

Answer 1

Me gustaría ofrecer una respuesta alternativa que se reduce a "sí y no".

Primero, es "algo imposible" si desea obtener todos los beneficios de una lista con doble enlace con un solo puntero por nodo.

Lista XOR

Sin embargo, aquí se cita también la lista vinculada XOR. Retiene un beneficio principal al tener una compresión con pérdida de dos punteros que se ajustan a uno que se pierde con una lista de enlaces individuales: la capacidad de recorrerla en reversa. No puede hacer cosas como eliminar elementos de la mitad de la lista en tiempo constante dada solo la dirección del nodo, y poder regresar a un elemento anterior en una iteración hacia adelante y eliminar un elemento arbitrario en tiempo lineal es incluso más simple sin el Lista XOR (también mantienes dos punteros de nodo allí: previous y current ).

Actuación

Sin embargo, también se cita en los comentarios un deseo de rendimiento . Teniendo en cuenta eso, creo que hay algunas alternativas prácticas.

Primero, un puntero siguiente / anterior en una lista doblemente enlazada no tiene que ser, digamos, un puntero de 64 bits en sistemas de 64 bits. Pueden ser dos índices en un espacio de direcciones contiguas de 32 bits. Ahora tienes dos índices para el precio de memoria de un puntero. Sin embargo, tratar de emular el direccionamiento de 32 bits en 64 bits es bastante complicado, tal vez no sea exactamente lo que desea.

Sin embargo, para obtener todos los beneficios de rendimiento de una estructura vinculada (árboles incluidos) a menudo es necesario que recupere el control sobre cómo se asignan y distribuyen los nodos en la memoria. Las estructuras vinculadas tienden a tener cuellos de botella porque, si solo utiliza malloc o un operator new simple para cada nodo, por ejemplo, pierde el control sobre el diseño de la memoria. A menudo (no siempre, puede tener suerte dependiendo del asignador de memoria, y si asigna todos los nodos a la vez o no), esto significa una pérdida de contigüidad, lo que significa una pérdida de la localidad espacial.

Es por eso que el diseño orientado a datos enfatiza las matrices más que cualquier otra cosa: las estructuras vinculadas normalmente no son muy amigables para el rendimiento. El proceso de mover fragmentos de una memoria más grande a una memoria más pequeña y más rápida le gusta si va a acceder a datos vecinos dentro de la misma porción (línea / página de caché, por ejemplo) antes del desalojo.

La lista no enrollada no tan citada

Así que aquí hay una solución híbrida que no se discute tan a menudo, que es la lista desenrollada. Ejemplo:

struct Element
{
    ...
};

struct UnrolledNode
{
    struct Element elements[32];
    struct UnrolledNode* prev;
    struct UnrolledNode* next;
};

Una lista desenrollada combina las características de las matrices y las listas con enlaces dobles, todo en uno. Le devolverá una gran cantidad de localidad espacial sin tener que recurrir al asignador de memoria.

Puede atravesar hacia adelante y hacia atrás, puede eliminar elementos arbitrarios del medio en cualquier momento por un precio bajo.

Y reduce la sobrecarga de la lista vinculada al mínimo absoluto: en este caso, codifiqué un tamaño de matriz desenrollada de 32 elementos por nodo. Eso significa que el costo de almacenar los punteros de la lista se ha reducido a 1/32 de su tamaño normal. Eso es incluso más barato desde el punto de vista general de los punteros de una lista que una lista enlazada individualmente, con un recorrido a menudo más rápido (debido a la localidad de caché).

No es un reemplazo perfecto para una lista con doble enlace. Para empezar, si está preocupado por la invalidación de los punteros existentes a los elementos de la lista en el momento de la eliminación, debe comenzar a preocuparse por dejar espacios vacíos (agujeros / lápidas) detrás de los que se reclaman (posiblemente asociando bits libres en cada uno de los rollos). nodo). En ese punto, está lidiando con muchas preocupaciones similares de implementar un asignador de memoria, incluidas algunas formas menores de fragmentación (por ejemplo, tener un nodo desenrollado con 31 espacios vacantes y solo un elemento ocupado: el nodo aún debe permanecer en la memoria) para evitar la invalidación hasta que esté completamente vacío).

Un "iterador" que permite la inserción / eliminación desde / hacia el medio normalmente tiene que ser más grande que un puntero (a menos que, como se indica en los comentarios, almacene metadatos adicionales con cada elemento). Puede desperdiciar memoria (por lo general, es discutible, a menos que tenga listas realmente pequeñas) al requerir, por ejemplo, la memoria para 32 elementos, incluso si tiene una lista de solo 1 elemento. Tiende a ser un poco más complejo de implementar que cualquiera de las soluciones anteriores. Pero es una solución muy útil en un escenario crítico de rendimiento y, a menudo, una que probablemente merezca más atención. Es uno que no se ha mencionado tanto en informática, ya que no funciona mejor desde una perspectiva algorítmica que una lista enlazada regular, pero la localidad de referencia tiene un impacto significativo en el rendimiento también en escenarios del mundo real.

Answer 2

No es completamente posible. Una lista doblemente enlazada requiere dos punteros, uno para el enlace en cada dirección.

Dependiendo de lo que necesite, la lista vinculada XOR puede hacer lo que necesite (consulte la respuesta de HolyBlackCat).

Otra opción es evitar un poco esta limitación haciendo cosas como recordar el último nodo que procesó a medida que recorre la lista. Esto le permitirá retroceder un paso durante el procesamiento, pero no hace que la lista esté doblemente vinculada.

Answer 3

No es posible de manera portátil sin invocar un comportamiento indefinido: ¿Se puede implementar una lista enlazada XOR en C ++ sin causar un comportamiento indefinido?

Answer 4

Puede declarar y admitir dos punteros iniciales a los nodos head y tail . En este caso, podrá agregar nodos a ambos extremos de la lista.

Tal lista a veces se llama una lista de dos caras.

Sin embargo, la lista en sí misma será una lista hacia adelante.

Usando una lista así, por ejemplo, puede simular una cola.

Answer 5

Sí, es posible, pero es un truco sucio.

Se llama lista enlazada XOR . ( https://en.wikipedia.org/wiki/XOR_linked_list )

Cada nodo almacena un XOR de next y prev como uintptr_t.

Aquí hay un ejemplo:

#include <cstddef>
#include <iostream>

struct Node
{
    int num;
    uintptr_t ptr;
};

int main()
{
    Node *arr[4];
    // Here we create a new list.
    int num = 0;
    for (auto &it : arr)
    {
        it = new Node;
        it->num = ++num;
    }
    arr[0]->ptr =                     (uintptr_t)arr[1];
    arr[1]->ptr = (uintptr_t)arr[0] ^ (uintptr_t)arr[2];
    arr[2]->ptr = (uintptr_t)arr[1] ^ (uintptr_t)arr[3];
    arr[3]->ptr = (uintptr_t)arr[2];

    // And here we iterate over it
    Node *cur = arr[0], *prev = 0;
    do
    {
        std::cout << cur->num << '' '';
        prev = (Node *)(cur->ptr ^ (uintptr_t)prev);
        std::swap(cur, prev);
    }
    while (cur);
    return 0;
}

Imprime 1 2 3 4 como se esperaba.