Doubly Linked List in C

What is a doubly linked list in C?

A Doubly Linked List is a unique type of Data Structure where there are a chain of nodes, that are connected to one another using pointers, where any individual node has 3 components –

  1. Data
  2. Previous Pointer
  3. Next Pointer

For any node, its previous pointer contains the address of the previous node and the next pointer contains the address of the next node in the chain of nodes.

Link

Components in a Doubly Linked List Program in C

For writing the Doubly Linked List Program in C we need to know that Doubly Linked List generally has the following components –

  • Node – A single unit in Doubly Linked List (DLL) contains – Data, previous and next pointers.
  • Next Pointer – Contains the Address to the next node
  • Previous Pointer – Contains Addresses to the previous node
  • Data – Stores the data value
  • Head – The first node in DLL

Some variations of DLL also have a tail node pointer, which signifies that this node is the end node in DLL.

Why doubly linked list?

For Doubly Linked list in Data Structure in C, unlike singly Linked List, which only traverses in one direction. Doubly Linked List can traverse both in forwards and backwards direction.

As for any given node, we have both previous and next node addresses information available.

Syntax for creating a node

This  will create a new node in a doubly linked list which will be storing integer type of data

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

Insertion operation in doubly linked list

Following insertion operation can be performed on a doubly linked list.

  1. Insertion at beginning
  2. Insertion at end
  3. Insertion in between of nodes

Doubly Linked List Insertion at Beginning

Algorithm of insertion at the beginning

  • Create a new node
  • Assign its data value
  • Assign newly created node’s next ptr to current head reference. So, it points to the previous start node of the linked list address
  • Assign newly created node’s previous node to NULL
  • Assign the current head’s previous node to this new node
  • Change the head reference to the new node’s address.
Doubly Linked List in C

Objective : Doubly Linked List Program in Data Structure in C

Code (Insertion at Beginning)

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

struct Node { 
    int data;
    struct Node *next;
    struct Node *prev;
};
void insertStart(struct Node** head, int data){
    
    // creating memory for newNode
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    
    // assigning newNode's next as the current head 
    // Assign data & and make newNode's prev as NULL
    newNode->data = data;
    newNode->next = *head;
    newNode->prev = NULL;
    
    // if list already had item(s)
    // We need to make current head previous node as this new node
    if(*head != NULL)
        (*head)->prev = newNode;
    
    // change head to this newNode
    *head = newNode;
    
}
void display(struct Node* node)
{
    struct Node* end;
    printf("\nIn Forward Direction\n");
    while (node != NULL) {
        printf(" %d ", node->data);
        end = node;
        node = node->next;
    }
 
    printf("\nIn Backward direction \n");
    while (end != NULL) {
        printf(" %d ", end->data);
        end = end->prev;
    }
}
int main()
{
    struct Node* head = NULL;
    
    // Need '&' i.e. address as we need to change head
    insertStart(&head,1);
    insertStart(&head,2);
    insertStart(&head,3);
    
    // no need for '&' as head need not be changed
    // only doing traversal
    display(head);
    
    return 0;
}

Output

In Forward Direction
 3  2  1 
In Backward direction 
 1  2  3

Doubly Linked List Insertion at the end

Algorithm of insertion at the beginning

  • Create a new node
  • Assign its data value
  • Traverse till the end of the Linked List call this node temp
  • Assign newly created node’s next node to NULL
  • Assign newly created node’s previous node to temp
  • Assign Temp’s next node to this newly created node.
Doubly Linked List in C end

Code in C (Insertion at the End)

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

struct Node { 
    int data;
    struct Node *next;
    struct Node *prev;
};
void insertStart(struct Node** head, int data){
    
    // creating memory for newNode
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    
    // assigning newNode's next as the current head 
    // Assign data & and make newNode's prev as NULL
    newNode->data = data;
    newNode->next = *head;
    newNode->prev = NULL;
    
    // if list already had item(s)
    // We need to make current head previous node as this new node
    if(*head != NULL)
        (*head)->prev = newNode;
    
    // change head to this newNode
    *head = newNode;
    
}

