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.
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.
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.
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
What is a doubly linked list?
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.
Can you traverse a doubly linked list both forwards and backwards?
Yes, we can traverse a doubly linked list in both directions due to the presence of both next and previous pointers.
What is the time complexity for inserting or deleting a node in a doubly linked list?
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).
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.
