Doubly Linked List Program in C

What is a doubly linked list ?

A Doubly Linked List in C 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  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.

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;
};

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.

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

  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

  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

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Doubly Linked List

Doubly Linked List

  • Introduction to Doubly Linked list in Data Structure
    Click Here
  • Doubly Linked List in –
    C | C++ | Java
  • Insertion in doubly linked list –
    C | C++ | Java
  • Insertion at beginning in doubly linked list –
    C | C++ | Java
  • Insertion at end in doubly linked list –
    C | C++ | Java
  • Insertion at nth node in doubly linked list –
    C | C++ | Java
  • Deletion in doubly linked list  –
    C | C++ | Java
  • Deletion from beginning in doubly linked list :
  • Deletion from nth in doubly linked list :
    C | C++ | Java
  • Deletion from end in doubly linked list :
    C | C++ | Java
  • Insertion and Deletion in a  doubly linked list :
    C | C++ | Java
  • Insertion in the middle in a  doubly linked list :
    C | C++ | Java