Implementação de lista duplamente vinculada

Question

Eu venho de uma experiência em C ++ e recentemente entrei em C, e uma das primeiras coisas que fiz foi uma lista duplamente vinculada, pois achei que seria uma boa prática para mim com ponteiros e alocação de memória. Não é muito complexo, mas apenas com algumas funções básicas.

Esta é a visão geral da minha lista:

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

typedef struct Node
{
    int val;
    struct Node* prev;
    struct Node* next;
} Node;

typedef struct
{
    int length;
    Node* head;
    Node* tail;
} double_list;

double_list* create_list(); // constructor
void destroy_list(double_list* const list); // destructor

void insert_pos(double_list* const list, int index, int val);
void insert_front(double_list* const list, int val);
void insert_back(double_list* const list, int val);

void remove_pos(double_list* const list, int index);
void remove_front(double_list* const list);
void remove_back(double_list* const list);

void sort_list(double_list* const list); // selection sort
void reverse_list(double_list* const list);

Ele apenas tem inserção e remoção básicas, bem como funções de construtor, destruidor, classificação e reversão.

Aqui está a definição real para as funções:

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

typedef struct Node
{
    int val;
    struct Node* prev;
    struct Node* next;
} Node;

typedef struct
{
    int length;
    Node* head;
    Node* tail;
} double_list;

double_list* create_list()
{
    double_list* list = malloc(sizeof(*list));

    list->length = 0;
    list->head = NULL;
    list->tail = NULL;

    return list;
}

void destroy_list(double_list* const list)
{
    list->length = 0;

    Node* node_ptr = list->head;
    while (node_ptr != NULL)
    {
        node_ptr = node_ptr->next;
        free(list->head);
        list->head = node_ptr;
    }
}

void insert_pos(double_list* const list, int index, int val)
{
    if (index < 0 || index > list->length)
        return;

    list->length += 1;

    if (list->head == NULL)
    {
        list->head = malloc(sizeof(*(list->head)));

        list->head->val = val;
        list->head->prev = NULL;
        list->head->next = NULL;

        list->tail = list->head;

        return;
    }

    if (index == 0)
    {
        Node* new_node = malloc(sizeof(*new_node));

        new_node->val = val;
        new_node->prev = NULL;
        new_node->next = list->head;

        list->head->prev = new_node;
        list->head = new_node;

        return;
    }

    if (index == list->length - 1)
    {
        Node* new_node = malloc(sizeof(*new_node));

        new_node->val = val;
        new_node->prev = list->tail;
        new_node->next = NULL;

        list->tail->next = new_node;
        list->tail = new_node;

        return;
    }
    
    Node* node_ptr = list->head;
    for (int a = 0; a < index; ++a)
        node_ptr = node_ptr->next;

    Node* new_node = malloc(sizeof(*new_node));

    new_node->val = val;
    new_node->next = node_ptr;
    new_node->prev = node_ptr->prev;

    node_ptr->prev->next = new_node;
    node_ptr->prev = new_node;
}

void insert_front(double_list* const list, int val)
{
    insert_pos(list, 0, val);
}

void insert_back(double_list* const list, int val)
{
    insert_pos(list, list->length, val);
}

void remove_pos(double_list* const list, int index)
{
    if (index < 0 || index >= list->length)
        return;

    list->length -= 1;

    if (index == 0)
    {
        Node* node_ptr = list->head;
        list->head = list->head->next;
        list->head->prev = NULL;

        free(node_ptr);
        return;
    }

    if (index == list->length)
    {
        Node* node_ptr = list->tail;
        list->tail = list->tail->prev;
        list->tail->next = NULL;

        free(node_ptr);
        return;
    }
    
    Node* node_ptr = list->head;
    for (int a = 0; a < index; ++a)
        node_ptr = node_ptr->next;

    node_ptr->prev->next = node_ptr->next;
    node_ptr->next->prev = node_ptr->prev;

    free(node_ptr);
}

void remove_front(double_list* const list)
{
    remove_pos(list, 0);
}

