Doubly Linked List
A Doubly linked list is a data structure that consists of a set of sequentially linked nodes, each containing two links: one to the next node and another to the previous node. This allows for traversal in both forward and backward directions, making it different from a singly
linked list, which only allows for traversal in one direction. In this tutorial, we'll explore the definition, basic operations, implementation details, and delve into best practices associated with doubly linked lists. Additionally, we'll analyze the advantages and limitations of using doubly linked lists in various scenarios.
Representation of a Doubly Linked List
A Doubly Linked List is represented by a series of nodes, where each node contains three fields.
- Data: Stores the value of the node.
- Previous: A pointer that stores the address of the previous node.
- Next: A pointer that stores the address of the next node.
- Node : The basic building block containing data, a reference to the next node, and a reference to the previous node.
- Head : The starting point of the list, representing the first node. The head node's previous pointer is always NULL.
- Tail : The last node in the list, where the reference to the next node is null.
- Null : The reference to the previous node in the head is null, and the reference to the next node in the tail is null.
Uses of Doubly Linked List
- Doubly linked lists are commonly used to implement undo mechanisms in applications. Each state change or action performed by a user corresponds to a node in the doubly linked list. The bidirectional nature of the list allows for easy navigation between different states. When an undo operation is requested, the application can traverse backward through the list to revert to the previous state.
- Web browsers use doubly linked lists to implement navigation systems. Each webpage visited is a node in the list, and the backward and forward buttons allow users to navigate through their browsing history bidirectionally.
- Image sliders or carousels in graphical user interfaces often use doubly linked lists. Each image is a node, and the bidirectional links enable smooth navigation between images. This structure is beneficial for implementing features like infinite loops in sliders.
- Doubly linked lists are employed in managing playlists for music applications. Each song in the playlist is a node, and the bidirectional links enable users to navigate through the playlist both forward and backward. This structure is essential for implementing features like shuffling and repeating playlists.
- To-do applications often use doubly linked lists to manage tasks. Each task represents a node, and the bidirectional links allow users to navigate through their task list and reorder tasks efficiently.
- Text editors benefit from the bidirectional traversal of doubly linked lists for efficient cursor movement. Each line or block of text is a node, and users can navigate both forward and backward within the document.
Advantages and Disadvantages of Doubly Linked List
Advantages of Doubly Linked List
- Doubly linked lists support efficient traversal in both forward and backward directions.
- Insertion and deletion operations are efficient, especially when performed at the beginning or end of the list.
- Reversing a doubly linked list is more straightforward than reversing a singly linked list, as each node contains a reference to both the next and previous nodes.
Disadvantages of Doubly Linked List
- Each node in a doubly linked list requires additional memory for both the next and previous references, resulting in more overhead compared to singly linked lists.
- Maintaining bidirectional links increases the complexity of implementation and can introduce more opportunities for bugs.
- Doubly linked lists use more memory compared to singly linked lists, making them less efficient in terms of memory usage.
Common Doubly Linked List Operations
Add a Node in a Doubly Linked List
To add a new node to the Doubly Linked List, we need to follow the following steps:
- Create a new node and set its data value.
- Set the next pointer of the new node to the current node's next pointer.
- Set the previous pointer of the new node to the current node.
- Set the next pointer of the current node to the new node.
- If the new node's next pointer is not null, then set the previous pointer of the new node's next node to the new node.
Traverse a Doubly Linked List
To traverse a Doubly Linked List, we can start from the head node and move forward until we reach the last node.
Delete a Node from Doubly Linked List
To delete a node from the Doubly Linked List, we need to follow the following steps:
- If the node to be deleted is the head node, then set the head node to the next node.
- If the node to be deleted is not the head node, then set the next pointer of the previous node of the node to be deleted to the next node of the node to be deleted.
- If the node to be deleted is not the last node, then set the previous pointer of the next node of the node to be deleted to the previous node of the node to be deleted.
- Free the memory of the node to be deleted.
Doubly Linked List Implementation Program
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *prev;
struct node *next;
};
// Function to add a node at the end of the list
void add_node_end(struct node **head, int data)
{
struct node *new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = data;
new_node->next = NULL;
if (*head == NULL)
{
new_node->prev = NULL;
*head = new_node;
return;
}
struct node *last_node = *head;
while (last_node->next != NULL)
{
last_node = last_node->next;
}
last_node->next = new_node;
new_node->prev = last_node;
}
// Function to traverse the list from head to tail
void traverse_forward(struct node *head)
{
printf("\nTraversal in forward direction:\n");
while (head != NULL)
{
printf("%d ", head->data);
head = head->next;
}
}
// Function to traverse the list from tail to head
void traverse_backward(struct node *tail)
{
printf("\nTraversal in backward direction:\n");
while (tail != NULL)
{
printf("%d ", tail->data);
tail = tail->prev;
}
}
// Function to delete a node with given key
void delete_node(struct node **head, int key)
{
if (*head == NULL)
{
printf("\nList is empty\n");
return;
}
struct node *temp = *head;
if (temp->data == key)
{
*head = temp->next;
(*head)->prev = NULL;
free(temp);
return;
}
while (temp != NULL && temp->data != key)
{
temp = temp->next;
}
if (temp == NULL)
{
printf("\nKey not found in list\n");
return;
}
if (temp->next == NULL)
{
temp->prev->next = NULL;
free(temp);
return;
}
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
free(temp);
}
int main()
{
struct node *head = NULL;
// Adding nodes to the list
add_node_end(&head, 10);
add_node_end(&head, 20);
add_node_end(&head, 30);
add_node_end(&head, 40);
add_node_end(&head, 50);
// Traversing the list in forward direction
traverse_forward(head);
// Traversing the list in backward direction
struct node *tail = head;
while (tail->next != NULL)
{
tail = tail->next;
}
traverse_backward(tail);
// Deleting a node with key 30
delete_node(&head, 30);
// Traversing the list after deletion
traverse_forward(head);
return 0;
}
Output
Traversal in forward direction: 10 20 30 40 50 Traversal in backward direction: 50 40 30 20 10 Traversal in forward direction: 10 20 40 50
Conclusion
Doubly linked lists offer enhanced functionality compared to singly linked lists by providing bidirectional traversal. Their efficient insertion and deletion operations make them suitable for various applications. By following best practices, such as maintaining a dummy node and handling edge cases, developers can ensure robust implementations. However, it's essential to consider the increased memory usage and complexity associated with doubly linked lists when choosing the appropriate data structure for a specific scenario. Understanding the advantages and limitations empowers developers to make informed decisions and leverage doubly linked lists effectively in their applications.