Doubly Linked List Program in C : With Code Examples

Updated on September 28, 2024

Article Outline

Doubly linked list is a more complex data structure. It is a type of the linked list data structure but it possesses some advantages. The most basic advantages of a linked list, such that it allows traversal efficiently along the list in both directions. It is because every node in the list has included a pointer to the previous node and a pointer to the next node. Doubly linked allows easy insertion and deletion of nodes. This article explains everything about the Doubly Linked List.

What is a Doubly Linked List?

The doubly linked list represents a type of linked data structure with nodes that contain three parts the data, a pointer to the next node in the sequence, and a pointer to the previous node. It offers traversal in both forward and backward directions, any position within the list and insertion may be performed at that point.

Doubly Linked List Program in C

*Image
Get curriculum highlights, career paths, industry insights and accelerate your technology journey.
Download brochure

Components in a Doubly Linked List

In the doubly linked list program in C language, we must define the following components in a Doubly Linked List.

 

  • Node: It is the basic unit of a doubly linked list. Nodes are linked together using a pointer. Each node stores the data item, the next pointer, and the previous pointer.
  • Next Pointer: It stores the address of the next node in the sequence in a doubly linked list.
  • Previous Pointer: This stores the address of the previous node in the sequence in a doubly linked list.
  • Data: This stores the data value of the node.
  • Heads: It represents the start of the doubly linked list.

Doubly Linked List Program in C

Operations on Doubly Linked List

With a doubly linked list, we can perform many operations. Later in the article, we will discuss the method and implementation of each operation below.

 

  • Traversing: It refers to visiting each node of the linked list from the head pointer until the end of the list. It is mainly performed to carry out a particular operation, such as displaying data in every node or searching for a node in the list.
  • Insertion: It is the process of adding nodes in the doubly linked list at the specific point or end of the linked list.
  • Insertion at the beginning: In this case, a new node is inserted before the doubly linked list. Then, the head pointer is updated to point to the newly added node.
  • Insertion at the end: In this case, a new node is inserted at the end of the doubly linked list. The head pointer does not need to be changed.
  • Insertion after a given node: In this case, given a pointer to a node in the doubly linked list, we need to insert the new node after the node whose pointer is given to use.
  • Insertion before a given node: It is given to a node. The goal is to insert the new node before the node whose pointer is given.
  • Deletion: We can also delete the node from the doubly linked list and maintain its structure after the operations.
  • Deletion at the beginning: We can delete the first node from the doubly linked list by making the head pointer point to the next node in the doubly linked list. The node is then deleted from memory.
  • Deletion at the end: The last node of the doubly linked list is removed.
  • Deletion of the node at a given position: We need to delete the node at the specified position from the doubly linked list.
  • Searching: We can also search elements in the doubly linked list by comparing the data of each node in the linked list with the item given to be searched. The location or address of the node is returned as the output. This can again be used to access the same node if required. It returns NULL output when no such node is found.

Inserting a Node at the Front of the Doubly Linked List

Here is the algorithm for inserting a node in the doubly linked list.

 

  • Allocate memory for a new node and set its data. Let’s call this node a new node.
  • Assign the next pointer of new_node to the head.
  • If the head pointer is not NULL, then assign the prev pointer of the head to the new_node.
  • Then, update the head pointer.

 

Program

#include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node* next; struct Node* prev; } Node; Node* createNode(int data) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = data; newNode->next = NULL; newNode->prev = NULL; return newNode; } void printList(Node* head) { Node* temp = head; while (temp != NULL) { printf("%d ", temp->data); temp = temp->next; } printf("n"); } void insertOne(Node** head, int data, int index) { Node* newNode = createNode(data); if (index == 0) { newNode->next = *head; if (*head != NULL) { (*head)->prev = newNode; } *head = newNode; return; } Node* temp = *head; int currentIndex = 0;   while (temp != NULL && currentIndex < index - 1) { temp = temp->next; currentIndex++; }   if (temp == NULL) { free(newNode); printf("Index out of bounds. Inserting at the end instead.n"); return; } newNode->next = temp->next; newNode->prev = temp; if (temp->next != NULL) { temp->next->prev = newNode; } temp->next = newNode; }   void freeList(Node** head) { Node* current = *head; Node* nextNode; while (current != NULL) { nextNode = current->next; free(current); current = nextNode; }  *head = NULL; }  int main() {  Node* head = NULL; printf("Doubly linked list after inserting at end: "); printList(head); insertOne(&head, 20, 1); printf("After inserting 20 at index 1: "); printList(head); insertOne(&head, 50, 0); printf("After inserting 50 at index 0: "); printList(head); insertOne(&head, 60, 10); printf("After attempting to insert 60 at index 10: "); printList(head); freeList(&head); return 0; }

Output

Doubly linked list after inserting at end: Index out of bounds. Inserting at the end instead. After inserting 20 at index 1: After inserting 50 at index 0: 50 Index out of bounds. Inserting at the end instead. After attempting to insert 60 at index 10: 50

