Published: December 19, 2024
Reading Time: 10 minutes
Source: NxtWave CCBP Blog
A doubly linked list program in C is a data structure where each node links to both the previous node and the next node. Each node contains three parts: a data part and two addresses. This linking enables traversal in both directions, which is what makes it different from the singly linked list.
Doubly linked lists are widely used in memory management, undo operations, and navigation systems and are an important tool in programming. This comprehensive guide covers the concept, implementation, operations, and practical applications to give students a thorough understanding of this crucial data structure.
A Doubly Linked List in C is a versatile data structure that connects nodes in a sequential chain using pointers. Each node in this list consists of three essential components:
This section demonstrates how a doubly linked list program in a data structure in C can be represented with code examples.
The following key components must be defined:
In the code, a single node is represented as:
struct node {
int data;
struct node *next;
struct node *prev;
}
Each struct node contains a data element and two pointers: one to the preceding node and one pointer to the next node.
Here's a simple doubly linked list program in C with three nodes to understand how it works:
#include <stdio.h>
#include <stdlib.h>
// Structure for a node in a doubly linked list
struct Node {
int data; // Data stored in the node
struct Node *next; // Pointer to the next node
struct Node *prev; // Pointer to the previous node
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
exit(1); // Exit the program if memory allocation fails
}
newNode->data = data; // Set the data
newNode->next = NULL; // Initialize next pointer to NULL
newNode->prev = NULL; // Initialize prev pointer to NULL
return newNode;
}
// Function to print the doubly linked list in forward order
void printList(struct Node* head) {
struct Node* temp = head;
printf("Forward Traversal: ");
while (temp != NULL) {
printf("%d ", temp->data); // Print the data in each node
if (temp->next == NULL) {
break; // Stop when we reach the last node
}
temp = temp->next; // Move to the next node
}
printf("\n");
// Call the reverse traversal function starting from the last node
printf("Reverse Traversal: ");
while (temp != NULL) {
printf("%d ", temp->data); // Print the data in each node
temp = temp->prev; // Move to the previous node
}
printf("\n");
}
// Function to free memory allocated for the list
void freeList(struct Node* head) {
struct Node* temp;
while (head != NULL) {
temp = head; // Store the current node
head = head->next; // Move to the next node
free(temp); // Free the current node
}
}
int main() {
// Create nodes
struct Node* node1 = createNode(10); // First node
struct Node* node2 = createNode(20); // Second node
struct Node* node3 = createNode(30); // Third node
// Link nodes
node1->next = node2;
node2->prev = node1;
node2->next = node3;
node3->prev = node2;
// Print the list with forward and reverse traversal
printList(node1);
// Free allocated memory
freeList(node1);
return 0;
}
Output:
Forward Traversal : 10 20 30
Reverse Traversal : 30 20 10
prev stores null for node one as there is no node before it. Its value is 10 and the next stores the address of node two.prev stores one as the pointer. Its value is 20, and the next store is the address of node three.prev stores two as the pointer. Its value is 30, and the next store is null.printList function prints the list in both forward and reverse directions.next pointers. Then it traverses backward from the last node to the head using the prev pointers.Adding a node to a doubly linked list is similar to inserting a node in a singly linked list, but it requires additional steps to manage the prev pointer for backward traversal.
In a doubly linked list, nodes can be inserted at three positions:
For example, consider a doubly linked list with elements 1, 2, and 3. These operations allow flexible modification of the list structure.
As discussed above, the insertion of nodes can be done in the beginning, in between or at the end. This section demonstrates insertion at the beginning.
In this example, we'll add a node of value 6 to the beginning of the doubly linked list.
Steps:
First, we create the new node by allocating memory for the newnode and assigning data to the newnode.
Second, the prev and next pointers are set for the new node. The next of the newnode is pointed to the first node in the list. Then the prev of the new node is pointed to the null.
Next, we make the new node as head node. For this the prev of the first node (formerly head node) is pointed to the newnode. Then point head to the newnode.
Code Implementation:
#include <stdio.h>
#include <stdlib.h>
// Define the structure of a node
struct Node {
int data; // Data part of the node
struct Node* next; // Pointer to the next node
struct Node* prev; // Pointer to the previous node
};
// Function to insert a node at the front of the doubly linked list
void insertFront(struct Node** head, int data) {
// Allocate memory for the new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) { // Check if memory allocation succeeded
printf("Memory allocation failed\n");
return;
}
// Assign data to the new node
newNode->data = data;
// Set the next pointer of the new node to the current head
newNode->next = *head;
// Set the prev pointer of the new node to NULL
newNode->prev = NULL;
// If the list is not empty, update the previous pointer of the current head
if (*head != NULL) {
(*head)->prev = newNode;
}
// Update the head to point to the new node
*head = newNode;
}
// Function to print the doubly linked list
void printList(struct Node* head) {
struct Node* temp = head;
printf("Doubly Linked List: ");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
// Driver code to test the insertFront function
int main() {
struct Node* head = NULL; // Initialize an empty doubly linked list
// Create a list with nodes 1, 2, and 3
insertFront(&head, 3); // List: 3
insertFront(&head, 2); // List: 2 -> 3
insertFront(&head, 1); // List: 1 -> 2 -> 3
// Insert new node with value 6 at the front
insertFront(&head, 6); // List: 6 -> 1 -> 2 -> 3
// Print the doubly linked list
printList(head);
return 0;
}
Output:
Doubly Linked List : 6 1 2 3
Deletion can also be done similar to insertion from three different positions. This section demonstrates deletion at the beginning on the same original doubly linked list as above.
To delete the first node (head node) in a doubly linked list, the head pointer is updated to point to the next node (head = head->next), making the second node the new head. If the new head is not NULL, its previous pointer is set to NULL to ensure there is no reference to the deleted node.
Finally, the memory of the old head node is freed to remove it from the list.
Code Implementation:
#include <stdio.h>
#include <stdlib.h>
// Define the structure of a node
struct Node {
int data; // Data part of the node
struct Node* next; // Pointer to the next node
struct Node* prev; // Pointer to the previous node
};
// Function to insert a node at the front of the doubly linked list
void insertFront(struct Node** head, int data) {
// Allocate memory for the new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) { // Check if memory allocation succeeded
printf("Memory allocation failed\n");
return;
}
// Assign data to the new node
newNode->data = data;
// Set the next pointer of the new node to the current head
newNode->next = *head;
// Set the prev pointer of the new node to NULL
newNode->prev = NULL;
// If the list is not empty, update the previous pointer of the current head
if (*head != NULL) {
(*head)->prev = newNode;
}
// Update the head to point to the new node
*head = newNode;
}
// Function to delete the first node in the doubly linked list
void deleteFirstNode(struct Node** head) {
// Check if the list is empty
if (*head == NULL) {
printf("The list is empty, nothing to delete.\n");
return;
}
// Store the old head node temporarily
struct Node* temp = *head;
// Update head to the next node
*head = (*head)->next;
// If the new head is not NULL, set its prev to NULL
if (*head != NULL) {
(*head)->prev = NULL;
}
// Free the memory of the old head
free(temp);
}
// Function to print the doubly linked list
void printList(struct Node* head) {
struct Node* temp = head;
printf("Doubly Linked List: ");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
// Driver code to test the insertFront and deleteFirstNode functions
int main() {
struct Node* head = NULL; // Initialize an empty doubly linked list
// Create a list with nodes 1, 2, and 3
insertFront(&head, 3); // List: 3
insertFront(&head, 2); // List: 2 -> 3
insertFront(&head, 1); // List: 1 -> 2 -> 3
// Print the list before deleting the first node
printf("Before deleting the first node:\n");
printList(head);
// Delete the first node
deleteFirstNode(&head); // List after deletion: 2 -> 3
// Print the list after deleting the first node
printf("After deleting the first node:\n");
printList(head);
return 0;
}
Output:
before deleting the first node:
Doubly Linked List : 1 2 3
After deleting the first node:
Doubly linked List : 2 3
Traversal across the doubly linked list can be performed in the forward and backward manner.
The forward traversal starts by initializing a pointer to the head of the list. As long as the pointer is not null, the data at the current node is visited. Then the pointer is moved to the next node.
For backward traversal, the process begins by initializing a pointer to the tail of the list. Similarly, as long as the pointer is not null, the data at the current node is visited. Then the pointer is moved to the previous node.
Code Implementation:
#include <stdio.h>
#include <stdlib.h>
// Define the Node structure
struct Node {
int data; // Data stored in the node
struct Node* next; // Pointer to the next node
struct Node* prev; // Pointer to the previous node
};
// Function to create a new node
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;
}
// Function to traverse the doubly linked list
// in forward direction
void forwardTraversal(struct Node* head) {
// Start traversal from the head of the list
struct Node* curr = head;
// Continue until the current node is not
// null (end of list)
while (curr != NULL) {
// Output data of the current node
printf("%d ", curr->data);
// Move to the next node
curr = curr->next;
}
// Print newline after traversal
printf("\n");
}
// Function to traverse the doubly linked list
// in backward direction
void backwardTraversal(struct Node* tail) {
// Start traversal from the tail of the list
struct Node* curr = tail;
// Continue until the current node is not
// null (end of list)
while (curr != NULL) {
// Output data of the current node
printf("%d ", curr->data);
// Move to the previous node
curr = curr->prev;
}
// Print newline after traversal
printf("\n");
}
int main() {
// Sample usage of the doubly linked list and
// traversal functions
struct Node* head = createNode(1);
struct Node* second = createNode(2);
struct Node* third = createNode(3);
head->next = second;
second->prev = head;
second->next = third;
third->prev = second;
printf("Forward Traversal:\n");
forwardTraversal(head);
printf("Backward Traversal:\n");
backwardTraversal(third);
// Free memory allocated for nodes
free(head);
free(second);
free(third);
return 0;
}
Output:
Forward Traversal:
1 2 3
Backward traversal:
3 2 1
The key applications of doubly linked list in C include the following:
Learning about doubly linked lists in C is crucial for anyone advancing in software development. It strengthens the understanding of fundamental data structures and memory management. Mastering this concept lays the groundwork for tackling more complex algorithms and systems.
To learn more and build your foundation for a career in software, enroll in the CCBP 4.0 Academy course.
A doubly linked list is a data structure where each node contains data, a pointer to the next node, and a pointer to the previous node. It allowing traversal in both directions.
In C, a doubly linked list is represented using a struct, where each node has three components: data, a pointer to the next node, and a pointer to the previous node. The list is manipulated using pointers to these nodes.
Basic operations on a doubly linked list include insertion (at the beginning, end, or in-between), deletion (of nodes), traversal (in both directions), and searching for elements.
Doubly linked lists allow traversal in both forward and backward directions which makes them more flexible than singly linked lists. They also enable deletion and insertion at both ends of the list.
Doubly linked lists are used in applications like browser history management, music and video player playlists, undo/redo functionality in software, and memory management systems.
About NxtWave
NxtWave offers comprehensive programming courses including CCBP 4.0 Academy for students looking to build careers in software development. The platform provides industry-recognized certifications and practical learning experiences.
Contact Information:
Course Offerings: