Implementar lista doblemente enlazada en C | Tutorial de programación

Introducción

En este proyecto, aprenderás a implementar una estructura de datos de lista doblemente enlazada en C. Una lista doblemente enlazada es un tipo de lista enlazada donde cada nodo contiene punteros a tanto su nodo predecesor como a su nodo sucesor, lo que permite un recorrido eficiente en ambas direcciones, hacia adelante y hacia atrás.

👀 Vista previa

$ gcc test_list.c list.c -o test
$./test
welcome
to
labex
online

🎯 Tareas

En este proyecto, aprenderás:

Cómo inicializar una lista doblemente enlazada
Cómo recorrer la lista doblemente enlazada y ejecutar una función de devolución de llamada para cada nodo
Cómo insertar un nuevo nodo después de un nodo dado en la lista doblemente enlazada
Cómo insertar un nuevo nodo antes de un nodo dado en la lista doblemente enlazada
Cómo eliminar un nodo de la lista doblemente enlazada

🏆 Logros

Después de completar este proyecto, serás capaz de:

Comprender la estructura básica y las operaciones de una lista doblemente enlazada
Implementar las funciones esenciales necesarias para el manejo de una lista doblemente enlazada
Demostrar la capacidad de trabajar con punteros y la asignación dinámica de memoria en C
Aplicar tus conocimientos para corregir y mejorar la implementación de la lista doblemente enlazada proporcionada

Corrigiendo errores de segmentación

En este paso, la función free_list no actualiza el puntero current después de liberar un nodo, lo que resultará en un error de segmentación. Ahora se debe corregir este problema.

Localiza la función free_list() en el archivo list.c.
Aquí está la función free_list() actualizada:

void free_list(struct List* list) {
    struct Node* current = list->head;
    struct Node* next = NULL;

    while (current) {
        next = current->next;
        free(current);
        current = next; // Actualizado
    }
    free(list);
}

Insertar un nodo después de un nodo dado

En este paso, aprenderás a insertar un nuevo nodo después de un nodo dado en la lista doblemente enlazada.

Localiza la función insert_after() en el archivo list.c.
Esta función toma un struct List*, un struct Node* (el nodo después del cual se insertará el nuevo nodo) y los data del nuevo nodo.
La función debe crear un nuevo struct Node e inicializar su campo data con los data proporcionados.
Luego, la función debe actualizar los punteros next y prev del nuevo nodo y del nodo prev para insertar el nuevo nodo correctamente.
Finalmente, la función debe actualizar el puntero tail si el nuevo nodo se está insertando al final de la lista.

Aquí está la función insert_after() actualizada:

void insert_after(struct List* list, struct Node* prev, void* data) {
    struct Node* newnode = (struct Node *) malloc(sizeof(struct Node));
    newnode->data = data;

    if (prev) { // Actualizado
        newnode->next = prev->next;
        newnode->prev = prev;
        prev->next = newnode;
        if (newnode->next) newnode->next->prev = newnode;
        else list->tail = newnode; // Actualizado
    } else {
        newnode->next = list->head;
        newnode->prev = NULL;
        if (list->head) list->head->prev = newnode;
        else list->tail = newnode; // Actualizado
        list->head = newnode;
    }
}

Localiza insert_after (list, NULL, data); y cambia a el siguiente código:

insert_after (list, list->tail, data);

Insertar un nodo antes de un nodo dado

En este paso, aprenderás a insertar un nuevo nodo antes de un nodo dado en la lista doblemente enlazada.

Localiza la función insert_before() en el archivo list.c.
Esta función toma un struct List*, un struct Node* (el nodo antes del cual se insertará el nuevo nodo) y los data del nuevo nodo.
La función debe crear un nuevo struct Node e inicializar su campo data con los data proporcionados.
Luego, la función debe actualizar los punteros next y prev del nuevo nodo y del nodo next para insertar el nuevo nodo correctamente.
Finalmente, la función debe actualizar el puntero head si el nuevo nodo se está insertando al principio de la lista.

Aquí está la función insert_before() actualizada:

void insert_before(struct List* list, struct Node* next, void* data) {
    struct Node* newnode = (struct Node *) malloc(sizeof(struct Node));
    newnode->data = data;

    if (next) { // Actualizado
        newnode->prev = next->prev;
        newnode->next = next;
        next->prev = newnode;
        if (newnode->prev) newnode->prev->next = newnode;
        else list->head = newnode; // Actualizado
    } else {
        newnode->prev = list->tail;
        newnode->next = NULL;
        if (list->tail) list->tail->next = newnode;
        else list->head = newnode; // Actualizado
        list->tail = newnode;
    }
}

Localiza insert_before (list, NULL, data); y cambia a el siguiente código:

insert_before (list, list->head, data);

Eliminar un nodo de la lista doblemente enlazada

En este paso, aprenderás a eliminar un nodo de la lista doblemente enlazada.

Localiza la función delete_from() en el archivo list.c.
Esta función toma un struct List* y un struct Node* (el nodo que se va a eliminar).
La función debe actualizar los punteros next y prev de los nodos adyacentes para eliminar el nodo dado de la lista.
La función también debe actualizar los punteros head y tail si el nodo eliminado era el head o el tail de la lista.
Finalmente, la función debe liberar la memoria ocupada por el nodo eliminado.

Aquí está la función delete_from() actualizada:

void delete_from(struct List* list, struct Node* node) {
    if (node->prev) node->prev->next = node->next;
    else list->head = node->next; // Actualizado

    if (node->next) node->next->prev = node->prev;
    else list->tail = node->prev; // Actualizado

    free(node);
}

Ahora, la implementación de la lista doblemente enlazada en el archivo list.c debería funcionar correctamente. Puedes usar el archivo test_list.c proporcionado para probar la funcionalidad de la lista doblemente enlazada. Los resultados de las pruebas son los siguientes:

$ gcc test_list.c list.c -o test
$./test
welcome
to
labex
online

Resumen

¡Felicidades! Has completado este proyecto. Puedes practicar más laboratorios en LabEx para mejorar tus habilidades.

Implementar una lista doblemente enlazada en C