Complexity Analysis

  • Time Complexity: O(1)
  • Space Complexity:  O(1)

Inserting a Node at the End of the Doubly Linked List

We can insert a node at the end of a doubly linked list, by following this algorithm.

 

  • Create a temporary pointer ptr. Then initialize it to the head pointer.
  • The ptr-> next is not NULL, and move to the next node.
  • Now, we can create a new node with data new_node .
  • Then assign ptr->next to the new_node and assign new_node -> prev to ptr.

 

Program

#include <stdio.h> #include <stdlib.h>  struct Node { int data; struct Node* next; struct Node* prev; };  struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; newNode->next = NULL; newNode->prev = NULL; return newNode; }  void insertAtEnd(struct Node** head_ref, int new_data) { struct Node* newNode = createNode(new_data);  if (*head_ref == NULL) { *head_ref = newNode; return; } struct Node* last = *head_ref; while (last->next != NULL) { last = last->next; }  last->next = newNode; newNode->prev = last; }  void printList(struct Node* node) { printf("Traversal in forward direction: n"); while (node != NULL) { printf("%d ", node->data); node = node->next; } printf("n"); }  int main() { struct Node* head = NULL;  insertAtEnd(&head, 10); insertAtEnd(&head, 20); insertAtEnd(&head, 30); insertAtEnd(&head, 50) ; insertAtEnd(&head,90)  ; insertAtEnd(&head, 200) ; insertAtEnd(&head, 500) ; printList(head);  return 0; }

Output

Traversal in forward direction: 10 20 30 50 90 200 500

Inserting a Node in Between Two Nodes of the Doubly Linked List

To add the node, after which we have to insert the new node.  You have to follow this algorithm to follow the doubly linked list.

 

  • Create a new node with the given data.
  • Assign that new node to the next node
  • Assign the node to the next to new_node
  • Then check, if the new_node is not NULL, then assign the new_node-> next – >prev to new_node.

 

Program

#include <stdio.h> #include <stdlib.h>  struct Node { int data; struct Node* next; struct Node* prev; };  struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; newNode->next = NULL; newNode->prev = NULL; return newNode; }  void insertAfter(struct Node* prev_node, int new_data) { if (prev_node == NULL) { printf("The given previous node cannot be NULLn"); return; }  struct Node* newNode = createNode(new_data); newNode->next = prev_node->next; prev_node->next = newNode; newNode->prev = prev_node;  if (newNode->next != NULL) { newNode->next->prev = newNode; }}  void printList(struct Node* node) { printf("Traversal in forward direction: n"); while (node != NULL) { printf("%d ", node->data); node = node->next; } printf("n"); }   int main() { struct Node* head = createNode(10); head->next = createNode(20); head->next->prev = head; head->next->next = createNode(30); head->next->next->prev = head->next;   printf("Original List:n"); printList(head);  insertAfter(head->next, 25);  printf("Modified List after inserting 25 after 20:n"); printList(head);  return 0; }

Output

Original List: Traversal in forward direction: 10 20 30 Modified List after inserting 25 after 20: Traversal in forward direction: 10 20 25 30

Deleting a Node at the Beginning of the Doubly Linked List

Deleting nodes from the beginning is easy. We have to follow the following steps.

 

  • First, You have to initialize a pointer curr to the head pointer.
  • If the head pointer is not NULL, then increment the head pointer.
  • Then make the curr pointer as NULL and free the memory.

 

Program

#include <stdio.h> #include <stdlib.h>  struct Node { int data; struct Node* next; };  struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; newNode->next = NULL; return newNode; }  void deleteAtFirst(struct Node** head_ref) { if (*head_ref == NULL) { printf("List is empty, nothing to delete.n"); return; }  struct Node* temp = *head_ref; *head_ref = temp->next;  free(temp); }  void printList(struct Node* node) { printf("Linked List: "); while (node != NULL) { printf("%d -> ", node->data); node = node->next; } printf("NULLn"); }  int main() { struct Node* head = createNode(10); head->next = createNode(20); head->next->next = createNode(30);  printf("Original List:n"); printList(head);  deleteAtFirst(&head);  printf("List after deleting the first node:n"); printList(head);  deleteAtFirst(&head); deleteAtFirst(&head);  return 0; }

Output

Original List: Linked List: 10 -> 20 -> 30 -> NULL List after deleting the first node: Linked List: 20 -> 30 -> NULL List is empty, nothing to delete.

Deleting a Code at the End of the Doubly Linked List

Deleting the node from the end of the doubly linked list is a crucial operation for understanding it.

 

  • Initialize a pointer curr to the head pointer.
  • Then curr-> next to not NULL, the increment the curr pointer.
  • Update the curr-> prev-> next as NULL and curr -> prev as NULL.
  • Then make the curr pointer as NULL and free the memory.

 

 

Program

