A Doubly Linked List is a linear data structure consisting of nodes where each node contains three components:
- Data: The actual value stored in the node.
- Pointer to the Next Node: Points to the next node in the list.
- Pointer to the Previous Node: Points to the previous node in the list.
Unlike a Singly Linked List, a Doubly Linked List allows traversal in both forward and backward directions.
Structure of a Doubly Linked List Node
In C, a node for a Doubly Linked List is defined as follows:
struct Node {
int data; // Data part
struct Node* next; // Pointer to the next node
struct Node* prev; // Pointer to the previous node
};
Characteristics of Doubly Linked Lists
- Bidirectional Traversal: Can traverse the list in both directions.
- Dynamic Size: The size can be adjusted during runtime.
- Efficient Insertions/Deletions: Compared to arrays, insertions and deletions are easier and faster.
Operations on Doubly Linked List
1. Traversal
a. Forward Traversal
void traverseForward(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf(“%d -> “, temp->data);
temp = temp->next;
}
printf(“NULL\n”);
}
b. Backward Traversal
void traverseBackward(struct Node* tail) {
struct Node* temp = tail;
while (temp != NULL) {
printf(“%d -> “, temp->data);
temp = temp->prev;
}
printf(“NULL\n”);
}
2. Insertion
a. Insert at the Beginning
void insertAtBeginning(struct Node** head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->prev = NULL;
newNode->next = *head;
if (*head != NULL) {
(*head)->prev = newNode;
}
*head = newNode;
}
b. Insert at the End
void insertAtEnd(struct Node** head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if (*head == NULL) {
newNode->prev = NULL;
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
c. Insert After a Given Node
void insertAfter(struct Node* prevNode, int value) {
if (prevNode == NULL) {
printf(“Previous node cannot be NULL.\n”);
return;
}
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = prevNode->next;
newNode->prev = prevNode;
if (prevNode->next != NULL) {
prevNode->next->prev = newNode;
}
prevNode->next = newNode;
}
3. Deletion
a. Delete from the Beginning
void deleteFromBeginning(struct Node** head) {
if (*head == NULL) {
printf(“List is empty.\n”);
return;
}
struct Node* temp = *head;
*head = temp->next;
if (*head != NULL) {
(*head)->prev = NULL;
}
free(temp);
}
b. Delete from the End
void deleteFromEnd(struct Node** head) {
if (*head == NULL) {
printf(“List is empty.\n”);
return;
}
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
if (temp->prev != NULL) {
temp->prev->next = NULL;
} else {
*head = NULL; // List becomes empty
}
free(temp);
}
c. Delete a Specific Node
void deleteByValue(struct Node** head, int value) {
if (*head == NULL) {
printf(“List is empty.\n”);
return;
}
struct Node* temp = *head;
// Search for the node to delete
while (temp != NULL && temp->data != value) {
temp = temp->next;
}
if (temp == NULL) {
printf(“Value not found.\n”);
return;
}
if (temp->prev != NULL) {
temp->prev->next = temp->next;
} else {
*head = temp->next; // Deleting the head node
}
if (temp->next != NULL) {
temp->next->prev = temp->prev;
}
free(temp);
}
4. Searching
Finding a specific value in the list.
void search(struct Node* head, int value) {
struct Node* temp = head;
int position = 1;
while (temp != NULL) {
if (temp->data == value) {
printf(“Value %d found at position %d.\n”, value, position);
return;
}
temp = temp->next;
position++;
}
printf(“Value %d not found.\n”, value);
}
Example Program
#include <stdio.h>
#include <stdlib.h>
// Node structure
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
// Function prototypes
void insertAtEnd(struct Node** head, int value);
void deleteFromBeginning(struct Node** head);
void traverseForward(struct Node* head);
int main() {
struct Node* head = NULL;
insertAtEnd(&head, 10);
insertAtEnd(&head, 20);
insertAtEnd(&head, 30);
printf(“Doubly Linked List after insertion:\n”);
traverseForward(head);
deleteFromBeginning(&head);
printf(“Doubly Linked List after deletion:\n”);
traverseForward(head);
return 0;
}
// Function implementations
void insertAtEnd(struct Node** head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if (*head == NULL) {
newNode->prev = NULL;
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
void deleteFromBeginning(struct Node** head) {
if (*head == NULL) {
printf(“List is empty.\n”);
return;
}
struct Node* temp = *head;
*head = temp->next;
if (*head != NULL) {
(*head)->prev = NULL;
}
free(temp);
}
void traverseForward(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf(“%d -> “, temp->data);
temp = temp->next;
}
printf(“NULL\n”);
}
Output Example
Doubly Linked List after insertion:
10 -> 20 -> 30 -> NULL
Doubly Linked List after deletion:
20 -> 30 -> NULL
Advantages of Doubly Linked List
- Bidirectional Traversal: Can traverse in both forward and backward directions.
- Efficient Deletion/Insertion: Easy to delete or insert nodes from both ends.
- No Wastage of Memory: Unlike arrays, there is no need for memory resizing.
Disadvantages of Doubly Linked List
- More Memory Overhead: Each node requires additional memory for the prev pointer.
- Complex Implementation: Requires managing two pointers for each node.
Applications of Doubly Linked List
- Navigation Systems: Forward and backward navigation in music players or browsers.
- Implementation of Deques: Efficient for double-ended queues.
- Undo/Redo Functionality: Used in applications with undo/redo operations.