Doubly Linked List in Data Structure: An Overview
If you are studying computer science, data structure, and algorithms then it is essential for you to learn about doubly linked lists. A doubly linked list is a type of data structure that stores a sequence of elements. It consists of elements arranged in a linear fashion such that each element contains references or pointers to the next element in the list as well as the previous one. The advantages associated with this particular data structure are tremendous ranging from efficient traversal capabilities to freeing up memory while manipulating complex datasets. This article will explore further into doubly linked lists why they're important and how they work so let's dive right in!
What is a doubly linked list in data structure?
A doubly linked list is a popular data structure used in computer science to store data in a specific order. Unlike a singly linked list, a doubly linked list allows each node to be connected to both its previous and next nodes, creating a chain that can be traversed in both directions. Doubly linked lists are excellent for text editors and other jobs that need efficient mid-list node operations as well as bidirectional traversal. They have become essential to computer science because of their adaptability and effectiveness.
A doubly linked list is a type of linked list in which each node consists of 3 components:
- *prev - address of the previous node
- data - data item
- *next - address of next node
Representation of Doubly Linked List
A doubly linked list is a data structure that consists of nodes, where each node contains a value and two pointers: one to the previous node and one to the next node. This allows for traversal in both directions.
Here is an algorithm for a doubly linked list:
- Define a Node class with three properties: value, prev (pointer to the previous node), and next (arrow to the next node).
- Create a DoublyLinkedList class with two properties: head (pointer to the first node) and tail (pointer to the last node).
- Implement the following methods in the DoublyLinkedList class:
- isEmpty(): Check if the list is empty by verifying if the head is null.
- prepend(value): Add a node with the given value at the beginning of the list.
- append(value): Add a node with the given value at the end of the list.
- insertAfter(value, targetValue): Insert a node with the given value after the first occurrence of the target value in the list.
- remove(value): Remove the first occurrence of a node with the given value from the list.
- removeFirst(): Remove the first node from the list.
- removeLast(): Remove the last node from the list.
- printList(): Traverse the list from the head to the tail and print the values of all the nodes.
- In each method, consider different cases such as adding or removing nodes at the beginning, end, or middle of the list, and update the pointers accordingly
Doubly Linked List in Data Structures Example
# Node of a doubly linked list
class Node:
def __init__(self, next=None, prev=None, data=None):
# reference to next node in DLL
self.next = next
# reference to previous node in DLL
self.prev = prev
self.data = data
// Class for Doubly Linked List
public class DLL {
// Head of list
Node head;
// Doubly Linked list Node
class Node {
int data;
Node prev;
Node next;
// Constructor to create a new node
// next and prev is by default initialized as null
Node(int d) { data = d; }
}
}
// Node of a doubly linked list
class Node {
public:
int data;
// Pointer to next node in DLL
Node* next;
// Pointer to previous node in DLL
Node* prev;
};In this doubly linked list program in data structure, we create a Node class for a doubly linked list (DLL) with features for data storage, references to the following and preceding nodes, and more.
Advantages of Doubly Linked List
- Efficient insertion and deletion: Unlike arrays, which require shifting of elements to insert or delete an element, doubly linked lists only require changing the pointers of the adjacent nodes. This makes the insertion and deletion operations much more efficient.
- Bidirectional traversal: The two pointers in each node allow for bidirectional traversal of the linked list, meaning the developer can traverse the list forward and backward. This is particularly useful in situations where the a need to search for elements or perform operations from both ends of the list.
- Flexibility: Because nodes in a doubly linked list have pointers to both the previous and next nodes, they can be easily removed from the list or inserted into the list without affecting the rest of the nodes. This makes doubly linked lists very flexible and adaptable to different situations.
- Memory efficiency: Unlike other data structures requiring a fixed amount of memory for each element, doubly linked lists can be allocated and resized dynamically, based on the amount of data being stored. This means that the user can use memory more efficiently and avoid wasting resources.
- Implementing other data structures: Doubly linked lists are often used as a building block for implementing other data structures, such as queues, stacks, and associative arrays. By using a doubly linked list as a base, anyone can implement these data structures more efficiently and with greater flexibility.
Disadvantages of Doubly Linked List
- Memory usage: Doubly linked lists require more memory than singly-linked lists, as they need to store a pointer to the previous node in addition to the next node.
- Insertion and deletion: Although doubly linked lists allow for more efficient insertion and deletion operations than arrays, they are less efficient than singly-linked lists. This is because each insertion or deletion requires updating both the previous and next pointers, which can be time-consuming.
- Traversal: Traversing a doubly linked list can also be slower than traversing an array or singly linked list, as it requires following both the previous and next pointers.
- Complexity: The use of doubly linked lists can add complexity to the code and increase the risk of bugs, as there are more pointers to manage and more edge cases to consider.
- Not suitable for some algorithms: Some algorithms may require random access to elements in a list, which is not efficient with doubly linked lists.
- Extra work for maintaining the list: In a doubly linked list, the user needs to handle the cases for both the next and previous node while inserting and deleting the node, it increases the complexity and there is a chance for error
Basic Operations on Doubly Linked List
Insertion Operation:
- Insertion at the beginning: To add a new node at the beginning of the list, you need to create a new node and update the references accordingly. If the list is empty, the new node will be both the head and tail of the list. Otherwise, you update the next reference of the new node to point to the current head, update the previous reference of the current head to point to the new node, and update the head reference to the new node.
- Insertion at the end: To add a new node at the end of the list, you create a new node and update the references accordingly. If the list is empty, the new node will be both the head and tail of the list. Otherwise, you update the next reference of the current tail to point to the new node, update the previous reference of the new node to point to the current tail, and update the tail reference to the new node.
- Insertion at a specific position: To insert a new node at a specific position in the list, you need to traverse the list until you reach the desired position. Once you reach the position, you create a new node and update the references accordingly. You update the next reference of the new node to point to the node currently at that position, update the previous reference of the new node to point to the node before the position, update the next reference of the node before the position to point to the new node and update the previous reference of the node at the position to point to the new node.
Algorithm for insertion operation
- Create a new node with the given data.
- If the doubly linked list is empty, set the head and tail pointers to point to the new node, and make the new node's prev and next pointers null.
- If the doubly linked list is not empty, do the following:
- Set the new node's next pointer to point to the current head of the list.
- Set the new node's prev pointer to null.
- Set the current head's prev pointer to point to the new node.
- Set the head pointer to point to the new node.
- The insertion operation is complete.
Example
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
def insertAtBeginning(head, data):
# Create a new node
newNode = Node(data)
newNode.next = head
# Update the previous pointer of the head node if it exists
if head is not None:
head.prev = newNode
# Update the head pointer
head = newNode
return head
def displayList(head):
current = head
while current is not None:
print(current.data, end=" ")
current = current.next
print()
# Main function
if __name__ == '__main__':
head = None # Initially, the list is empty
# Insert nodes at the beginning of the list
head = insertAtBeginning(head, 3)
head = insertAtBeginning(head, 2)
head = insertAtBeginning(head, 1)
# Display the list
print("Doubly Linked List:", end=" ")
displayList(head)
class Node {
int data;
Node prev;
Node next;
}
class DoublyLinkedList {
Node head;
// Function to insert a new node at the beginning of the list
void insertAtBeginning(int data) {
// Create a new node
Node newNode = new Node();
newNode.data = data;
newNode.prev = null;
newNode.next = head;
// Update the previous pointer of the head node if it exists
if (head != null)
head.prev = newNode;
// Update the head pointer
head = newNode;
}
// Function to display the contents of the doubly linked list
void displayList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
DoublyLinkedList list = new DoublyLinkedList();
// Insert nodes at the beginning of the list
list.insertAtBeginning(3);
list.insertAtBeginning(2);
list.insertAtBeginning(1);
// Display the list
System.out.print("Doubly Linked List: ");
list.displayList();
}
}
#include <iostream>
// Node structure for doubly linked list
struct Node {
int data;
Node* prev;
Node* next;
};
// Function to insert a new node at the beginning of the list
void insertAtBeginning(Node** head, int data) {
// Create a new node
Node* newNode = new Node();
newNode->data = data;
newNode->prev = nullptr;
newNode->next = *head;
// Update the previous pointer of the head node if it exists
if (*head != nullptr)
(*head)->prev = newNode;
// Update the head pointer
*head = newNode;
}
// Function to display the contents of the doubly linked list
void displayList(Node* head) {
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
int main() {
Node* head = nullptr; // Initially, the list is empty
// Insert nodes at the beginning of the list
insertAtBeginning(&head, 3);
insertAtBeginning(&head, 2);
insertAtBeginning(&head, 1);
// Display the list
std::cout << "Doubly Linked List: ";
displayList(head);
return 0;
}This example defines a doubly linked list and offers functions to show the list and insert nodes at the start of the list. It displays the doubly linked list: "1 2 3" after showing how nodes with the values 1, 2, and 3 are inserted at the beginning.
Output
Doubly Linked List: 1 2 3Deletion Operation
- Deletion from the beginning: To remove the first node from the list, you update the head reference to point to the next node, update the previous reference of the new head to null, and optionally free the memory occupied by the old head node.
- Deletion from the end: To remove the last node from the list, you update the tail reference to point to the previous node, update the next reference of the new tail to null, and optionally free the memory occupied by the old tail node.
- Deletion from a specific position: To remove a node from a specific position in the list, you need to traverse the list until you reach the desired position. Once you reach the position, you update the next reference of the node before the position to point to the node after the position, update the previous reference of the node after the position to point to the node before the position, and optionally free the memory occupied by the node at the position.
Algorithm for deletion operation
- If the list is empty, exit the algorithm since there is nothing to delete.
- If the node to be deleted is the first node (head) of the list:
- Set the head pointer to point to the next node (head = head.next).
- If the new head exists, set its previous pointer to null (head.prev = null).
- If the new head is null, set the tail pointer to null as well (tail = null).
- Exit the algorithm.
- If the node to be deleted is the last node (tail) of the list:
- Set the tail pointer to point to the previous node (tail = tail.prev).
- If the new tail exists, set its next pointer to null (tail.next = null).
- Exit the algorithm.
- If the node to be deleted is somewhere in the middle of the list:
- Set the previous node's next pointer to the next node (previousNode.next = currentNode.next).
- Set the next node's previous pointer to the previous node (nextNode.prev = currentNode.prev).
- Exit the algorithm
Example
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
def insertAtBeginning(head, data):
newNode = Node(data)
if head is None:
head = newNode
else:
newNode.next = head
head.prev = newNode
head = newNode
return head
def insertAtEnd(head, data):
newNode = Node(data)
if head is None:
head = newNode
else:
current = head
while current.next is not None:
current = current.next
current.next = newNode
newNode.prev = current
return head
def displayList(head):
if head is None:
print("The list is empty.")
else:
current = head
while current is not None:
print(current.data, end=" ")
current = current.next
print()
def deleteNode(head, data):
if head is None:
print("The list is empty.")
return head
current = head
prevNode = None
while current is not None:
if current.data == data:
if prevNode is None:
head = current.next
if head is not None:
head.prev = None
else:
prevNode.next = current.next
if current.next is not None:
current.next.prev = prevNode
del current
print("Node with data", data, "deleted successfully.")
return head
prevNode = current
current = current.next
print("Node with data", data, "not found in the list.")
return head
if __name__ == '__main__':
head = None
# Insert nodes at the beginning
head = insertAtBeginning(head, 5)
head = insertAtBeginning(head, 3)
head = insertAtBeginning(head, 1)
# Insert nodes at the end
head = insertAtEnd(head, 7)
head = insertAtEnd(head, 9)
print("Initial list: ")
displayList(head)
# Delete a node
head = deleteNode(head, 3)
print("List after deletion: ")
displayList(head)
class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
Node head;
// Function to insert a node at the beginning of the list
void insertAtBeginning(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
newNode.next = head;
head.prev = newNode;
head = newNode;
}
}
// Function to insert a node at the end of the list
void insertAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
newNode.prev = current;
}
}
// Function to display the doubly linked list
void displayList() {
if (head == null) {
System.out.println("The list is empty.");
} else {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
// Function to delete a node from the list
void deleteNode(int data) {
if (head == null) {
System.out.println("The list is empty.");
return;
}
Node current = head;
Node prevNode = null;
while (current != null) {
if (current.data == data) {
if (prevNode == null) {
head = current.next;
if (head != null) {
head.prev = null;
}
} else {
prevNode.next = current.next;
if (current.next != null) {
current.next.prev = prevNode;
}
}
System.out.println("Node with data " + data + " deleted successfully.");
return;
}
prevNode = current;
current = current.next;
}
System.out.println("Node with data " + data + " not found in the list.");
}
}
public class Main {
public static void main(String[] args) {
DoublyLinkedList list = new DoublyLinkedList();
// Insert nodes at the beginning
list.insertAtBeginning(5);
list.insertAtBeginning(3);
list.insertAtBeginning(1);
// Insert nodes at the end
list.insertAtEnd(7);
list.insertAtEnd(9);
System.out.print("Initial list: ");
list.displayList();
// Delete a node
list.deleteNode(3);
System.out.print("List after deletion: ");
list.displayList();
}
}
#include <iostream>
using namespace std;
struct Node {
int data;
Node* prev;
Node* next;
};
// Function to create a new node
Node* createNode(int data) {
Node* newNode = new Node();
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
// Function to insert a node at the beginning of the list
void insertAtBeginning(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
newNode->next = *head;
(*head)->prev = newNode;
*head = newNode;
}
}
// Function to insert a node at the end of the list
void insertAtEnd(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
Node* current = *head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
newNode->prev = current;
}
}
// Function to display the doubly linked list
void displayList(Node* head) {
if (head == NULL) {
cout << "The list is empty." << endl;
} else {
Node* current = head;
while (current != NULL) {
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
}
// Function to delete a node from the list
void deleteNode(Node** head, int data) {
if (*head == NULL) {
cout << "The list is empty." << endl;
return;
}
Node* current = *head;
Node* prevNode = NULL;
while (current != NULL) {
if (current->data == data) {
if (prevNode == NULL) {
*head = current->next;
if (*head != NULL) {
(*head)->prev = NULL;
}
} else {
prevNode->next = current->next;
if (current->next != NULL) {
current->next->prev = prevNode;
}
}
delete current;
cout << "Node with data " << data << " deleted successfully." << endl;
return;
}
prevNode = current;
current = current->next;
}
cout << "Node with data " << data << " not found in the list." << endl;
}
int main() {
Node* head = NULL;
// Insert nodes at the beginning
insertAtBeginning(&head, 5);
insertAtBeginning(&head, 3);
insertAtBeginning(&head, 1);
// Insert nodes at the end
insertAtEnd(&head, 7);
insertAtEnd(&head, 9);
cout << "Initial list: ";
displayList(head);
// Delete a node
deleteNode(&head, 3);
cout << "List after deletion: ";
displayList(head);
return 0;
}This example defines a doubly linked list and offers functions to show the list, insert nodes at the start or end, and delete a particular node based on its value. It shows how to add nodes, display the initial list, delete a node with the value 3, and then display the revised list.
Output
Initial list: 1 3 5 7 9
Node with data 3 deleted successfully.
List after deletion: 1 5 7 9
Traversal Operation:
You can traverse the doubly linked list in both directions. Starting from the head, you can visit each node by following the next references until you reach the end of the list (tail). Similarly, starting from the tail, you can visit each node by following the previous references until you reach the beginning of the list (head)
Algorithm for traversal operation
- Start at the head of the doubly linked list.
- If the head is null, the list is empty. Exit the algorithm.
- Initialize a pointer variable current and set it to the head of the list.
- While the current is not null, do the following steps:
- Process the data of the current node.
- Move the current pointer to the next node.
- Repeat step 4 until the current becomes null.
- Exit the algorithm
Example
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
# Function to insert a node at the beginning of the doubly linked list
def insertAtBeginning(head, data):
# Create a new node
newNode = Node(data)
newNode.prev = None
# If the list is empty, set the new node as the head
if head is None:
newNode.next = None
head = newNode
return head
# Make the new node the new head
newNode.next = head
head.prev = newNode
head = newNode
return head
# Function to traverse the doubly linked list and print the elements
def traverseList(head):
print("Doubly linked list elements: ", end='')
# Traverse the list
while head is not None:
print(head.data, end=' ')
head = head.next
print()
# Initialize an empty doubly linked list
head = None
# Insert elements into the list
head = insertAtBeginning(head, 5)
head = insertAtBeginning(head, 10)
head = insertAtBeginning(head, 15)
head = insertAtBeginning(head, 20)
# Traverse and print the doubly linked list
traverseList(head)
class Node {
int data;
Node prev;
Node next;
}
public class DoublyLinkedList {
// Function to insert a node at the beginning of the doubly linked list
static void insertAtBeginning(Node[] head, int data) {
// Create a new node
Node newNode = new Node();
newNode.data = data;
newNode.prev = null;
// If the list is empty, set the new node as the head
if (head[0] == null) {
newNode.next = null;
head[0] = newNode;
return;
}
// Make the new node the new head
newNode.next = head[0];
head[0].prev = newNode;
head[0] = newNode;
}
// Function to traverse the doubly linked list and print the elements
static void traverseList(Node head) {
System.out.print("Doubly linked list elements: ");
// Traverse the list
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println();
}
public static void main(String[] args) {
// Initialize an empty doubly linked list
Node[] head = new Node[1];
// Insert elements into the list
insertAtBeginning(head, 5);
insertAtBeginning(head, 10);
insertAtBeginning(head, 15);
insertAtBeginning(head, 20);
// Traverse and print the doubly linked list
traverseList(head[0]);
}
}
#include <iostream>
// Doubly linked list node
struct Node {
int data;
Node* prev;
Node* next;
};
// Function to insert a node at the beginning of the doubly linked list
void insertAtBeginning(Node** head, int data) {
// Create a new node
Node* newNode = new Node;
newNode->data = data;
newNode->prev = nullptr;
// If the list is empty, set the new node as the head
if (*head == nullptr) {
newNode->next = nullptr;
*head = newNode;
return;
}
// Make the new node the new head
newNode->next = *head;
(*head)->prev = newNode;
*head = newNode;
}
// Function to traverse the doubly linked list and print the elements
void traverseList(Node* head) {
std::cout << "Doubly linked list elements: ";
// Traverse the list
while (head != nullptr) {
std::cout << head->data << " ";
head = head->next;
}
std::cout << std::endl;
}
int main() {
// Initialize an empty doubly linked list
Node* head = nullptr;
// Insert elements into the list
insertAtBeginning(&head, 5);
insertAtBeginning(&head, 10);
insertAtBeginning(&head, 15);
insertAtBeginning(&head, 20);
// Traverse and print the doubly linked list
traverseList(head);
return 0;
}This example defines a function to insert nodes at the list's beginning as well as a doubly linked list. The doubly linked list is traversed and printed after being initialized as an empty list, with the members of the list being output as "20 15 10 5."
Output
Doubly linked list elements: 20 15 10 5Applications of Doubly Linked List
- Browser History: A browser history is a list of web pages that a user has visited. A doubly linked list is an ideal data structure for implementing a browser history because it allows users to navigate forward and backward through the pages they have visited.
- Music and Video Player: Doubly linked lists can be used to implement a music or video player's playlist. The links between the nodes allow users to navigate through the playlist in both the forward and backward directions.
- Text Editor: Text editors use doubly linked lists to implement the undo and redo features. Each node in the list represents the state of the document, and the links between the nodes allow users to navigate through the document's history.
- Cache: A cache is a temporary storage area used to speed up data access. Doubly linked lists can be used to implement a cache, with the most recently accessed data at the head of the list and the least recently accessed data at the tail.
- Operating System: Doubly linked lists are used in many operating systems for various purposes, such as managing processes, allocating memory, and handling input/output operations.
- File System: File systems use doubly linked lists to implement file directories. Each node in the list represents a file or a directory, and the links between the nodes allow users to navigate through the file system's directory structure
FAQs
1. What is a doubly linked list in data structure?
Each node in a doubly linked list holds a reference to both the node before it and the node after it, enabling bidirectional traversal.
2. Why do we use doubly linked lists in data structure?
Doubly linked lists are used because they can be efficiently traversed both forward and backward, making them appropriate for use in undo capabilities in text editors and other applications.
3. What is the difference between a doubly vs singly linked list?
The main distinction is that each node in a singly linked list only has a reference to the node after it, whereas each node in a doubly linked list includes references to both the nodes before and after it, allowing for bidirectional traversal.
4. Where is the doubly linked list used?
When bidirectional traversal is required, such as when implementing undo/redo functionality, browser history, or specific data structures like deques, doubly linked lists are utilized.
5. What are the advantages of a doubly linked list?
Bidirectional traversal, effective deletion and insertion at both ends and the capacity to create complex data structures and apps necessitating backward traversal are all advantages.
Summary
Ultimately, understanding the basic principles of a doubly linked list in the data structure is essential for any programmer or computer scientist. It not only allows us to store and manipulate complex information but also gives us control over how that is organized and accessed by a computer. Doubly linked lists are effective for applications and data structures that are efficient and save time and resources. You can build complex buildings if you can master them. To succeed more, investigate, explore, and use doubly linked lists!
Take our free skill tests to evaluate your skill!
In less than 5 minutes, with our skill test, you can identify your knowledge gaps and strengths.
Previous Tutorial