#include <stdio.h> #include <stdlib.h>  struct Node { int data; struct Node* next; struct Node* prev; };  struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; newNode->next = NULL; newNode->prev = NULL; return newNode; }  void deleteLastNode(struct Node** head) { if (*head == NULL) { printf("The list is empty.n"); return; }  struct Node* temp = *head;  if (temp->next == NULL) { free(temp); *head = NULL; return; }  while (temp->next != NULL) { temp = temp->next; }  temp->prev->next = NULL; free(temp); }  void displayList(struct Node* node) { if (node == NULL) { printf("The list is empty.n"); return; }  printf("Doubly Linked List: "); while (node != NULL) { printf("%d ", node->data); node = node->next; } printf("n"); }  void appendNode(struct Node** head, int data) { struct Node* newNode = createNode(data); if (*head == NULL) { *head = newNode; return; }  struct Node* temp = *head; while (temp->next != NULL) { temp = temp->next; } temp->next = newNode; newNode->prev = temp; } int main() { struct Node* head = NULL;  appendNode(&head, 10); appendNode(&head, 20); appendNode(&head, 30); appendNode(&head, 40); appendNode(&head,  909 ) ;  printf("Before deletion:n"); displayList(head); deleteLastNode(&head); printf("After deletion:n"); displayList(head); while (head != NULL) { struct Node* temp = head; head = head->next; free(temp); }  return 0; }

Output

Before deletion: Doubly Linked List: 10 20 30 40 909 After deletion: Doubly Linked List: 10 20 30 40

Deleting a Node at a Specified Position of the Doubly Linked List

In this section, we must delete the Node at a specified position in the doubly linked list.

 

  • If the user selects position 1, we must delete the node at the front.
  • Iterate a pointer curr until position >1
  • Now, we need to remove the curr node and connect curr-> prev and curr -> next.
  • Assign the curr node to the prev node and to next to curr and curr-> next to curr -> prev.

 

Program

#include <stdio.h> #include <stdlib.h>  struct Node { int data; struct Node* next; struct Node* prev; };  struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; newNode->next = NULL; newNode->prev = NULL; return newNode; }  void deleteNodeAtPosition(struct Node** head, int position) { if (*head == NULL || position < 0) { printf("Invalid position or the list is empty.n"); return; }  struct Node* temp = *head;  if (position == 0) { *head = temp->next; if (*head != NULL) { (*head)->prev = NULL; } free(temp); return; }  for (int i = 0; temp != NULL && i < position; i++) { temp = temp->next; }  if (temp == NULL) { printf("Position does not exist in the list.n"); return; }  if (temp->next != NULL) { temp->next->prev = temp->prev; } if (temp->prev != NULL) { temp->prev->next = temp->next; }  free(temp); }  void displayList(struct Node* node) { if (node == NULL) { printf("The list is empty.n"); return; }  printf("Doubly Linked List: "); while (node != NULL) { printf("%d ", node->data); node = node->next; } printf("n"); } void appendNode(struct Node** head, int data) { struct Node* newNode = createNode(data); if (*head == NULL) { *head = newNode; return; } struct Node* temp = *head; while (temp->next != NULL) { temp = temp->next; } temp->next = newNode; newNode->prev = temp; } int main() { struct Node* head = NULL; appendNode(&head, 10); appendNode(&head, 20); appendNode(&head, 30); appendNode(&head, 40); printf("Before deletion:n"); displayList(head); int position; printf("Enter the position of the node to delete (0-based index): "); scanf("%d", &position); deleteNodeAtPosition(&head, position); printf("After deletion:n"); displayList(head); while (head != NULL) { struct Node* temp = head; head = head->next; free(temp); } return 0; }

Output

Before deletion: Doubly Linked List: 10 20 30 40 Enter the position of the node to delete (0-based index):

Conclusion

In this article, we learned about the doubly linked list in C language, which is dynamic data with ease and efficiency. Each allows each node to reference its next and previous neighbours’ operations, such as insertion and deletion, without extensive traversal. A bidirectional capability is particularly beneficial in scenarios requiring frequent updates or complex data manipulation. Understanding doubly linked lists lays the groundwork for mastering more advanced data structures and algorithms. It is a valuable skill for any programmer aiming to build robust software solutions.

FAQs
A doubly linked list is a data structure in which each node contains three components: data, a pointer to the next node, and a pointer to the previous node. It allows traversal in both directions.
Yes, we can traverse a doubly linked list in both directions due to the presence of both next and previous pointers.
The time complexity for insertion or deletion at a known position is O(1). However, if the position is unknown, traversing the list to find it requires O(n).

Updated on September 28, 2024

Link
left dot patternright dot pattern

Programs tailored for your success

Popular

Management

Data Science

Finance

Technology

Future Tech

Upskill with expert articles

View all
Hero Vired logo
Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.
Blogs
Reviews
Events
In the News
About Us
Contact us
Learning Hub
18003093939     ·     hello@herovired.com     ·    Whatsapp
Privacy policy and Terms of use

|

Sitemap

© 2024 Hero Vired. All rights reserved