Implementación de listas vinculadas XOR

Question

Estoy tratando de resolver la siguiente pregunta para prepararme para una entrevista xD

Una lista enlazada XOR es una lista doblemente enlazada más eficiente en memoria. En lugar de que cada nodo contenga los campos siguiente y anterior, contiene un campo denominado ambos, que es un XOR del nodo siguiente y del nodo anterior. Implementar una lista enlazada XOR; tiene un add (elemento) que agrega el elemento al final, y un get (índice) que devuelve el nodo en el índice.

Sugiera cómo se puede mejorar esta implementación. Gracias antes.

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int value;
    long both;
    
} StNode; 
typedef StNode *pStNode;

pStNode add(pStNode lastNode, int value)
{
    pStNode newNode = (StNode *) malloc(sizeof(StNode));
    newNode->value = value;
    
    //[both]=value of previous node pointer if it is last node
    newNode->both = (long)lastNode; 
    
    //calculating previous node [both] value
    lastNode->both = (long)newNode ^ lastNode->both;
    
    return newNode;
}

pStNode get(pStNode headNode, int index)
{    
    pStNode prevNode;
    pStNode currNode;
    long tmp;
    
    //special handling
    //case: cur=1, prev=0
    //we have set previous node of head node value to be 0 manually
    currNode = (StNode *) ((headNode->both) ^ 0);
    prevNode = headNode;
    
    //skim through linked list
    for(int i=2; i<=index; i++)
    {
        tmp = (long)prevNode;
        prevNode = currNode;
        currNode = (StNode *)(currNode->both ^ tmp);
    }
    
    return currNode;
}


int main() {  
    
    //I named first node as headNode, and last node as tailNode
    //create head node with both=0 since there is no previous node to it
    pStNode headNode = (StNode *) malloc(sizeof(StNode));
    headNode->both = 0; 
    headNode->value = 2;
    
    //assign pointers
    pStNode tailNode = headNode;
    
    //lets add 10 nodes after head, and assign values
    for(int i=3; i<13; i++)
    {
        tailNode = add(tailNode, i);
    }
    
    //get node value where index=3
    pStNode iNode = get(headNode, 3);
    printf( "result: %d\n",  iNode->value);
    
    return 0;
}

Answer 1

longno es necesariamente una buena elección de tipo entero para almacenar punteros; afortunadamente <stdint.h>nos proporciona lo uintptr_tque se garantiza que será lo suficientemente ancho para este propósito (siempre prefiera un tipo sin signo cuando trabaje con operaciones bit a bit).

No me gusta esconder tipos de punteros detrás de typedefs como pStNode. Creo que es más claro usar el tipo de puntero directamente, o un puntero a const StNodedonde sea apropiado. Por ejemplo, get()debería tomar un puntero a const.

No es necesario (y generalmente se considera imprudente) emitir el resultado de malloc(). void*se puede asignar a cualquier tipo de puntero en C.

Hay muchas cosas que faltan en el código que esperaría de algo que dice ser una implementación de la lista. No hay ninguna función para eliminar elementos, y el único descriptor de acceso proporcionado es el captador de acceso aleatorio de bajo rendimiento.

En particular, no ha proporcionado funciones next()y prev(), que esperaría ver si desea demostrar que ambas direcciones de recorrido funcionan correctamente.

¿Por qué get()acepta un entero con signo para el índice? Parece que los valores negativos son todos equivalentes a 0; deberíamos hacer que funcionen o aceptar un tipo sin firmar. Además, podemos reducir de forma segura el alcance de tmpdentro del bucle.

Es mejor escribir main()como un prototipo de función int main(void)(es decir, sin argumentos, en lugar de un número de argumentos no especificado). Y, a diferencia de otras funciones, main()no necesita devolver un valor para el éxito, por lo que esa línea se puede omitir.

Answer 2

long both;

1. Usar un longpara almacenar un puntero de fundición puede ser un desperdicio y muy poco. Solo usa el dedicado uintptr_t. Incluso si su implementación puede no estar completamente a la altura de C99 (MS saluda), probablemente lo haya hecho <stdint.h>y el typedef.

pStNode newNode = (StNode *) malloc(sizeof(StNode));

La línea anterior demuestra tres malas ideas:

1. Más piezas de las que hacer un seguimiento significa más complejidad, lo cual es malo. Por lo tanto, ocultar punteros detrás de typedefs es una mala idea, a menos que ese tipo de puntero nunca se desreferencia y, por lo tanto, sea el único tipo verdadero utilizado.

2. Lanzar un void*es superfluo y propenso a errores.
   Consulte " ¿Lanzo el resultado de malloc? ".

3. No lo use a sizeof(TYPE)menos que sea inevitable. Hacerlo bien incluso si los tipos no están ocultos es propenso a errores. Solo usa sizeof *pointer.

pStNode get(pStNode headNode, int index)

1. Hay un tipo adecuado de forma única como un índice: size_t. Alternativamente, si desea algo firmado, es posible que le interese ptrdiff_t. Aunque sí, si su caso de uso garantiza pocos nodos suficientes, intpodría funcionar.

2. Realmente debería encapsular su lista de alguna manera. Actualmente, está creando un archivo único en main().
   Además, la limpieza debería ser posible sin terminar el programa.

3. Si usa al menos C99, main()tiene implícito return 0;.