void insertLast(struct Node** head, int data){
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));

    newNode->data = data;
    newNode->next = NULL;
    
    //need this if there is no node present in linked list at all
    if(*head==NULL){
        *head = newNode;
        newNode->prev = NULL;
        return;
    }
    
    struct Node* temp = *head;
    
    // traverse till the last node
    while(temp->next!=NULL)
        temp = temp->next;
    
    // assign last node's next to this new Node
    temp->next = newNode;
    // assign this new Node's previous to last node(temp)
    newNode->prev = temp;
}
void display(struct Node* node)
{
    struct Node* end;
    printf("\nIn Forward Direction\n");
    while (node != NULL) {
        printf(" %d ", node->data);
        end = node;
        node = node->next;
    }
 
    printf("\nIn Backward direction \n");
    while (end != NULL) {
        printf(" %d ", end->data);
        end = end->prev;
    }
}
int main()
{
    struct Node* head = NULL;
    
    // Need '&' i.e. address as we need to change head
    insertStart(&head,1);
    insertStart(&head,2);
    insertStart(&head,3);
    
    insertLast(&head,10);
    insertLast(&head,20);
    
    // no need for '&' as head need not be changed
    // only doing traversal
    display(head);
    
    return 0;
}

Output

In Forward Direction
 3  2  1  10  20 
In Backward direction 
20  10  1  2  3

Doubly Linked List Insertion after a position

Algorithm of insertion at the beginning

  • Create a new node
  • Assign its data value
  • Traverse till nth(pos) node lets call this temp
  • Assign newly created node’s next node to temp’s next node
  • Assign newly created node’s previous node to temp
  • Assign Temp’s next node to this newly created node.
Doubly Linked List in C position

Code in C (Insertion After a certain Position)

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

struct Node { 
    int data;
    struct Node *next;
    struct Node *prev;
};
void insertStart(struct Node** head, int data){
    
    // creating memory for newNode
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    
    // assigning newNode's next as the current head 
    // Assign data & and make newNode's prev as NULL
    newNode->data = data;
    newNode->next = *head;
    newNode->prev = NULL;
    
    // if list already had item(s)
    // We need to make current head previous node as this new node
    if(*head != NULL)
        (*head)->prev = newNode;
    
    // change head to this newNode
    *head = newNode;
    
}

void insertLast(struct Node** head, int data){
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));

    newNode->data = data;
    newNode->next = NULL;
    
    //need this if there is no node present in linked list at all
    if(*head==NULL){
        *head = newNode;
        newNode->prev = NULL;
        return;
    }
    
    struct Node* temp = *head;
    
    // traverse till the last node
    while(temp->next!=NULL)
        temp = temp->next;
    
    // assign last node's next to this new Node
    temp->next = newNode;
    // assign this new Node's previous to last node(temp)
    newNode->prev = temp;
}

int calcSize(struct Node* node){
    int size=0;

    while(node!=NULL){
        node = node->next;
        size++;
    }
    return size;
}

void insertPosition(int pos, int data, struct Node** head){
        int size = calcSize(*head);

    //If pos is 0 then should use insertStart method
    //If pos is less than 0 then can't enter at all
    //If pos is greater than size then bufferbound issue
    if(pos<1 || size < pos) 
    { 
        printf("Can't insert, %d is not a valid position\n",pos); 
    } 
    else{ 
        struct Node* temp = *head; 
        struct Node* newNode = (struct Node*) malloc(sizeof(struct Node)); 

        newNode->data = data;
        newNode->next = NULL;
        
        // traverse till pos
        while(--pos)
        {
            temp=temp->next;
        }
        
        // assign prev/next of this new node
        newNode->next = temp->next;
        newNode->prev = temp;
        
        // change next of temp node
        temp->next = newNode;
    }
}

void display(struct Node* node)
{
    struct Node* end;
    printf("\nIn Forward Direction\n");
    while (node != NULL) {
        printf("%d  ", node->data);
        end = node;
        node = node->next;
    }
 
    printf("\n\nIn Backward direction \n");
    while (end != NULL) {
        printf("%d  ", end->data);
        end = end->prev;
    }
}
int main()
{
    struct Node* head = NULL;
    
    // Need '&' i.e. address as we need to change head
    insertStart(&head,1);
    insertStart(&head,2);
    insertStart(&head,3);
    
    insertLast(&head,10);
    insertLast(&head,20);
    
    
    insertPosition(2, 100, &head);
    
    // no need for '&' as head need not be changed
    // only doing traversal
    display(head);
    
    return 0;
}

