Chapter 5: Doubly Linked Lists
Welcome to Chapter 5! In this chapter, we’ll explore the Doubly Linked List—a more versatile type of linked list compared to the singly linked list. If you think of singly linked lists as one-way streets, doubly linked lists are like multi-lane roads with traffic flowing in both directions. This added flexibility can be particularly useful in various applications where bidirectional traversal is required.
What is a Doubly Linked List?
A Doubly Linked List is a type of linked list where each node has two pointers:
- Next Pointer: Points to the next node in the sequence.
- Previous Pointer: Points to the previous node in the sequence.
Here’s a graphical representation:
NULL <- [Prev | Data | Next] <-> [Prev | Data | Next] <-> [Prev | Data | Next] -> NULL
Each node contains a data field, a next pointer, and a prev pointer. The prev pointer of the first node is NULL, and the next pointer of the last node is NULL.
Why Use Doubly Linked Lists?
Doubly linked lists provide several advantages over singly linked lists:
- Bidirectional Traversal: You can traverse the list both forwards and backwards, which can be useful for certain algorithms and data processing tasks.
- Easier Deletion: Deleting a node is easier since you have a reference to the previous node, making it simpler to update pointers.
Doubly linked lists are used in applications such as navigation systems, where moving in both directions is necessary, similar to handling user interactions in educational platforms like Emancipation Edutech Private Limited.
Building a Doubly Linked List
To implement a doubly linked list, we start by defining the node structure:
#include <stdio.h>
#include <stdlib.h>
// Define a node structure
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
Each node now includes an additional pointer to the previous node.
Creating a Node
Here’s how you can create a new node:
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
This function initializes a new node with the given value and sets both the next and prev pointers to NULL.
Inserting Elements in a Doubly Linked List
Here’s how you can insert nodes into a doubly linked list:
At the Beginning:
void insertAtBeginning(struct Node** head, int value) {
struct Node* newNode = createNode(value);
newNode->next = *head;
newNode->prev = NULL;
if (*head != NULL) {
(*head)->prev = newNode;
}
*head = newNode;
}This function inserts a new node at the start of the list and updates the previous pointer of the current head node.
At the End:
void insertAtEnd(struct Node** head, int value) {
struct Node* newNode = createNode(value);
struct Node* temp = *head;
if (*head == NULL) {
*head = newNode;
return;
}
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}This function adds a new node to the end of the list and updates the previous pointer of the new node.
Inserting After a Given Node:
void insertAfter(struct Node* prevNode, int value) {
if (prevNode == NULL) {
printf("The given previous node cannot be NULL");
return;
}
struct Node* newNode = createNode(value);
newNode->next = prevNode->next;
newNode->prev = prevNode;
if (prevNode->next != NULL) {
prevNode->next->prev = newNode;
}
prevNode->next = newNode;
}This method inserts a new node after a specified node and adjusts pointers accordingly.
Traversing a Doubly Linked List
Traversal in a doubly linked list can be done in both directions:
Forward Traversal:
void traverseForward(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d <-> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}Backward Traversal:
void traverseBackward(struct Node* head) {
struct Node* temp = head;
if (temp == NULL) return;
// Move to the end of the list
while (temp->next != NULL) {
temp = temp->next;
}
// Traverse backwards
while (temp != NULL) {
printf("%d <-> ", temp->data);
temp = temp->prev;
}
printf("NULL\n");
}Forward traversal starts from the head and moves to the end, while backward traversal starts from the end and moves to the head.
Example: Creating and Traversing a Doubly Linked List
Here’s a sample program to create a doubly linked list and traverse it:
int main() {
struct Node* head = NULL;
// Inserting nodes
insertAtEnd(&head, 10);
insertAtEnd(&head, 20);
insertAtBeginning(&head, 5);
insertAtEnd(&head, 30);
insertAfter(head->next, 15); // Insert 15 after the node with data 10
// Traverse the list forward
printf("Forward Traversal:\n");
traverseForward(head);
// Traverse the list backward
printf("Backward Traversal:\n");
traverseBackward(head);
return 0;
}
Output:
Forward Traversal:
5 <-> 10 <-> 15 <-> 20 <-> 30 <-> NULL
Backward Traversal:
30 <-> 20 <-> 15 <-> 10 <-> 5 <-> NULL
Deleting Nodes in a Doubly Linked List
Deleting nodes in a doubly linked list is straightforward because you have pointers to both the next and previous nodes:
Deleting the First Node:
void deleteFirstNode(struct Node** head) {
if (*head == NULL) return;
struct Node* temp = *head;
*head = (*head)->next;
if (*head != NULL) {
(*head)->prev = NULL;
}
free(temp);
}Deleting the Last Node:
void deleteLastNode(struct Node** head) {
if (*head == NULL) return;
struct Node* temp = *head;
if (temp->next == NULL) {
free(temp);
*head = NULL;
return;
}
while (temp->next != NULL) {
temp = temp->next;
}
temp->prev->next = NULL;
free(temp);
}Deleting a Node by Value:
void deleteNodeByValue(struct Node** head, int value) {
struct Node* temp = *head;
while (temp != NULL && temp->data != value) {
temp = temp->next;
}
if (temp == NULL) return; // Node with the value not found
if (temp->prev != NULL) {
temp->prev->next = temp->next;
} else {
*head = temp->next; // Node to be deleted is the head
}
if (temp->next != NULL) {
temp->next->prev = temp->prev;
}
free(temp);
}
Advantages and Disadvantages of Doubly Linked Lists
Advantages:
- Bidirectional Traversal: Easier to traverse in both directions.
- Simpler Deletion: Deleting a node is more straightforward with a reference to the previous node.
Disadvantages:
- Extra Memory: Requires additional memory for the previous pointer.
- Increased Complexity: Slightly more complex to manage compared to singly linked lists.
Wrapping Up Chapter 5
In this chapter, we delved into Doubly Linked Lists—an enhanced version of singly linked lists that allows bidirectional traversal and simplifies node deletion. Mastering doubly linked lists will give you greater flexibility in handling dynamic data.
Key takeaways:
- Nodes in a doubly linked list have both
nextandprevpointers. - You can traverse the list in both directions.
- Deletion of nodes is simpler due to the additional pointer.
As always, if you want to see more examples or practice with interactive exercises, visit digilearn.cloud. And remember, **Emancipation