Doubly Linked List Program in C

Last Updated on June 8, 2023 by Mayank Dham

We shall explore the definition and operation of a doubly linked list in this post. In addition, we will implement a doubly linked list program in C with a thorough description, a dry run, and an algorithm, and at the conclusion of the article, we will analyze the time and space costs associated with such a program.

What is a Doubly Linked List?

A doubly linked list is a data structure that consists of a sequence of elements, where each element contains a reference to the previous and next element in the sequence. In contrast to a singly linked list, which only has a reference to the next element, a doubly linked list allows traversal in both directions.
Each element in a doubly linked list, commonly called a "node," contains two pointers or references: one pointing to the previous node and another pointing to the next node. The first and last nodes of the list have their previous and next pointers set to null or a special value to indicate the beginning and end of the list.

The memory representation to the above mentioned illustration of a linked list with the colorized data denoting the information a doubly linked list holds i.e. previous address, next address and the data:-

There are different operations performed on a doubly linked which are demonstrated as:

• Traversal – Forward/Backward
• Insert – Start/End/Position
• Delete

In this article, we are going to create doubly linked list program in c that covers all of the operations mentioned. A doubly linked is created with the help of self-referential structure in C programming language.

struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};

The traversal to linked list requires the head node which is traversed until the head becomes zero. Though, in doubly linked list, traversal can be performed both the ways, courtesy of previous pointer.

Insert at Start – Doubly Linked List Program in C

Lets look at each operation that is going to be a subpart of the doubly linked list program in C. Firstly, we have the dry run, algorithm, code and analysis for the insert at the start operation.

Step To Insert at Start of Doubly Linked List
We assign the head to the ptr node and lets suppose that we have a newly created node temp containing the value want to link at start, the next of temp is addressed to ptr and the previous of ptr is addressed to temp. Finally, the head is updated to the temp (newly created node) with its previous being NULL.

Algorithm

Step 1: IF head = NULL
            Exit
Step 2: SET ptr = head
Step 3: SET temp -> data = data
Step 4: SET temp -> prev = NULL
Step 5: SET temp -> next = ptr
Step 6 SET ptr->prev = temp
Step 6: SET temp -> prev = NULL
Step 7: SET head = temp
Step 8: EXIT

void InsertAtStart(struct Node** head, int data)
{
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
 
    temp->data = new_data;
 
    temp->next = (*head);
    temp->prev = NULL;
 
    if ((*head) != NULL)
        (*head)->prev = temp;
 
    (*head) = temp;
}

Insert at End – Doubly Linked List Program in C

We assign the head node to ptr and traverse till the end node of the doubly linked list. Once the next of the node is NULL, we break out. Further step, temp is the newly created node and the next of traversed ptr node is set as temp with temp’s previous address set to ptr and next address set to NULL and returning head.

Algorithm

Step 1: IF head = NULL 
            Exit
Step 2: SET ptr = head
Step 3: While ptr->next != NULL
            ptr = ptr->next
Step 4: SET temp -> data = data
Step 5: SET temp -> prev = ptr
Step 6: SET temp -> next = NULL
Step 7 SET ptr->next = temp
Step 8: EXIT

void InsertAtEnd(struct Node** head, int data)
{
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    struct Node* ptr = *head; 
    
    temp->data = data
      
    if (*head == NULL) {
        ptr = temp;
        return;
    }
 
  
    while (ptr->next != NULL)
        ptr = ptr->next;
  	
    temp->next = NULL;
    ptr->next = temp;
 
    temp->prev = ptr;
 
    return;
}

Insert Before a Node – Doubly Linked List Program in C

Lets suppose we have the address to head node and a particular node named fixNode, as we need to insert a new node before fixNode. We assign head to ptr and traverse ptr till the next of ptr is not equal to fixNode, if head == fixNode then will insert the node at start and you can refer the Section 3 of this article.

Once we are done traversing, we have the previous address of fixNode in ptr, the new node named temp will point next address to fixNode and fixNode previous address will point to temp. The next address of ptr will point to temp and previous address of temp will point to ptr.

Algorithm

Step 1: IF head = NULL
            Exit
        If head == fixNode
            InsertAtStart(head,data)
            Exit
Step 2: SET ptr = head

Step 3: While ptr->next != fixNode
            ptr = ptr->next
Step 4: SET temp->data = data
Step 5: SET temp -> prev = ptr
Step 6: SET temp -> next = fixNode
Step 7 SET ptr->next = temp
Step 8: SET fixNode->prev = temp
Step 8: EXIT

void insertBefore(struct Node **head, struct Node* fixNode, int num){
    struct Node *ptr, *temp;

    temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = num;
  

    if (*head == fixNode) {
        temp->next = *head;
        (*head)->prev = temp;
        *head = temp;
        return;
    }

    ptr = *head;
    while (ptr->next != fixNode) {
        ptr = ptr->next;
    }

    temp->next = fixNode;
    temp->prev = ptr;
    ptr->next = temp;
    fixNode->prev = temp;
}

Delete A Node – Doubly Linked List Progam in C

To delete a node, we have an address to the node to be deleted namely, delNode. We check if the head node is NULL and return if that is the case.
Head is assigned to node named ptr and if ptr == delNode, head is shifted to immediate successor and ptr is deleted else,

Ptr is traversed till next of ptr is not equal to delNode, when we break out, ptr->next->next is assigned to temp. To delete, next of ptr is set to temp and previous of temp is set to ptr, resulting in deletion of delNode.

The purpose of this question was to adjoin the breakage in linked list that is going to exist upon the deletion of the node that is to be deleted.

Algorithm

Step 1: IF head = NULL
            Exit
        If head == nodetoDelete
            head = head->next
            delete nodetoDelete

