A doubly linked list is a dynamic data structure where each node contains two pointers: one pointing to the next node and one pointing to the previous node. This structure allows traversal in both forward and backward directions, making it more flexible than a singly linked list. Understanding doubly linked lists is essential for implementing advanced data structures like deques, stacks, and queues efficiently.
Understanding the Problem
Implementing a doubly linked list requires careful management of both the next and prev pointers during all operations. Errors in pointer assignment can break the list or cause runtime errors. Additionally, edge cases—such as empty lists or inserting/deleting at the first or last position—must be handled correctly to maintain the integrity of the list.
Program 1: Insertion and Display
This program demonstrates insertion at the beginning, end, and a specific position. It also includes functions to display the list in forward and backward order, showing how the prev and next pointers are managed.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
struct Node *prev;
} Node;
Node *head = NULL;
// Insert at the beginning
void insertAtBeginning(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
newNode->prev = NULL;
newNode->next = head;
if (head) head->prev = newNode;
head = newNode;
}
// Insert at the end
void insertAtEnd(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
if (!head) {
newNode->prev = NULL;
head = newNode;
return;
}
Node *temp = head;
while (temp->next) temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}
// Insert at a specific position
void insertAtPosition(int value, int pos) {
if (pos < 1) {
printf("Invalid position\n");
return;
}
if (pos == 1) {
insertAtBeginning(value);
return;
}
Node *temp = head;
for (int i = 1; i < pos - 1 && temp; i++) temp = temp->next;
if (!temp) {
printf("Position out of bounds\n");
return;
}
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
newNode->next = temp->next;
newNode->prev = temp;
if (temp->next) temp->next->prev = newNode;
temp->next = newNode;
}
// Display forward
void displayForward() {
if (!head) {
printf("Doubly Linked List is empty\n");
return;
}
Node *temp = head;
printf("Forward: ");
while (temp) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
// Display backward
void displayBackward() {
if (!head) {
printf("Doubly Linked List is empty\n");
return;
}
Node *temp = head;
while (temp->next) temp = temp->next; // Go to last node
printf("Backward: ");
while (temp) {
printf("%d ", temp->data);
temp = temp->prev;
}
printf("\n");
}
int main() {
insertAtBeginning(10);
insertAtEnd(20);
insertAtPosition(15, 2);
insertAtEnd(30);
printf("Current List:\n");
displayForward();
displayBackward();
return 0;
}This program allows insertion at multiple positions and demonstrates forward and backward traversal.
Program 2: Update a Node
This program allows updating a node’s value by searching for the old value. Updating is a common operation for modifying list contents without changing structure.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
struct Node *prev;
} Node;
Node *head = NULL;
// Insert at the end
void insertAtEnd(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
if (!head) {
newNode->prev = NULL;
head = newNode;
return;
}
Node *temp = head;
while (temp->next) temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}
// Display forward
void displayForward() {
if (!head) {
printf("Doubly Linked List is empty\n");
return;
}
Node *temp = head;
printf("Forward: ");
while (temp) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
void updateNode(int oldValue, int newValue) {
Node *temp = head;
while (temp) {
if (temp->data == oldValue) {
temp->data = newValue;
printf("Node updated from %d to %d\n", oldValue, newValue);
return;
}
temp = temp->next;
}
printf("Node with value %d not found\n", oldValue);
}
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
displayForward();
updateNode(20, 25);
displayForward();
return 0;
}This function traverses the list, finds the node with the given value, and updates it safely.
Program 3: Delete a Node
This program deletes a node at a given value, handling all cases: beginning, middle, and end of the list. Proper pointer updates ensure list integrity.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
struct Node *prev;
} Node;
Node *head = NULL;
// Insert at the end
void insertAtEnd(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
if (!head) {
newNode->prev = NULL;
head = newNode;
return;
}
Node *temp = head;
while (temp->next) temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}
// Display forward
void displayForward() {
if (!head) {
printf("Doubly Linked List is empty\n");
return;
}
Node *temp = head;
printf("Forward: ");
while (temp) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
void deleteNode(int value) {
if (!head) {
printf("List is empty\n");
return;
}
Node *temp = head;
while (temp && temp->data != value) temp = temp->next;
if (!temp) {
printf("Node with value %d not found\n", value);
return;
}
if (temp->prev) temp->prev->next = temp->next;
else head = temp->next; // Deleting first node
if (temp->next) temp->next->prev = temp->prev;
free(temp);
printf("Node with value %d deleted\n", value);
}
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
displayForward();
deleteNode(20);
displayForward();
return 0;
}This program safely deletes nodes and handles edge cases like deleting the first or last node.
Program 4: Delete at Beginning
This program deletes the first node in a doubly linked list. It updates the head pointer to the next node and ensures the prev pointer of the new head is set to NULL. This keeps the list structure valid after removal.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
struct Node *prev;
} Node;
Node *head = NULL;
// Insert at the end
void insertAtEnd(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
if (!head) {
newNode->prev = NULL;
head = newNode;
return;
}
Node *temp = head;
while (temp->next) temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}
// Display forward
void displayForward() {
if (!head) {
printf("Doubly Linked List is empty\n");
return;
}
Node *temp = head;
printf("Forward: ");
while (temp) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
// Delete at beginning
void deleteAtBeginning() {
if (!head) {
printf("List is empty\n");
return;
}
Node *temp = head;
head = head->next;
if (head) head->prev = NULL;
printf("Node at beginning with value %d deleted\n", temp->data);
free(temp);
}
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
displayForward();
deleteAtBeginning();
displayForward();
return 0;
}This deletes the first node and updates the head pointer correctly. It also ensures the new head’s prev pointer becomes NULL.
Program 5: Delete at End
This program deletes the last node from the doubly linked list. It traverses to the last node, disconnects it from the list, and then frees its memory. If there was only one node, the list becomes empty.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
struct Node *prev;
} Node;
Node *head = NULL;
// Insert at the end
void insertAtEnd(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
if (!head) {
newNode->prev = NULL;
head = newNode;
return;
}
Node *temp = head;
while (temp->next) temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}
// Display forward
void displayForward() {
if (!head) {
printf("Doubly Linked List is empty\n");
return;
}
Node *temp = head;
printf("Forward: ");
while (temp) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
// Delete at end
void deleteAtEnd() {
if (!head) {
printf("List is empty\n");
return;
}
Node *temp = head;
while (temp->next) temp = temp->next;
if (temp->prev) temp->prev->next = NULL;
else head = NULL; // only one node
printf("Node at end with value %d deleted\n", temp->data);
free(temp);
}
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
displayForward();
deleteAtEnd();
displayForward();
return 0;
}This deletes the last node by moving to the end and unlinking it. If the list has one node, it becomes empty.
Program 6: Delete at Specific Position
This program deletes a node at a given position (1-based index). It checks if the position exists, then safely adjusts pointers to remove the node. This ensures no dangling links remain in the list.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
struct Node *prev;
} Node;
Node *head = NULL;
// Insert at the end
void insertAtEnd(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
if (!head) {
newNode->prev = NULL;
head = newNode;
return;
}
Node *temp = head;
while (temp->next) temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}
// Display forward
void displayForward() {
if (!head) {
printf("Doubly Linked List is empty\n");
return;
}
Node *temp = head;
printf("Forward: ");
while (temp) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
// Delete at specific position
void deleteAtPosition(int pos) {
if (!head) {
printf("List is empty\n");
return;
}
Node *temp = head;
int i = 1;
while (temp && i < pos) {
temp = temp->next;
i++;
}
if (!temp) {
printf("Position %d out of range\n", pos);
return;
}
if (temp->prev) temp->prev->next = temp->next;
else head = temp->next;
if (temp->next) temp->next->prev = temp->prev;
printf("Node at position %d with value %d deleted\n", pos, temp->data);
free(temp);
}
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
insertAtEnd(40);
displayForward();
deleteAtPosition(2);
displayForward();
return 0;
}This deletes the node at the given position. It makes sure pointers are updated and memory freed properly.
Program 7: Search in a Doubly Linked List
This program searches for a specific value in the list. It traverses the nodes one by one, keeping track of their positions. If found, it reports the position; otherwise, it confirms the value is missing.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
struct Node *prev;
} Node;
Node *head = NULL;
// Insert at the end
void insertAtEnd(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
if (!head) {
newNode->prev = NULL;
head = newNode;
return;
}
Node *temp = head;
while (temp->next) temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}
// Display forward
void displayForward() {
if (!head) {
printf("Doubly Linked List is empty\n");
return;
}
Node *temp = head;
printf("Forward: ");
while (temp) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
// Search a value
void searchValue(int value) {
Node *temp = head;
int pos = 1;
while (temp) {
if (temp->data == value) {
printf("Value %d found at position %d\n", value, pos);
return;
}
temp = temp->next;
pos++;
}
printf("Value %d not found\n", value);
}
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
insertAtEnd(40);
displayForward();
searchValue(30);
searchValue(100);
return 0;
}This searches the list for a given value and shows its position. If the value is missing, it prints a not-found message.
FAQs
Q1: Can a doubly linked list be traversed backward?
Yes, the prev pointer allows traversal from the last node to the first.
Q2: What is the time complexity for insertion or deletion at a specific position?
O(n), as traversal may be required to reach the position.
Q3: Can nodes be updated?
Yes, traverse the list to locate the node and modify its data.
Q4: Is extra memory required compared to a singly linked list?
Yes, each node has an additional prev pointer, increasing memory usage slightly.
Conclusion
Doubly linked lists allow flexible insertion, deletion, updating, and traversal in both directions. Proper handling of next and prev pointers ensures the list remains robust. Mastering this structure provides a foundation for more advanced data structures and dynamic list operations.
References & Additional Resources
The following books and online resources provide both theoretical foundations and practical examples to help you understand more on the topic.
- Kernighan, B. W., & Ritchie, D. M. (1988). The C Programming Language (2nd Edition). Prentice Hall – Classic reference on C fundamentals, including pointers and memory, critical for linked list operations.
- Thareja, R. (2011). Data Structures Using C. Oxford University Press – Detailed coverage of linked lists, dynamic memory allocation, and related algorithms.
- GeeksforGeeks: Doubly Linked List in C – Introduction to concepts, structure, and implementation details of doubly linked lists.
- Programiz: Data Structures – Doubly Linked List – Beginner-friendly guide with clear examples for insertion and deletion.
- Tutorialspoint: What is Dynamic Memory Allocation in C? – Explanation of
malloc(),calloc(),realloc(), andfree()functions for memory management. - C Standard Library Documentation – Memory Management – Official reference for memory allocation and deallocation functions in C.
