Implementing Doubly Linked List in C

Introduction

In this project, you will learn how to implement a doubly linked list data structure in C. A doubly linked list is a type of linked list where each node contains pointers to both its predecessor and successor nodes, allowing for efficient traversal in both forward and backward directions.

👀 Preview

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

🎯 Tasks

In this project, you will learn:

• How to initialize a doubly linked list
• How to traverse the doubly linked list and execute a callback function for each node
• How to insert a new node after a given node in the doubly linked list
• How to insert a new node before a given node in the doubly linked list
• How to delete a node from the doubly linked list

🏆 Achievements

After completing this project, you will be able to:

• Understand the basic structure and operations of a doubly linked list
• Implement the core functions required for managing a doubly linked list
• Demonstrate the ability to work with pointers and dynamic memory allocation in C
• Apply your knowledge to fix and improve the provided doubly linked list implementation

Skills Graph

Fixing Segmentation Faults

In this step, the free_list function does not update the current pointer after freeing a node, which will result in a segmentation fault. The glitch needs to be fixed now.

1. Locate the free_list() function in the list.c file.
2. Here's the updated free_list() function:

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

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

Insert a Node After a Given Node

In this step, you will learn how to insert a new node after a given node in the doubly linked list.

1. Locate the insert_after() function in the list.c file.
2. This function takes a struct List*, a struct Node* (the node to insert the new node after), and the data for the new node.
3. The function should create a new struct Node and initialize its data field with the provided data.
4. The function should then update the next and prev pointers of the new node and the prev node to insert the new node correctly.
5. Finally, the function should update the tail pointer if the new node is being inserted at the end of the list.

Here's the updated insert_after() function:

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) { // Updated
        newnode->next = prev->next;
        newnode->prev = prev;
        prev->next = newnode;
        if (newnode->next) newnode->next->prev = newnode;
        else list->tail = newnode; // Updated
    } else {
        newnode->next = list->head;
        newnode->prev = NULL;
        if (list->head) list->head->prev = newnode;
        else list->tail = newnode; // Updated
        list->head = newnode;
    }
}

6. Locate insert_after (list, NULL, data); and change to the following code:

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

Insert a Node Before a Given Node

In this step, you will learn how to insert a new node before a given node in the doubly linked list.

1. Locate the insert_before() function in the list.c file.
2. This function takes a struct List*, a struct Node* (the node to insert the new node before), and the data for the new node.
3. The function should create a new struct Node and initialize its data field with the provided data.
4. The function should then update the next and prev pointers of the new node and the next node to insert the new node correctly.
5. Finally, the function should update the head pointer if the new node is being inserted at the beginning of the list.

Here's the updated insert_before() function:

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) { // Updated
        newnode->prev = next->prev;
        newnode->next = next;
        next->prev = newnode;
        if (newnode->prev) newnode->prev->next = newnode;
        else list->head = newnode; // Updated
    } else {
        newnode->prev = list->tail;
        newnode->next = NULL;
        if (list->tail) list->tail->next = newnode;
        else list->head = newnode; // Updated
        list->tail = newnode;
    }
}

6. Locate insert_before (list, NULL, data); and change to the following code:

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

Delete a Node from the Doubly Linked List

In this step, you will learn how to delete a node from the doubly linked list.

1. Locate the delete_from() function in the list.c file.
2. This function takes a struct List* and a struct Node* (the node to be deleted).
3. The function should update the next and prev pointers of the neighboring nodes to remove the given node from the list.
4. The function should also update the head and tail pointers if the deleted node was the head or tail of the list.
5. Finally, the function should free the memory occupied by the deleted node.

Here's the updated delete_from() function:

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

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

    free(node);
}

Now, the doubly linked list implementation in the list.c file should be working correctly. You can use the provided test_list.c file to test the functionality of the doubly linked list. The test results are as follows:

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

Summary

Congratulations! You have completed this project. You can practice more labs in LabEx to improve your skills.