Step 2: SET ptr = head
Step 3: While ptr->next != nodetoDelete
            ptr = ptr->next
Step 7 SET ptr->next = nodetoDelete.next
Step 8: IF nodetoDelete->next != NULL
            nodetoDelete->next->prev = ptr
Step 8: EXIT

void deleteNode(struct Node **head, struct Node *nodeToDelete) {
    if (*head == NULL) {
        return;
    }

    if (*head == nodeToDelete) {
        *head = (*head)->next;
        free(nodeToDelete);
        return;
    }

    struct Node *ptr = *head;
    while (ptr->next != nodeToDelete) {
        ptr = ptr->next;
    }

    ptr->next = nodeToDelete->next;
    if (nodeToDelete->next != NULL) {
        nodeToDelete->next->prev = ptr;
    }
    free(nodeToDelete);
}

Code – Compilation of Performed Operations

As discussed until now, a compilation of all operations such as traversal, insert at different positions and deletion can be found in the code attached below:

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

struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};
 

void InsertAtStart(struct Node** head, int data)
{
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
 
    temp->data = data;
 
    temp->next = (*head);
    temp->prev = NULL;
 
    if ((*head) != NULL)
        (*head)->prev = temp;
 
    (*head) = temp;
}

void insertBefore(struct Node **head, struct Node* fixNode, int num){
    struct Node *ptr, *temp;

    temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = num;
  

    if (*head == fixNode) {
        temp->next = *head;
        (*head)->prev = temp;
        *head = temp;
        return;
    }

    ptr = *head;
    while (ptr->next != fixNode) {
        ptr = ptr->next;
    }

    temp->next = fixNode;
    temp->prev = ptr;
    ptr->next = temp;
    fixNode->prev = temp;
}



void InsertAtEnd(struct Node** head, int data)
{
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    struct Node* ptr = *head; 
    
    if (*head == NULL) {
      	temp->data = data;
        ptr = temp;
        return;
    }
 
  
    while (ptr->next != NULL)
        ptr = ptr->next;
  	
    temp->data = data;
    temp->next = NULL;
    ptr->next = temp;
 
    temp->prev = ptr;
 
    return;
}

void deleteNode(struct Node **head, struct Node *nodeToDelete) {
    if (*head == NULL) {
        return;
    }

    if (*head == nodeToDelete) {
        *head = (*head)->next;
        free(nodeToDelete);
        return;
    }

    struct Node *ptr = *head;
    while (ptr->next != nodeToDelete) {
        ptr = ptr->next;
    }

    ptr->next = nodeToDelete->next;
    if (nodeToDelete->next != NULL) {
        nodeToDelete->next->prev = ptr;
    }
    free(nodeToDelete);
}

void print(struct Node* node)
{
  
    while (node != NULL) {
        printf(" %d ", node->data);
        node = node->next;
    }
}
 

int main()
{
    struct Node* head = NULL;
 
    InsertAtStart(&head, 6);
 
    InsertAtEnd(&head, 7);
    InsertAtEnd(&head, 1);
 
    deleteNode(&head, head->next->next);
 
    print(head);
 
    return 0;
}

Explanation: In a linked supposed to be 3->2->7->9->1. After performing the operation, the linked list will be 6->3->2->7->9->1. After that two consecutive insertion at end position is done, which turns the linked list as,
6->3->2->7->9->1->7->1 and at the end, a deletion is done on the third node resulting in final output of linked list as 6->3->7->9->1->7->1.

Conclusion
A doubly linked list is a data structure that allows bidirectional traversal and efficient insertion/deletion operations. It consists of nodes, each containing references to the previous and next nodes. While it offers advantages such as flexibility in traversal and efficient modifications, it also has some drawbacks like increased memory usage and added complexity in maintaining the list’s integrity.

FAQs related to Doubly Linked List Program in C:

Q1. How do I create a doubly linked list in C?
To create a doubly linked list in C, you need to define a structure to represent the nodes and implement functions to perform operations such as insertion, deletion, and traversal. You can use pointers to maintain the connections between the nodes.

Q2. How do I insert an element into a doubly linked list?
To insert an element into a doubly linked list, you need to create a new node, update the previous and next pointers of the neighboring nodes to include the new node and adjust the pointers of the new node accordingly. If the insertion is at the beginning or end of the list, special cases should be handled.

Q3. How do I delete an element from a doubly linked list?
To delete an element from a doubly linked list, you need to adjust the previous and next pointers of the neighboring nodes to exclude the node to be deleted. Additionally, you should free the memory occupied by the deleted node.

Q4. How do I traverse a doubly linked list?
To traverse a doubly linked list, you can start from the head (or tail) node and repeatedly follow the next pointers to access each node in order. Alternatively, you can start from the tail (or head) node and follow the previous pointers to traverse the list in reverse order.

Q5. How do I reverse a doubly linked list?
To reverse a doubly linked list, you need to swap the previous and next pointers of each node in the list. Initially, the head and tail pointers should be swapped, and then you can iterate through the list and update the pointers accordingly. Finally, the new head and tail should be adjusted.

Q6. How do I search for an element in a doubly linked list?
To search for an element in a doubly linked list, you can start from the head (or tail) node and compare the values of each node with the target value. If a match is found, you can return the node or its position. If the target is not found, you can continue traversing until the end of the list.

Q7. How do I free the memory allocated for a doubly linked list?
To free the memory allocated for a doubly linked list, you should iterate through the list, starting from the head (or tail) node, and free the memory occupied by each node. Make sure to update the previous and next pointers accordingly to avoid accessing freed memory. Finally, you can free the memory occupied by the head and tail pointers.