Before starting this tutorial, make sure to check out Linked Lists: One Step at a Time! to understand the basics of singly linked lists first.
First Step: What is a doubly linked list node made up of?
Explanation:
A doubly linked list is made up of nodes, just like a singly linked list.
Each node contains some data and TWO pointers: one to the next node and one to the previous node.
This allows traversal in both directions (forward and backward).
Define a structure for the node that includes an integer and pointers to both next and previous nodes.
Code:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
Second Step: Creating Two Nodes and Linking Them
Explanation:
Create two nodes.
Set the first node's next pointer to the second node.
Set the second node's previous pointer to the first node.
Set the first node's previous pointer to NULL (start of list).
Set the second node's next pointer to NULL (end of list).
Assign values to the nodes using scanf.
Code:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
int main() {
struct Node* first = (struct Node*)malloc(sizeof(struct Node));
struct Node* second = (struct Node*)malloc(sizeof(struct Node));
printf("Enter value for the first node: ");
scanf("%d", &first->data);
first->prev = NULL;
first->next = second;
printf("Enter value for the second node: ");
scanf("%d", &second->data);
second->prev = first;
second->next = NULL;
free(first);
free(second);
return 0;
}
Third Step: Creating Three Nodes and Linking Them
Explanation:
Create three nodes.
Link them in a chain where each node points to the next and previous nodes.
The first node's previous pointer is NULL.
The last node's next pointer is NULL.
Code:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
int main() {
struct Node* first = (struct Node*)malloc(sizeof(struct Node));
struct Node* second = (struct Node*)malloc(sizeof(struct Node));
struct Node* third = (struct Node*)malloc(sizeof(struct Node));
printf("Enter value for the first node: ");
scanf("%d", &first->data);
first->prev = NULL;
first->next = second;
printf("Enter value for the second node: ");
scanf("%d", &second->data);
second->prev = first;
second->next = third;
printf("Enter value for the third node: ");
scanf("%d", &third->data);
third->prev = second;
third->next = NULL;
free(first);
free(second);
free(third);
return 0;
}
Fourth Step: Creating a Doubly Linked List of 10 Nodes in a Loop
Explanation:
Create a doubly linked list with 10 nodes using a loop.
Use a head pointer to point to the first node.
Use temporary pointers to build the list.
Each new node must link to the previous node (if any).
Use scanf to get values for each node from the user.
Code:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
int main() {
struct Node* head = NULL;
struct Node* temp = NULL;
struct Node* newNode = NULL;
for (int i = 0; i < 10; i++) {
newNode = (struct Node*)malloc(sizeof(struct Node));
printf("Enter value for node %d: ", i + 1);
scanf("%d", &newNode->data);
newNode->next = NULL;
newNode->prev = NULL;
if (head == NULL) {
head = newNode;
} else {
temp->next = newNode;
newNode->prev = temp;
}
temp = newNode;
}
return 0;
}
Fifth Step: Printing the Doubly Linked List (Forward and Backward)
Explanation:
Write functions to print the list in both directions.
For forward traversal, start from head and move using next pointers.
For backward traversal, first find the tail, then move using prev pointers.
Print the data of each node.
Code:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
void printListForward(struct Node* head) {
struct Node* temp = head;
printf("Forward: ");
while (temp != NULL) {
printf("%d <-> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
void printListBackward(struct Node* head) {
struct Node* temp = head;
if (temp == NULL) return;
while (temp->next != NULL) {
temp = temp->next;
}
printf("Backward: ");
while (temp != NULL) {
printf("%d <-> ", temp->data);
temp = temp->prev;
}
printf("NULL\n");
}
int main() {
struct Node* head = NULL;
struct Node* temp = NULL;
struct Node* newNode = NULL;
for (int i = 0; i < 5; i++) {
newNode = (struct Node*)malloc(sizeof(struct Node));
printf("Enter value for node %d: ", i + 1);
scanf("%d", &newNode->data);
newNode->next = NULL;
newNode->prev = NULL;
if (head == NULL) {
head = newNode;
} else {
temp->next = newNode;
newNode->prev = temp;
}
temp = newNode;
}
printListForward(head);
printListBackward(head);
temp = head;
while (temp != NULL) {
struct Node* next = temp->next;
free(temp);
temp = next;
}
return 0;
}
Sixth Step: Adding a Node to the Beginning
Explanation:
Write a function that takes a double pointer to the head of the list.
Create a new node, assign its value from the function parameter.
Make the new node's next pointer point to the current head.
If head exists, update its previous pointer to point to the new node.
Update the head to point to the new node.
Use printListForward to print the updated list.
Code:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
void printListForward(struct Node* head) {
struct Node* temp = head;
printf("Forward: ");
while (temp != NULL) {
printf("%d <-> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
void addNodeAtBeginning(struct Node** pointerToHead, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = *pointerToHead;
newNode->prev = NULL;
if (*pointerToHead != NULL) {
(*pointerToHead)->prev = newNode;
}
*pointerToHead = newNode;
}
int main() {
struct Node* head = NULL;
struct Node* temp = NULL;
struct Node* newNode = NULL;
for (int i = 0; i < 3; i++) {
newNode = (struct Node*)malloc(sizeof(struct Node));
printf("Enter value for node %d: ", i + 1);
scanf("%d", &newNode->data);
newNode->next = NULL;
newNode->prev = NULL;
if (head == NULL) {
head = newNode;
} else {
temp->next = newNode;
newNode->prev = temp;
}
temp = newNode;
}
int newValue;
printf("Enter value for the new node at the beginning: ");
scanf("%d", &newValue);
addNodeAtBeginning(&head, newValue);
printListForward(head);
temp = head;
while (temp != NULL) {
struct Node* next = temp->next;
free(temp);
temp = next;
}
return 0;
}
Seventh Step: Inserting a Node After the Nth Node
Explanation:
Write a function that takes the head of the list, a position n, and a value.
Traverse the list to find the nth node.
If the nth node exists, create a new node.
Update the links: new node's prev points to nth node, new node's next points to nth node's next.
If nth node's next exists, update its prev to point to new node.
Update nth node's next to point to new node.
Code:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
void printListForward(struct Node* head) {
struct Node* temp = head;
printf("Forward: ");
while (temp != NULL) {
printf("%d <-> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
void insertNodeAfterNth(struct Node* head, int n, int value) {
struct Node* temp = head;
for (int i = 0; i < n; i++) {
if (temp == NULL) return;
temp = temp->next;
}
if (temp != NULL) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = temp->next;
newNode->prev = temp;
if (temp->next != NULL) {
temp->next->prev = newNode;
}
temp->next = newNode;
}
}
int main() {
struct Node* head = NULL;
head = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->prev = NULL;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->data = 2;
head->next->prev = head;
head->next->next = (struct Node*)malloc(sizeof(struct Node));
head->next->next->data = 3;
head->next->next->prev = head->next;
head->next->next->next = NULL;
printf("Original list:\n");
printListForward(head);
int n = 1, value = 99;
insertNodeAfterNth(head, n, value);
printf("After inserting %d after position %d:\n", value, n);
printListForward(head);
struct Node* temp = head;
while (temp != NULL) {
struct Node* next = temp->next;
free(temp);
temp = next;
}
return 0;
}
Eighth Step: Deleting the Head Node
Explanation:
Write a function that takes a double pointer to the head of the list.
If the list is not empty, save the current head.
Make the head point to the second node.
If the new head exists, update its prev pointer to NULL.
Free the memory of the old head node.
Code:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
void printListForward(struct Node* head) {
struct Node* temp = head;
printf("Forward: ");
while (temp != NULL) {
printf("%d <-> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
void deleteHeadNode(struct Node** head) {
if (*head != NULL) {
struct Node* temp = *head;
*head = (*head)->next;
if (*head != NULL) {
(*head)->prev = NULL;
}
free(temp);
}
}
int main() {
struct Node* head = NULL;
head = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->prev = NULL;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->data = 2;
head->next->prev = head;
head->next->next = (struct Node*)malloc(sizeof(struct Node));
head->next->next->data = 3;
head->next->next->prev = head->next;
head->next->next->next = NULL;
printf("Original list:\n");
printListForward(head);
deleteHeadNode(&head);
printf("After deleting head:\n");
printListForward(head);
struct Node* temp = head;
while (temp != NULL) {
struct Node* next = temp->next;
free(temp);
temp = next;
}
return 0;
}
Ninth Step: Deleting a Node with a Specific Value
Explanation:
Write a function that takes a double pointer to the head of the list and a value.
Traverse the list to find the node with the given value.
If found, update the links to bypass the node.
Handle three cases: deleting head node, deleting middle node, deleting tail node.
Free the memory of the deleted node.
Code:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
void printListForward(struct Node* head) {
struct Node* temp = head;
printf("Forward: ");
while (temp != NULL) {
printf("%d <-> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
void deleteNodeWithValue(struct Node** head, int value) {
struct Node* temp = *head;
while (temp != NULL && temp->data != value) {
temp = temp->next;
}
if (temp == NULL) return;
if (temp == *head) {
*head = temp->next;
if (*head != NULL) {
(*head)->prev = NULL;
}
}
else {
if (temp->prev != NULL) {
temp->prev->next = temp->next;
}
if (temp->next != NULL) {
temp->next->prev = temp->prev;
}
}
free(temp);
}
int main() {
struct Node* head = NULL;
head = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->prev = NULL;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->data = 2;
head->next->prev = head;
head->next->next = (struct Node*)malloc(sizeof(struct Node));
head->next->next->data = 3;
head->next->next->prev = head->next;
head->next->next->next = NULL;
printf("Original list:\n");
printListForward(head);
int valueToDelete = 2;
deleteNodeWithValue(&head, valueToDelete);
printf("After deleting node with value %d:\n", valueToDelete);
printListForward(head);
struct Node* temp = head;
while (temp != NULL) {
struct Node* next = temp->next;
free(temp);
temp = next;
}
return 0;
}
Bonus Step: Reversing a Doubly Linked List
Explanation:
Write a function that reverses the entire doubly linked list.
Traverse the list and swap the next and prev pointers for each node.
Update the head to point to the last node (which becomes the new first node).
Code:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
void printListForward(struct Node* head) {
struct Node* temp = head;
printf("Forward: ");
while (temp != NULL) {
printf("%d <-> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
void reverseList(struct Node** head) {
struct Node* temp = NULL;
struct Node* current = *head;
while (current != NULL) {
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}
if (temp != NULL) {
*head = temp->prev;
}
}
int main() {
struct Node* head = NULL;
head = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->prev = NULL;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->data = 2;
head->next->prev = head;
head->next->next = (struct Node*)malloc(sizeof(struct Node));
head->next->next->data = 3;
head->next->next->prev = head->next;
head->next->next->next = (struct Node*)malloc(sizeof(struct Node));
head->next->next->next->data = 4;
head->next->next->next->prev = head->next->next;
head->next->next->next->next = NULL;
printf("Original list:\n");
printListForward(head);
reverseList(&head);
printf("Reversed list:\n");
printListForward(head);
struct Node* temp = head;
while (temp != NULL) {
struct Node* next = temp->next;
free(temp);
temp = next;
}
return 0;
}