Doubly linked list in C

Doublu linked list in C programming

What is doubly linked list in C?

Doubly linked list in C are the advance and complex type of linked list that give user an ease to traverse through the linked list in both the directions that is from head to tail as well as from tail to head. The starting node of linked list is termed as head and last node is termed as tail.Unlike singly linked list each node of doubly linked list is divided into three parts previous, data and next.

  • Previous :- It stores the address of previous node.
  • Data :- It stores the value of the node.
  • Next :- It stores the address of next node.

 

Why doubly linked list?

This question that why do we need doubly linked list when singly linked list are already there?  is very obvious. The diagram besides will help you understand this concept. Doubly linked list nodes are made up of three parts previous, data and next. This division of nodes in three parts helps us in moving through out the list easily saving our time thus these doubly linked lists are necessary.

Doubly Linked list in C PrepInsta

Construction of in C

We use user defined data types to build a doubly linked list, i.e. we make a structure in C for constructing doubly linked list. We design a user defined struct data type, that contains a datatype, for storing the desired data and  a pointer variable for storing the address of the next node and previous node in the doubly linked list.

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   
{  
    struct node *prev;   
    int data;  
    struct node *next;   
}   

Advantages of using doubly linked list in C

  1. It saves time as we can traverse in both the direction.
  2. It utilizes memory as we can construct and delete nodes according to our need.
  3. Insertion and deletion of the node becomes efficient if the position id given.

Disadvantages of using doubly linked list in C

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

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.

Deletion operation in doubly linked list.

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

  1. Deletion at beginning
  2. Deletion at end
  3. Deletion of a specific node.
Doubly Linked List in C

Code for Implementing Doubly Linked List in C

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

struct node { 
    int num;
    struct node * preptr;
    struct node * nextptr;
}*start_node, *end_node; //Creating node.
 

void creation(int n);
void display();

int main()
{
    int n;
    start_node = NULL;
    end_node = NULL;
	
    printf("Enter the number of nodes:");
    scanf("%d", &n);
 
    creation(n); 
    display();
    return 0;
}
 
void creation(int n)//Function to create list.
{
    int i, num;
    struct node *fnNode;
 
    if(n >= 1)
    {
        start_node = (struct node *)malloc(sizeof(struct node));
 
        if(start_node != NULL)
        {
            printf("Enter data for 1 node:"); 
            scanf("%d", &num);
 
            start_node->num = num;
            start_node->preptr = NULL;
            start_node->nextptr = NULL;
            end_node = start_node;
           
            for(i=2; i<=n; i++)
            {
                fnNode = (struct node *)malloc(sizeof(struct node));
                if(fnNode != NULL)
                {
                    printf("Enter data for %d node:",i);
                    scanf("%d", &num);  //Accepting data for the nodes.
                    fnNode->num = num;
                    fnNode->preptr = end_node;    //New node linked with previous node.
                    fnNode->nextptr = NULL;
 
                    end_node->nextptr = fnNode;   //Linking previous node with the new node
                    end_node = fnNode;            //Making new node as last node.
                }
                else
                {
                    printf(" Memory can not be allocated.");
                    break;
                }
            }
        }
        else
        {
            printf("Memory can not be allocated.");
        }
    }
}
void display()
{
    struct node * tmp;
    int n = 1;
    if(start_node == NULL)
    {
        printf("Empty List");
    }
    else
    {
        tmp = start_node;
        printf("Data entered is:\n");
 
        while(tmp != NULL)
        {
            printf("node %d : %d\n", n, tmp->num);//Printing every node.
            n++;
            tmp = tmp->nextptr; 
        }
    }
}
Output:
Enter the number of nodes:5
Enter data for 1 node:11
Enter data for 2 node:22
Enter data for 3 node:33
Enter data for 4 node:44
Enter data for 5 node:55
Data entered is:
node 1 : 11
node 2 : 22
node 3 : 33
node 4 : 44
node 5 : 55