Implementação de lista vinculada XOR

Question

Estou tentando resolver a questão abaixo para me preparar para uma entrevista xD

Uma lista vinculada XOR é uma lista duplamente vinculada mais eficiente em termos de memória. Em vez de cada nó manter os campos next e prev, ele contém um campo denominado both, que é um XOR do próximo nó e do nó anterior. Implementar uma lista vinculada XOR; tem um add (elemento) que adiciona o elemento ao final, e um get (index) que retorna o nó no índice.

Por favor, sugira como esta implementação pode ser melhorada. Obrigado 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

longnão é necessariamente uma boa escolha de tipo inteiro para armazenar ponteiros - felizmente <stdint.h>nos fornece o uintptr_tque é garantido como amplo o suficiente para esse propósito (sempre prefira um tipo sem sinal ao trabalhar com operações bit a bit).

Não gosto de ocultar tipos de ponteiro atrás de typedefs, como pStNode. Acho que é mais claro usar o tipo de ponteiro diretamente - ou um ponteiro para const StNodeonde for apropriado. Por exemplo, get()deve levar um ponteiro para const.

É desnecessário (e geralmente considerado imprudente) converter o resultado de malloc(). void*pode ser atribuído a qualquer tipo de ponteiro em C.

Há muitas coisas faltando no código que eu esperaria de algo que afirma ser uma implementação da lista. Não há função para remover elementos, e o único acessador fornecido é o getter de acesso aleatório de baixo desempenho.

Em particular, você não forneceu as funções next()e prev(), que esperaria ver se você quisesse demonstrar que as duas direções de passagem funcionam corretamente.

Por que get()aceita um número inteiro assinado para o índice? Parece que todos os valores negativos são equivalentes a 0; devemos fazer com que funcionem ou aceitar um tipo sem sinal. Além disso, podemos reduzir com segurança o escopo de tmppara dentro do loop.

É melhor escrever main()como um protótipo de função int main(void)(ou seja, sem argumentos, em vez de um número não especificado de argumentos). E, ao contrário de outras funções, main()não precisa retornar um valor de sucesso, de modo que essa linha pode ser omitida.

Answer 2

long both;

1. Usar um longpara armazenar um ponteiro de elenco pode ser um desperdício e muito pouco. Basta usar o dedicado uintptr_t. Mesmo que sua implementação não esteja totalmente até C99 (MS cumprimenta), provavelmente está <stdint.h>e o typedef.

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

A linha acima demonstra três idéias ruins:

1. Mais peças para controlar significa mais complexidade, o que é ruim. Portanto, ocultar ponteiros atrás de typedefs é uma má ideia, a menos que esse tipo de ponteiro nunca seja desreferenciado e, portanto, seja o único tipo verdadeiro usado.

2. Fundir um void*é supérfluo e sujeito a erros.
   Consulte " Eu lanço o resultado de malloc? ".

3. Não use a sizeof(TYPE)menos que seja inevitável. Fazer certo, mesmo que os tipos não sejam obscurecidos, é propenso a erros. Basta usar sizeof *pointer.

pStNode get(pStNode headNode, int index)

1. Há um tipo adequado de forma única como um índice: size_t. Alternativamente, se você deseja algo assinado, pode ser do seu interesse ptrdiff_t. Embora sim, se seu caso de uso garantir poucos nós suficientes, intpode funcionar.

2. Você realmente deve encapsular sua lista de alguma forma. Atualmente, você está criando um em main().
   Além disso, a limpeza deve ser possível sem encerrar o programa.

3. Se você usar pelo menos C99, main()tem um implícito return 0;.