Output

In Forward Direction
3  2  100  1  10  20  

In Backward direction 
20  10  1  2  3

Advantages of using doubly linked list in C

  1. It saves time as we can traverse in both directions.
  2. It utilizes memory as we can construct and delete nodes according to our needs.
  3. Insertion and deletion of the node become efficient if the position is given.

Disadvantages of using doubly linked list in C

  1. Uses more memory per node.
  2. Insertion and deletion take more time because extra pointers need to be maintained.

Also, check the following page – 

Deletion in a Doubly Linked List in C

Singly Linked List

  • Introduction to Linked List in Data Structure
  • Linked List in – C | C++ | Java
  • Singly Linked List in – C | C++ | Java
  • Insertion in singly Linked List – C | C++ | Java
    • Insertion at beginning in singly Linked List  – C | C++Java
    • Insertion at nth position in singly Linked List  – C | C++Java
    • Insertion at end in singly Linked List  – C | C++Java
  • Deletion in singly Linked List  – C | C++Java
    • Deletion from beginning in singly linked list : C | C++ | Java
    • Deletion from nth position in singly linked list : C | C++ | Java
    • Deletion from end in singly linked list : C | C++ | Java
  • Reverse a linked list without changing links between nodes (Data reverse only) – C | C++Java
  • Linked List Insertion and Deletion – C | C++Java
  • Reverse a linked list by changing links between nodes – C | C++Java
  • Linked List insertion in the middle – C | C++Java
  • Print reverse of a linked list without actually reversing – C |C++ | Java
  • Search an element in a linked list – C | C++Java
  • Insertion in a Sorted Linked List – C | C++Java
  • Delete alternate nodes of a Linked List – C | C++Java
  • Find middle of the linked list – C | C++Java
  • Reverse a linked list in groups of given size – C | C++Java
  • Find kth node from end of the linked list – C | C++Java
  • Append the last n nodes of a linked list to the beginning of the list – C | C++Java
  • Check whether linked list is palindrome or not – C | C++Java
  • Fold a Linked List – C | C++Java
  • Insert at a given position – C | C++Java
  • Delete at a given position – C | C++Java

Singly Linked List

  • Introduction to Linked List in Data Structure
    Click Here
  • Linked List in –
    C | C++ | Java
  • Singly Linked List in –
    C | C++ | Java
  • Insertion in singly Linked List –
    C | C++ | Java
  • Insertion at beginning in singly Linked List  –
    C | C++Java
  • Insertion at nth position in singly Linked List  –
    C | C++Java
  • Insertion at end in singly Linked List  –
    C | C++Java
  • Deletion in singly Linked List  –
    C | C++Java
  • Deletion from beginning in singly linked list :
    C | C++ | Java
  • Deletion from nth position in singly linked list :
    C | C++ | Java
  • Deletion from end in singly linked list :
    C | C++ | Java
  • Linked List Insertion and Deletion –
    C | C++Java
  • Reverse a linked list without changing links between nodes (Data reverse only) –
    C | C++Java
  • Reverse a linked list by changing links between nodes –
    C | C++Java
  • Print reverse of a linked list without actually reversing –
    C |C++Java
  • Print reverse of a linked list without actually reversing –
    C |C++Java
  • Insertion in the middle Singly Linked List –
    C | C++Java
  • Insertion in a Sorted Linked List –
    C | C++Java
  • Delete alternate nodes of a Linked List –
    C | C++Java
  • Find middle of the linked list –
    C | C++Java
  • Reverse a linked list in groups of given size –
    C | C++Java
  • Find kth node from end of the linked list –
    C | C++Java
  • Append the last n nodes of a linked list to the beginning of the list –
    C | C++Java
  • Check whether linked list is palindrome or not –
    C | C++Java
  • Fold a Linked List –
    C | C++Java
  • Insert at given Position –
    C | C++Java
  • Deletion at given Position –
    C | C++Java