Doubly linked lists and its applications
A doubly linked list is a type of linked list where each node has two pointers: one pointing to the next node in the sequence, and another pointing to the previous node. This bidirectional linkage allows traversal of the list both forwards and backwards. Here's a detailed explanation:
Node Structure:
In a doubly linked list, each node consists of three fields:
- Data/Value: This field holds the actual data or value associated with the node.
- Next Pointer: This pointer points to the next node in the sequence.
- Previous Pointer: This pointer points to the previous node in the sequence.
A node in doubly linked list:
The prev part of the first node and the next part of the last node will always contain null indicating end in each direction.
Key Characteristics:
Bidirectional Traversal: One of the main advantages of a doubly linked list is that it allows traversal of the list in both forward and backward directions. This bidirectional traversal is facilitated by the presence of previous pointers in addition to next pointers.
Insertion and Deletion: Insertion and deletion operations in a doubly linked list are more efficient compared to a singly linked list. This is because, in addition to updating the next pointer of adjacent nodes, insertion and deletion also involve updating the previous pointers.
Flexibility: Doubly linked lists offer flexibility in terms of insertion and deletion at both ends (head and tail) of the list, as well as at any arbitrary position within the list. This flexibility makes them suitable for various applications where dynamic manipulation of data is required.
Memory Overhead: Doubly linked lists require additional memory to store the previous pointers for each node compared to singly linked lists. This extra memory overhead is a trade-off for the bidirectional traversal capability.
Operations on Doubly Linked List
In a double linked list, we perform the following operations...
-
Insertion
-
Deletion
-
Display
Insertion
In a double linked list, the insertion operation can be performed in three ways as follows...
-
Inserting At Beginning of the list
-
Inserting At End of the list
-
Inserting At Specific location in the list
Algorithm to Insert element at beginning
Algorithm: Insert at Beginning in Doubly Linked List
Input: Value (Value to be inserted)
Step 1: Create a new node newNode with the given value and newNode → previous as NULL.
Step 2: Check whether the list is Empty (head == NULL).
Step 3: If the list is Empty:
Assign NULL to newNode → next.
Assign newNode to head.
EXIT.
Step 4: If the list is not Empty:
Assign head to newNode → next.
Assign newNode to head.
EXIT.
Algorithm to Insert element at the end
Algorithm: Insert at End in Doubly Linked List
Input: Value (Value to be inserted)
Step 1: Create a new node newNode with the given value and newNode → next as NULL.
Step 2: Check whether the list is Empty (head == NULL).
Step 3: If the list is Empty:
Assign NULL to newNode → previous.
Assign newNode to head.
EXIT.
Step 4: If the list is not Empty:
Define a node pointer temp and initialize it with head.
Step 5: Keep moving the temp pointer to its next node until it reaches the last node in the list (until temp → next is equal to NULL).
Step 6: Assign newNode to temp → next.
Assign temp to newNode → previous.
EXIT.
Algorithm to Insert element at specific position
Algorithm: Insert at Specific Position in Doubly Linked List
Input: Value (Value to be inserted), Position (Position where the new node is to be inserted)
Step 1: Create a new node newNode with the given value.
Step 2: If Position is less than or equal to 0, display 'Invalid position' and terminate the function.
Step 3: If Position is 1 (i.e., inserting at the beginning):
Assign NULL to newNode → previous.
Set newNode → next to head.
If head is not NULL:
Assign newNode to head → previous.
Set newNode to head.
EXIT.
Step 4: Define a node pointer temp and initialize it with head.
Define a variable count and initialize it with 1.
Step 5: Traverse the list using temp until temp is NULL or count is equal to Position - 1.
If temp is NULL and count is less than Position - 1:
Display 'Invalid position' and terminate the function.
Otherwise, move temp to the next node and increment count.
Step 6: Assign temp → next to newNode.
If temp → next is not NULL:
Assign newNode to temp → next → previous.
Assign temp to newNode → previous.
Set newNode → next to temp → next.
Assign newNode to temp → next.
Step 7: EXIT.
Algorithm to delete from beginning
Algorithm: Delete from Beginning of Doubly Linked List
Step 1: If the list is empty (head == NULL), display "Empty list: Deletion not possible" and terminate the function.
Step 2: If the list has only one node (head → next == NULL):
Set temp to head.
Set head to NULL.
Delete temp.
EXIT.
Step 3: Set temp to head.
Step 4: Set head to head → next.
Step 5: Set head → previous to NULL.
Step 6: Delete temp.
Step 7: EXIT.
Algorithm to delete from end
Algorithm DeleteFromEnd()
if head == NULL
Display "Empty list: Deletion not possible"
Exit Algorithm
end if
if head → next == NULL
temp = head
head = NULL
Delete temp
Exit Algorithm
end if
temp = head
prev = NULL
// Traverse to the last node
while temp → next ≠ NULL
prev = temp
temp = temp → next
end while
// Disconnect the last node from the list
prev → next = NULL
Delete temp
End Algorithm
Algorithm to delete from specific position
Algorithm DeleteFromPosition(position)
// Check if the list is empty
if head == NULL
Display "Empty list: Deletion not possible"
Exit Algorithm
end if
// Check if position is valid
if position <= 0
Display "Invalid position"
Exit Algorithm
end if
// If deleting from the beginning
if position == 1
if head → next == NULL
temp = head
head = NULL
Delete temp
else
temp = head
head = head → next
head → previous = NULL
Delete temp
end if
Exit Algorithm
end if
// Traverse the list to the specified position
temp = head
count = 1
while count < position and temp ≠ NULL
prev = temp
temp = temp → next
count = count + 1
end while
// If position is beyond the end of the list
if temp == NULL
Display "Position exceeds list length: Deletion not possible"
Exit Algorithm
end if
// Deleting node at specified position
prev → next = temp → next
if temp → next ≠ NULL
temp → next → previous = prev
Delete temp
End Algorithm
Algorithm to display doubly linked list
Algorithm DisplayDoublyLinkedList()
// Check if the list is empty
if head == NULL
Display "Empty list"
Exit Algorithm
end if
// Traverse the list and display each node's value
temp = head
while temp ≠ NULL
Display temp → data
temp = temp → next
end while
End Algorithm
Applications/Uses of doubly linked list in real life
Doubly linked lists find applications in various real-life scenarios due to their unique features, such as bidirectional traversal and efficient insertion and deletion operations. Here are some common uses:
- Text Editors: Text editors often use doubly linked lists to implement features like undo and redo operations. Each change in the text can be stored as a node in the list, with pointers to both the previous and next versions of the text.
- Browser History: Web browsers use doubly linked lists to store the history of visited web pages. Each page visited is stored as a node in the list, allowing users to navigate backward and forward through their browsing history.
- Music Player: Doubly linked lists can be used to implement playlists in music players. Each song in the playlist can be stored as a node in the list, with pointers to the previous and next songs, allowing users to navigate through the playlist in both directions.
- Task Scheduler: Operating systems often use doubly linked lists to manage tasks and processes. Each task can be represented as a node in the list, with pointers to both the previous and next tasks, allowing for efficient scheduling and execution.
- Database Management Systems: Doubly linked lists are used in database management systems to implement indexes and linked lists of records. They allow for efficient traversal and manipulation of data, making them suitable for tasks such as sorting and searching.
- Symbol Tables: Compilers and interpreters use doubly linked lists to implement symbol tables, which store information about variables, functions, and other identifiers in a programming language. Each symbol can be represented as a node in the list, allowing for efficient lookup and modification.
- Cache Management: Doubly linked lists are used in cache management algorithms, such as LRU (Least Recently Used) and LFU (Least Frequently Used). They allow for efficient removal and replacement of cache entries based on access patterns.
Write a C++ program to implement doubly linked list.
#include<iostream>
using namespace std;
class Node{
public:
int data;
Node *prev;
Node *next;
Node(){
prev=NULL;
next=NULL;
}
Node * getNode(int data){
Node *new_node = new Node();
new_node->data=data;
return new_node;
}
};
class LinkedList{
Node *head;
public:
LinkedList(){
head=NULL;
}
void insert_at_head(Node *node){
Node *temp;
if(head==NULL){
head=node;
}
else{
temp = head;
node->next=temp;
temp->prev=node;
head=node;
}
}
void display(){
if(head==NULL){
cout<<"Empty List:"<<endl;
}
else{
Node *temp;
temp=head;
cout<<"Following are the elements of linked list: "<<endl;
while(temp!=NULL){
cout<<temp->data<<" ";
temp=temp->next;
}
cout<<endl;
}
}
void insert_at_end(Node *node){
if(head==NULL){
insert_at_head(node);
}
else
{
Node *temp;
temp = head;
while(temp->next!=NULL){
temp = temp->next;
}
temp->next = node;
node->prev=temp;
}
}
void insert_at_position(int pos,Node *node){
int cur_pos=1;
Node *temp;
if(head==NULL){
insert_at_head(node);
}
else{
temp = head;
while(cur_pos!=pos-1){
temp = temp->next;
cur_pos++;
}
node->prev = temp;
node->next=temp->next;
temp->next=node;
}
}
void delete_from_front(){
Node *temp;
if(head==NULL){
cout<<"ERROR!! Underflow condition"<<endl;
exit(0);
}else{
temp = head;
head = temp->next;
head->prev=NULL;
delete temp;
}
}
void delete_from_position(int pos){
int cur_pos=1;
Node *temp;
if(head==NULL){
cout<<"ERROR!! Underflow condition"<<endl;
exit(0);
}
else
{
temp = head;
while(cur_pos!=pos){
temp = temp->next;
cur_pos++;
}
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
delete temp;
}
}
};
int main(){
Node n;
LinkedList list;
list.display();
list.insert_at_end(n.getNode(100));
list.display();
list.insert_at_head(n.getNode(10));
list.insert_at_head(n.getNode(20));
list.insert_at_head(n.getNode(30));
list.insert_at_head(n.getNode(40));
list.insert_at_head(n.getNode(50));
list.display();
list.insert_at_end(n.getNode(200));
list.display();
list.insert_at_position(3,n.getNode(405));
list.display();
list.delete_from_front();
list.display();
list.delete_from_position(2);
list.display();
return 0;
}