void remove_back(double_list* const list)
{
    remove_pos(list, list->length - 1);
}

void sort_list(double_list* const list)
{
    Node* index_ptr = list->head;
    Node* small_ptr = list->head;
    Node* node_ptr = list->head;
    while (index_ptr->next != NULL)
    {
        while (node_ptr != NULL)
        {
            if (node_ptr->val < small_ptr->val)
                small_ptr = node_ptr;

            node_ptr = node_ptr->next;
        }

        int hold = index_ptr->val;
        index_ptr->val = small_ptr->val;
        small_ptr->val = hold;

        index_ptr = index_ptr->next;
        node_ptr = index_ptr;
        small_ptr = index_ptr;
    }
}

void reverse_list(double_list* const list)
{
    Node* node_ptr = list->head;

    list->head = list->tail;
    list->tail = node_ptr;

    while (node_ptr != NULL)
    {
        Node* temp = node_ptr->prev;
        node_ptr->prev = node_ptr->next;
        node_ptr->next = temp;

        node_ptr = node_ptr->prev;
    }
}

E aqui está um pequeno exemplo de como minha lista seria usada:

double_list* list = create_list();

insert_back(list, 1);
insert_back(list, 2);
insert_back(list, 3);

sort_list(list);

destroy_list(list);

Minha principal área de preocupação são:

1. O construtor e o destruidor estão fazendo seu trabalho corretamente? O destruidor está perdendo memória e há uma maneira melhor de fazer o construtor?

2. As funções remove()e insert()são eficientes? Existe uma maneira melhor de fazer isso, como criar uma remove()função mais genérica para que eu não precise ter casos de teste especiais para índice de 0 e coisas assim?

3. As funções sort()e estão reverse()corretas, pelo menos? Eu sei que a classificação por seleção não é o melhor algoritmo a ser usado. E a reverse()função está implementada corretamente? Existe uma maneira melhor de reverter a lista?

Desculpe, estou sendo um pouco amplo com minha pergunta. Posso editá-lo para me concentrar em uma questão mais específica, se necessário.

obrigado

Answer 1

Boa pergunta, bem formatada, bem elaborada e a implementação parece funcionar!

Primeiro a responder às suas perguntas:

Q1:

Construtor:

• Verifique o valor de retorno de malloc, poderia ser NULLse falhou (sem memória)

Destruidor:

• apenas passe double_list *list, o constlá não faz sentido (não sei por que você colocou lá).
• você perde memória, porque você não libera list, que você alocou no construtor

Editar 1:

Se você passar, double_list *const listisso significa que o valor da lista (o ponteiro) não pode ser alterado, o que não faz sentido aqui porque o usuário desta interface se apega ao ponteiro.

Se constfor antes do tipo, const double_list *listisso significa que o conteúdo para onde a lista está apontando não pode ser alterado.

Por exemplo, se você tem uma função que recebe uma string e deseja comunicar ao usuário dessa função que o conteúdo da string não vai mudar, você deve fazer void foo(const char *bar). Se a função for apenas, foo(char *bar)o usuário não pode ter certeza de que o conteúdo da string barainda é o mesmo depois.

Q2:

• Não vejo problemas com as funções removee em insertrelação ao desempenho. A inserção no meio sempre será O (n). Remover / inserir no início e fim é O (1) que você consegue em seu código.
• Seria um pouco mais intuitivo se você implementasse o caso simples de remover cabeça / cauda na função remove_front/ remove_backe usasse essas funções na remove_posfunção genérica .

Q3:

Ordenação

• sort_list: o que você poderia fazer é definir um sinalizador quando a lista for ordenada para que, se for ordenada novamente, seja rápido (desmarque o sinalizador quando um elemento for adicionado)
• caso contrário, não vejo problemas com a implementação de classificação

reverter

