Double linked lists

A doubly linked list is a type of linked list where traversal is possible in both directions. This is because each node contains two pointers: one pointing to the previous node and the other pointing to the next node in the list. This allows moving forward and backward through the list efficiently.

• The first node in a doubly linked list has its previous pointer set to NULL, indicating it’s the start of the list.
• Similarly, the last node has its next pointer set to NULL, indicating the end of the list.

struct Node {
    int data;             // data can be any type : int , char, arrays, structures, etc.
    struct Node* next;     // Pointer to the next node
    struct Node* prev;     // Pointer to the previous node
};

Example

Managing nodes in a double linked list

1. Traversing through nodes in a list
2. Adding a node to list
   • Add at the end of list
   • Add at the beginning of list
3. Deleting a node from list
   • Delete first node
   • Delete last node
   • Delete a selected node

1. Traversing through nodes

Traversing through nodes in a double linked list is just like in a singly linked list, the last node in a doubly linked list has its next pointer set to NULL, indicating the end of the list.

struct Node *tmp = head; //assigning head node to a temporary pointer

while (tmp != NULL) {
            /* print each node's data */
             printf("Data = %d\n", tmp->data);
             tmp = tmp->data;
}

2. Adding a node

Adding at the end

In this approach, the new node becomes the first node of the list, and its next pointer will point to the current first node (head). The head pointer is then updated to point to this new node.

void add_tail(struct node **head)
{
        struct node *tmp;
        struct node *new_node;
        int val;

        printf("enter a value to insert:");
        scanf("%d", &val);
        new_node = (struct node*)calloc(1, sizeof(struct node));
        new_node->data = val;
        new_node->next = new_node->prev = NULL;
        if (*head == NULL)
                *head = new_node;
        else {
                tmp = *head;
                while (tmp->next != NULL)
                        tmp = tmp->next;
                tmp->next = new_node;
                new_node->prev = tmp;
        }
}

Adding at the beginning

In this approach, the new node becomes the first node of the list, and its next pointer will point to the current first node (head). The head pointer is then updated to point to this new node.

void add_head(struct node **head)                                                                              
{
        struct node *new_node = NULL;
        int val;

        new_node = (struct node*)calloc(1, sizeof(struct node));
        printf("enter a value to insert:");
        scanf("%d", &val);
        new_node->data = val;
        new_node->next = new_node->prev = NULL;
        if (*head == NULL)
                *head = new_node;

        new_node->next = *head;
        (*head)->prev = new_node;
        *head = new_node;
}

2. Deleting a node

To delete a node from a double linked list, it involves removing an existing node from the list while maintaining the structure.

Deleting first node

The first node (pointed to by the head) is removed. To do this, the head pointer is updated to point to the second node in the list. The first node is then deallocated or freed. And the new head node’s previous pointer have to update with NULL.

void delete_first_node(struct node **head)
{
        struct node *tmp;

        if (*head == NULL) {
                printf("list empty\n");
                return;
        }
        tmp = *head;
        *head = tmp->next;
        if (*head)
                (*head)->prev = NULL;
        free(tmp);
}

Deleting last node

To delete the last node in a doubly linked list, first traverse to the last node. Once at the last node, move to the previous node using the last node’s previous pointer. Then, set the next pointer of this previous node to NULL, disconnecting the last node. Finally, free the memory of the last node to complete the deletion process.

void delete_last_node(struct node **head)
{       
        struct node *tmp;
        
        if (*head == NULL) {
                printf("list empty\n");
                return;
        }
        if ((*head)->next == NULL) {
                free(*head);
                *head = NULL;
                return;
        }
        tmp = *head;
        while (tmp->next->next != NULL)
                tmp = tmp->next;
        free(tmp->next);
        tmp->next = NULL;
}

Deleting a selected node

To delete a node in the middle of the list (or a specific node), first, traverse the list to find the node that precedes the one to be deleted. Update the previous node’s next pointer to point to the node after the one being deleted, effectively bypassing the node to delete. Finally, deallocate the selected node.

void delete_node(struct node **head)
{
        int val;
        struct node *tmp, *node;

        if (head == NULL) {
                printf("List empty\n");
                return;
        }
        printf("enter value to delete:");
        scanf("%d", &val);

        if ((*head)->data == val) {
                tmp = (*head)->next;
                if (tmp)
                        tmp->prev = NULL;
                free(*head);
                *head = tmp;
                return;
        }
        tmp = *head;
        while (tmp->next != NULL && tmp->next->data != val) {
                tmp = tmp->next;
        };
        if (tmp->next == NULL) {
                printf("node not found with val:%d\n", val);
                return;
        }
        printf("deleting a node\n");
        node = tmp->next;
        tmp->next = node->next;
        if (node->next)
                node->next->prev = tmp;
        free(node);
}

Github link for data structures applications here