Implementación de lista doblemente vinculada

Question

Vengo de una experiencia en C ++, y recientemente entré en C, y una de las primeras cosas que hice fue una lista de doble enlace, ya que pensé que sería una buena práctica para mí con punteros y asignación de memoria. Sin embargo, no es demasiado complejo, solo tiene algunas funciones básicas.

Aquí está la descripción general de mi 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);

Solo tiene funciones básicas de inserción y eliminación, así como funciones de constructor, destructor, ordenación e inversión.

Aquí está la definición real de las funciones:

#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;
    }
}

Y aquí hay una pequeña muestra de cómo se usaría mi lista:

double_list* list = create_list();

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

sort_list(list);

destroy_list(list);

Mi principal área de preocupación son:

1. ¿El constructor y el destructor están haciendo su trabajo correctamente? ¿El destructor pierde memoria y hay una mejor manera de hacer el constructor?

2. ¿Son eficientes las funciones remove()y insert()? ¿Hay una mejor manera de hacerlo, como hacer una remove()función más genérica para no tener que tener casos de prueba especiales para el índice 0 y cosas así?

3. ¿Están bien las funciones sort()y reverse()al menos? Sé que el ordenamiento por selección no es el mejor algoritmo para usar. ¿Y la reverse()función está implementada correctamente? ¿Existe una mejor manera de invertir la lista?

Siento haber sido demasiado amplio con mi pregunta. Puedo editarlo para centrarme en una pregunta más específica si es necesario.

Gracias

Answer 1

¡Buena pregunta, bien formateada, bien elaborada y la implementación parece funcionar!

Primero en responder a sus preguntas:

Q1:

Constructor:

• Verifique el valor de retorno de malloc, podría ser NULLsi fallara (sin memoria)

Incinerador de basuras:

• simplemente pase double_list *list, constno tiene sentido (no estoy seguro de por qué lo puso allí).
• pierde memoria, porque no la libera list, que ha asignado en el constructor

Edición 1:

Si pasa, double_list *const listsignifica que el valor de la lista (el puntero) no se puede cambiar, lo que no tiene sentido aquí porque el usuario de esta interfaz se aferra al puntero.

Si constestá antes del tipo, const double_list *listesto significa que el contenido de donde apunta la lista no puede cambiar.

Por ejemplo, si tienes una función que toma una cadena y quieres comunicarle al usuario de esta función que el contenido de la cadena no va a cambiar, debes hacerlo void foo(const char *bar). Si la función es solo, foo(char *bar)el usuario no puede estar seguro de que el contenido de la cadena barsiga siendo el mismo después.

P2:

• No veo ningún problema con las funciones removey con insertrespecto al rendimiento. Insertar en el medio siempre será O (n). Quitar / insertar en la cabeza y la cola es O (1) que logra en su código.
• Sería un poco más intuitivo si implementara el caso simple de eliminar head / tail en la función remove_front/ remove_backy usara estas funciones en la remove_posfunción genérica .

Q3:

clasificación

• sort_list: lo que podría hacer es establecer una bandera cuando se ordena la lista para que, si se vuelve a ordenar, sea rápido (desmarcar la bandera cuando se agrega un elemento)
• de lo contrario, no veo ningún problema con la implementación de clasificación

contrarrestar

La implementación inversa de su lista es O (n), pero dado que tiene una lista doblemente vinculada, podría hacer uso de esto. Puede tener dos conjuntos de operaciones en la lista, uno opera en dirección de avance y el otro en retroceso. Siempre que reverse_listse llame, intercambiará el conjunto de funciones. Vea el ejemplo a continuación:

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;
}

Comentarios más generales:

Ocultar información privada

Filtra algunos de los detalles en el archivo h. Probablemente no desee que un usuario de su double_listbiblioteca pueda meterse con los nodos, por lo tanto, debe ocultarlo y agregar funciones para obtener el valor. El archivo h se vería así:

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);

Quitar la constante

Estás pasando double_list* const list, ¿qué estás tratando de lograr exactamente con el const?

Falta el protector de inclusión

Debes agregar lo siguiente:

#ifndef __DOUBLE_LIST_H__
#define __DOUBLE_LIST_H__

// snip

#endif

Eliminar las inclusiones en el archivo h

Las inclusiones deben ir solo en los archivos c. De lo contrario, puede encontrarse con inclusiones cíclicas.

la estrella del puntero se pega a la variable

por ejemplo, no es bueno: char* b

mejor: char *b

de lo contrario, se ve extraño si tiene la siguiente declaración:

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

Verificar NULL

Verifique el listargumento para NULL en las funciones

Verificar NULL después de asignar

Cuando asigna los nodos, también debe verificar si se mallocdevuelven NULL.

Pruebas

Cuando agrega a su lista, agrega el elemento en orden 1,2,3, por sort_listlo que no está haciendo mucho.

Nombrar las funciones

Cuando se trata de nombrar funciones, ciertamente se reduce al gusto personal, pero yo me quedaría con las expresiones comunes. Por ejemplo backy frontson un poco infrecuentes, pienso heady taildescribo mejor para qué funcionan.

También hace que su interfaz sea un poco más limpia si los nombra de manera 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()

Solo avíseme si algo no está claro, codereview "olvidó" la mitad de mi texto, así que me apresuré un poco a escribirlo de nuevo.

Answer 2

respecto a:

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

La mayoría de los depuradores utilizan el nombre de 'etiqueta' de una estructura para poder acceder a los campos individuales. Sugerir insertar un nombre de 'etiqueta'

main()falta la función. Quizás ahí es donde colocarías las llamadas:

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

sugiero encarecidamente mantener la lista ordenada en 'insertar ()' en lugar de como una operación separada

Answer 3

Lo trataría Nodecomo una clase, como lo hizo con usted double_list. Es decir, crear funciones node_create(), node_destroy()etc.
Deje que las node_...()funciones modifiquen / revisen el contenido del Nodo.