A implementação reversa de sua lista é O (n), mas como você tem uma lista duplamente vinculada, você pode simplesmente fazer uso dela. Você poderia ter dois conjuntos de operações na lista, um opera na direção para frente e o outro na direção reversa. Sempre que o reverse_listé chamado, você deve trocar o conjunto de funções. Veja o exemplo abaixo:

struct list_operations
{
    void (*insert_front)(double_list* const list, int val);
    // more functions
};

static const struct list_operations list_operations_forward = 
{
    .insert_front = insert_front_forward,
    // more functions
};

static const struct list_operations list_operations_reverse = 
{
    .insert_front = insert_front_reverse,
    // more functions
};

void reverse_list(double_list* list)
{
    if (NULL == list)
    {
        return
    }

    list->operations = (list->operations == &list_operations_forward)?&list_operations_reverse:&list_operations_forward;
}

Feedback mais geral:

Esconder informação privada

Você vaza alguns dos detalhes no arquivo h. Você provavelmente não quer que um usuário de sua double_listbiblioteca possa mexer com os nós, portanto, você deve ocultá-lo e adicionar funções para obter o valor. O arquivo h ficaria assim:

typedef struct double_list_s double_list_t;

double_list* create_list();
void destroy_list(double_list* list);

void insert_pos(double_list *list, int index, int val);
void insert_front(double_list *list, int val);
void insert_back(double_list *list, int val);

void remove_pos(double_list *list, int index);
void remove_front(double_list *list);
void remove_back(double_list *list);

int get_pos(double_list *list, pos);
int get_front(double_list *list);
int get_back(double_list *list);

void sort_list(double_list *list); // selection sort
void reverse_list(double_list *list);

Remova o const

Você está passando double_list* const list, o que exatamente você está tentando alcançar com o const?

Proteção de inclusão ausente

Você deve adicionar o seguinte:

#ifndef __DOUBLE_LIST_H__
#define __DOUBLE_LIST_H__

// snip

#endif

Remova as inclusões no arquivo h

As inclusões devem ir apenas nos arquivos c. Caso contrário, você pode ter inclusões cíclicas.

a estrela indicadora gruda na variável

por exemplo, não é bom: char* b

Melhor: char *b

caso contrário, parecerá estranho se você tiver a seguinte declaração:

char* b, *avs ( char *b, *a)

Verifique se há NULL

Verifique o listargumento para NULL nas funções

Verifique se há NULL após a alocação

Ao alocar os nós, você também deve verificar se mallocretornou NULL.

Testando

Quando você adiciona à sua lista, você adiciona o elemento na ordem 1,2,3, então sort_listnão está fazendo muito.

Nomeando as funções

Quando se trata de nomear funções, certamente se trata de gosto pessoal, mas eu ficaria com as expressões comuns. Por exemplo backe frontsão um pouco incomuns, acho heade taildescrevo melhor para que servem as funções.

Além disso, torna sua interface um pouco mais limpa se você nomeá-los de forma consistente

list_create()
list_destroy()

list_pos_insert()
list_head_insert()
list_tail_insert()

list_pos_remove()
list_head_remove()
list_tail_remove()

list_sort()
list_reverse()

Avise-me se algo não estiver claro, o codereview "esqueceu" metade do meu texto, então me apressei um pouco para escrevê-lo novamente.

Answer 2

a respeito de:

typedef struct
{
    int length;
    Node* head;
    Node* tail;
} double_list;

A maioria dos depuradores usa o nome de 'tag' de uma estrutura para poder acessar os campos individuais. Sugira inserir um nome de 'tag'

a main()função está faltando. Talvez seja onde você faria as chamadas:

double_list* list = create_list();
insert_back(list, 1);
insert_back(list, 2);
insert_back(list, 3);
sort_list(list);
destroy_list(list);

sugiro fortemente manter a lista classificada em 'insert ()' ao invés de como uma operação separada

Answer 3

Eu trataria Nodecomo uma classe, como você fez com double_list. Ou seja, criar funções node_create(), node_destroy()etc.
Deixe que as node_...()funções modifiquem / verifiquem o conteúdo do Node.