Doubly Linked List Program in C

In this article, we will study what a doubly linked list is and how a doubly linked list functions. Apart from this, we will be doing a doubly linked list program in C with a detailed explanation, dry run, algorithm and at the end of the article, we will be analysing the cost of a doubly linked list program in C in terms of time and space consumed.

What is a Doubly Linked List?

A Doubly Linked List is a special form of linked list that has an additional previous pointer with next pointer. The previous pointer contains the address to the node immediately previous to the current node whilst the next pointer holds the information to the next node. The illustration gives you clarity on what doubly list actual representation is like:-

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
In this article, we covered what is doubly linked list and how to implement doubly linked list program in c along with the dry, algorithm and analysis of the program.

For more of such articles, stay connected with PrepBytes and we hope to see you again with another insightful piece of information again.

Other C Programs

C Program for Binary Search
C Program to Add Two Numbers
C Program to Calculate Percentage of 5 Subjects
C Program to Convert Binary Number to Decimal Number
C Program to Convert Celsius to Fahrenheit
C Program to Convert Infix to Postfix
C Program to Find Area of Circle
C Program to Find Roots of Quadratic Equation
C program to Reverse a Linked List
C program to reverse a number
Ascending Order Program in C
Menu Driven Program For All Operations On Doubly Linked List in C
C Program for Armstrong Number
C Program For Merge Sort For Linked Lists
C program for performing Bubble sort on Linked List
Hello World Program in C
Perfect Number Program in C
Leap Year Program in C
Odd Even Program in C
Selection Sort Program in C
Linear Search Program in C
While Loop Program in C
C Program to Swap Two Numbers
Calculator Program in C Language
Simple Interest Program in C
Compound Interest Program in C
Priority Scheduling Program in C