Before we move on to talking about doubly linked lists, let’s review what we already know about singly linked lists and then consider the improvements and extra features that doubly linked lists offer.
#include <stdio.h>
#include <stdlib.h>
// Define the structure of a node
struct Node {
int data;
struct Node* next;
};- Insert at the Beginning
- Insert at the End
- Delete a Node
- Display List
Let’s move on to the doubly linked list, which provides greater versatility while building on the previously taught notions.
Introduction: Doubly Linked List (DLL)
An expansion of a single linked list is a doubly linked list. The main difference is that every node has an extra pointer that leads to the node before it, enabling bidirectional traversal.
Consider this scenario you have a group of friends (named A, B, C, and D) standing in a line,
Friend A is holding hands with B.
B is holding hands with A on the left and C on the right.
C is holding hands with B on the left and D on the right.
D is holding hands with C.
So, if you want to go from A to D:You go from A to B, B to C, and C to D.
And if you want to go back from D to A:
You go from D to C, C to B, and B to A.
A doubly linked list, resembling a line of friends holding hands, is a useful tool in programming for moving in both directions, though it’s more complex and occupies more space.
In a doubly linked list, each node has three parts:
- Data part to store the data.
- Pointer to the next node in the list.
- Pointer to the previous node in the list.
Syntax Of Doubly Linked List
The purpose of the additional pointers in a doubly linked list causes major differences in syntax between singly and doubly linked lists in C, despite certain similarities.
typedef struct Node {
int data;
struct Node* next;
struct Node* prev;
} Node;A doubly linked list node contains:
- An integer data value.
- A pointer to the next node.
- A pointer to the previous node.
Basic Operations
- Node Definition: You require an appropriate node definition in order to carry out fundamental actions on a doubly list. This provides the structure for storing the data as well as references to the nodes that come before and after it.
typedef struct Node {
int data;
struct Node* next;
struct Node* prev;
} Node;As you might notice, it’s also the same as it’s syntax.
2. Creation of a Node: Memory must normally be allocated dynamically, and pointers must be initialized to NULL when a new node is created.
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}Example
#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));
if (newNode == NULL) {
printf("Memory allocation failed\n");
return NULL;
}
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
void traverseForward(Node* head) {
Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
void traverseBackward(Node* head) {
if (head == NULL) {
return;
}
Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->prev;
}
printf("\n");
}
int main() {
// Creating individual nodes
Node* head = createNode(1);
Node* second = createNode(2);
Node* third = createNode(3);
Node* fourth = createNode(4);
// Linking nodes to form the doubly linked list
head->next = second;
second->prev = head;
second->next = third;
third->prev = second;
third->next = fourth;
fourth->prev = third;
printf("Forward traversal: ");
traverseForward(head);
printf("Backward traversal: ");
traverseBackward(head);
// Freeing the allocated memory
free(fourth);
free(third);
free(second);
free(head);
return 0;
}In this example:
- We create four individual nodes with values 1, 2, 3, 4.
- We link these nodes to form a doubly linked list.
- We traverse the list forward from the head to the end, printing each node’s data.
- We traverse the list backward from the end to the head, printing each node’s data.
- We free the allocated memory to prevent memory leaks.
Forward traversal: 1 2 3 4
Backward traversal: 4 3 2 1Don’t worry; we’ll explore how to traverse a doubly linked list and other related context.
3. Insertion:
- Inserting at the Front: Insert a node at the beginning of the list.
void insertAtFront(Node** head, int data) {
Node* newNode = createNode(data);
newNode->next = *head;
if (*head != NULL) {
(*head)->prev = newNode;
}
*head = newNode;
}- Insertion at the End: Insert a node at the end of the list.
void insertAtEnd(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}- Inserting a Node After a Given Node:
To insert a node after or before a specified node in a doubly linked list, the involved nodes’ next and previous pointers need to be carefully updated.
void insertAfter(Node* prevNode, int data) {
if (prevNode == NULL) {
printf("The given previous node cannot be NULL\n");
return;
}
Node* newNode = createNode(data);
newNode->next = prevNode->next;
newNode->prev = prevNode;
if (prevNode->next != NULL) {
prevNode->next->prev = newNode;
}
prevNode->next = newNode;
}Inserting a Node Before a Given Node:
void insertBefore(Node** head, Node* nextNode, int data) {
if (nextNode == NULL) {
printf("The given next node cannot be NULL\n");
return;
}
Node* newNode = createNode(data);
newNode->prev = nextNode->prev;
newNode->next = nextNode;
if (nextNode->prev != NULL) {
nextNode->prev->next = newNode;
} else {
// If the new node is inserted before the head node
*head = newNode;
}
nextNode->prev = newNode;
}Use Case Example
This is a detailed example showing how to make use of these functions:
#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 insertAfter(Node* prevNode, int data) {
if (prevNode == NULL) {
printf("The given previous node cannot be NULL\n");
return;
}
Node* newNode = createNode(data);
newNode->next = prevNode->next;
newNode->prev = prevNode;
if (prevNode->next != NULL) {
prevNode->next->prev = newNode;
}
prevNode->next = newNode;
}
void insertBefore(Node** head, Node* nextNode, int data) {
if (nextNode == NULL) {
printf("The given next node cannot be NULL\n");
return;
}
Node* newNode = createNode(data);
newNode->prev = nextNode->prev;
newNode->next = nextNode;
if (nextNode->prev != NULL) {
nextNode->prev->next = newNode;
} else {
// If the new node is inserted before the head node
*head = newNode;
}
nextNode->prev = newNode;
}
void traverseForward(Node* head) {
Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int main() {
Node* head = NULL;
Node* first = createNode(1);
Node* second = createNode(2);
Node* third = createNode(3);
head = first;
first->next = second;
second->prev = first;
second->next = third;
third->prev = second;
printf("Original list: ");
traverseForward(head);
insertAfter(second, 4);
printf("After inserting 4 after second node: ");
traverseForward(head);
insertBefore(&head, second, 5);
printf("After inserting 5 before second node: ");
traverseForward(head);
return 0;
}Output
Original list: 1 2 3
After inserting 4 after second node: 1 2 4 3
After inserting 5 before second node: 1 5 2 4 34. Deletion: Same as traversing a node, you must update the next and prev pointers appropriately when deleting nodes from it. You can delete a node from:
- From the Front: Remove a node from the beginning of the list.
void deleteFromFront(Node** head) {
if (*head == NULL) {
printf("The list is already empty\n");
return;
}
Node* temp = *head;
*head = (*head)->next;
if (*head != NULL) {
(*head)->prev = NULL;
}
free(temp);
}- From the End: Remove a node from the end of the list.
void deleteFromEnd(Node** head) {
if (*head == NULL) {
printf("The list is already empty\n");
return;
}
Node* temp = *head;
// Traverse to the last node
while (temp->next != NULL) {
temp = temp->next;
}
// If there's only one node in the list
if (temp->prev == NULL) {
*head = NULL;
} else {
temp->prev->next = NULL;
}
free(temp);
}- Given Node: Remove a specific node from the list.
void deleteGivenNode(Node** head, Node* del) {
if (*head == NULL || del == NULL) {
printf("The list or the given node is NULL\n");
return;
}
if (*head == del) {
*head = del->next;
}
if (del->next != NULL) {
del->next->prev = del->prev;
}
if (del->prev != NULL) {
del->prev->next = del->next;
}
free(del);
}Use Case Examples
#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 insertAtEnd(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
void deleteFromFront(Node** head) {
if (*head == NULL) {
printf("The list is already empty\n");
return;
}
Node* temp = *head;
*head = (*head)->next;
if (*head != NULL) {
(*head)->prev = NULL;
}
free(temp);
}
void deleteFromEnd(Node** head) {
if (*head == NULL) {
printf("The list is already empty\n");
return;
}
Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
if (temp->prev == NULL) {
*head = NULL;
} else {
temp->prev->next = NULL;
}
free(temp);
}
void deleteGivenNode(Node** head, Node* del) {
if (*head == NULL || del == NULL) {
printf("The list or the given node is NULL\n");
return;
}
if (*head == del) {
*head = del->next;
}
if (del->next != NULL) {
del->next->prev = del->prev;
}
if (del->prev != NULL) {
del->prev->next = del->next;
}
free(del);
}
void traverseForward(Node* head) {
Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int main() {
Node* head = NULL;
insertAtEnd(&head, 1);
insertAtEnd(&head, 2);
insertAtEnd(&head, 3);
insertAtEnd(&head, 4);
printf("Original list: ");
traverseForward(head);
deleteFromFront(&head);
printf("After deleting from front: ");
traverseForward(head);
deleteFromEnd(&head);
printf("After deleting from end: ");
traverseForward(head);
deleteGivenNode(&head, head->next); // Delete the second node
printf("After deleting given node: ");
traverseForward(head);
return 0;
}Output
Original list: 1 2 3 4
After deleting from front: 2 3 4
After deleting from end: 2 3
After deleting given node: 25 . Traversal:
- Forward Traversal: Visit each node starting from the head and moving to the tail.
void traverseForward(Node* head) {
Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}- Backward Traversal: Visit each node starting from the tail and moving to the head.
void traverseBackward(Node* head) {
Node* temp = head;
if (temp == NULL) {
return;
}
while (temp->next != NULL) {
temp = temp->next;
}
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->prev;
}
printf("\n");
}Use Case Examples
Here is a comprehensive example that shows how to traverse a doubly linked list both forward and backward:
#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 insertAtEnd(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
void traverseForward(Node* head) {
Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
void traverseBackward(Node* head) {
if (head == NULL) {
return;
}
Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->prev;
}
printf("\n");
}
int main() {
Node* head = NULL;
insertAtEnd(&head, 1);
insertAtEnd(&head, 2);
insertAtEnd(&head, 3);
insertAtEnd(&head, 4);
printf("Forward traversal: ");
traverseForward(head);
printf("Backward traversal: ");
traverseBackward(head);
return 0;
}In this example, we:
- Created a doubly linked list with the values 1, 2, 3, 4.
- Traverse the list forward from the head to the end, printing each node’s data.
- Traverse the list backward from the end to the head, printing each node’s data.
Output
Forward traversal: 1 2 3 4
Backward traversal: 4 3 2 16. Search: In a doubly linked list, to find a node from the head, you may traverse down the list and compare the data of each node with the value you want. If you find a match, you can return a pointer to the node; if not, you can return NULL.
Node* searchNode(Node* head, int target) {
Node* current = head;
while (current != NULL) {
if (current->data == target) {
return current;
}
current = current->next;
}
return NULL; // Node not found
}Example Usage:
#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 insertAtEnd(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
Node* searchNode(Node* head, int target) {
Node* current = head;
while (current != NULL) {
if (current->data == target) {
return current;
}
current = current->next;
}
return NULL; // Node not found
}
void traverseForward(Node* head) {
Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int main() {
Node* head = NULL;
insertAtEnd(&head, 1);
insertAtEnd(&head, 2);
insertAtEnd(&head, 3);
insertAtEnd(&head, 4);
printf("Original list: ");
traverseForward(head);
int target = 3;
Node* foundNode = searchNode(head, target);
if (foundNode != NULL) {
printf("Node with data %d found.\n", target);
} else {
printf("Node with data %d not found.\n", target);
}
target = 5;
foundNode = searchNode(head, target);
if (foundNode != NULL) {
printf("Node with data %d found.\n", target);
} else {
printf("Node with data %d not found.\n", target);
}
return 0;
}In this example, we first build a doubly linked list with the values 1, 2, 3, 4. Then, we use the searchNode function to search for nodes with the values 3 and 5. The output shows whether each node was found in the list.
Output
Original list: 1 2 3 4
Node with data 3 found.
Node with data 5 not found.7. Update: As the name implies, in a doubly linked list, updating a node requires first locating the node you wish to change, then changing its data value.
void updateNode(Node* head, int oldData, int newData) {
Node* current = head;
while (current != NULL) {
if (current->data == oldData) {
current->data = newData;
return;
}
current = current->next;
}
printf("Node with data %d not found.\n", oldData);
}Use Case Example
#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 insertAtEnd(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
void traverseForward(Node* head) {
Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
void updateNode(Node* head, int oldData, int newData) {
Node* current = head;
while (current != NULL) {
if (current->data == oldData) {
current->data = newData;
return;
}
current = current->next;
}
printf("Node with data %d not found.\n", oldData);
}
int main() {
Node* head = NULL;
insertAtEnd(&head, 1);
insertAtEnd(&head, 2);
insertAtEnd(&head, 3);
insertAtEnd(&head, 4);
printf("Original list: ");
traverseForward(head);
int oldData = 3;
int newData = 10;
updateNode(head, oldData, newData);
printf("After updating node with data %d to %d: ", oldData, newData);
traverseForward(head);
oldData = 5;
newData = 20;
updateNode(head, oldData, newData); // This node doesn't exist
printf("After attempting to update node with data %d to %d: ", oldData, newData);
traverseForward(head);
return 0;
}Output
Original list: 1 2 3 4
After updating node with data 3 to 10: 1 2 10 4
Node with data 5 not found.
After attempting to update node with data 5 to 20: 1 2 10 4In this example, we first build a doubly linked list with the values 1, 2, 3, 4. Then, we use the updateNode function to update the node with the value 3 to 10. The output shows the list before and after the update. We also attempt to update a node with the value 5, which does not exist in the list, to demonstrate the handling of a node that is not found.
ADVANCED OPERATIONS
There are some advanced operations that could be done in doubly linked list. They are
8. Reversing a Doubly Linked List: Basically to reverse a doubly linked list you just need to swap the next and prev pointers of each node. Here’s a function to show how this work :-
void reverse(Node** head) {
Node* temp = NULL;
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;
}
}Example Usage
#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 insertAtEnd(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
void traverseForward(Node* head) {
Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
void reverse(Node** head) {
Node* temp = NULL;
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() {
Node* head = NULL;
insertAtEnd(&head, 1);
insertAtEnd(&head, 2);
insertAtEnd(&head, 3);
insertAtEnd(&head, 4);
printf("Original list: ");
traverseForward(head);
reverse(&head);
printf("Reversed list: ");
traverseForward(head);
return 0;
}Output
Original list: 1 2 3 4
Reversed list: 4 3 2 19. Sorting a Doubly Linked List: Sorting a doubly linked list can be done using various sorting algorithms. Here is an example using Bubble Sort:
void swap(Node* a, Node* b) {
int temp = a->data;
a->data = b->data;
b->data = temp;
}
void bubbleSort(Node* head) {
if (head == NULL) {
return;
}
int swapped;
Node* ptr1;
Node* lptr = NULL;
do {
swapped = 0;
ptr1 = head;
while (ptr1->next != lptr) {
if (ptr1->data > ptr1->next->data) {
swap(ptr1, ptr1->next);
swapped = 1;
}
ptr1 = ptr1->next;
}
lptr = ptr1;
} while (swapped);
}10. Merging Two Linked Lists Into One: Combining two different sorted lists into one sorted list is known as merging two doubly linked lists. Every node in the final list retains the characteristics of a doubly linked list, with each node pointing to the nodes before and after it.
Take a look at this function that merge two sorted doubly linked lists:
Node* merge(Node* first, Node* second) {
// If one of the lists is empty, return the other
if (first == NULL) {
return second;
}
if (second == NULL) {
return first;
}
// Initialize the head of the merged list
Node* mergedHead = NULL;
// Determine the head of the merged list
if (first->data <= second->data) {
mergedHead = first;
first = first->next;
} else {
mergedHead = second;
second = second->next;
}
// Pointer to the last node in the merged list
Node* mergedTail = mergedHead;
// Traverse both lists and merge them
while (first != NULL && second != NULL) {
if (first->data <= second->data) {
mergedTail->next = first;
first->prev = mergedTail;
first = first->next;
} else {
mergedTail->next = second;
second->prev = mergedTail;
second = second->next;
}
mergedTail = mergedTail->next;
}
// Attach the remaining nodes, if any
if (first != NULL) {
mergedTail->next = first;
first->prev = mergedTail;
} else {
mergedTail->next = second;
second->prev = mergedTail;
}
return mergedHead;
}Double linked lists are a versatile and efficient data organization method, enhancing efficiency and convenience in various tasks in computer science and other fields.
- Make sure to applaud this writer.👏👏
