Introduction
A Doubly Linked List (DLL) is a data structure in which each node of the list contains a pointer to its previous and next nodes. This allows bidirectional traversal of the list. In this tutorial, we will discuss the representation, advantages, and disadvantages of using a DLL over a singly linked list, operations on DLL, and applications of DLL.
Representation of DLL
A doubly linked list is represented using a structure that contains three fields:
- Data: This field contains the actual data stored in the node.
- Prev: This field contains a pointer to the previous node in the list.
- Next: This field contains a pointer to the next node in the list.
Here is an example of the structure of a doubly linked list node in Java:
public class Node {
// The data that the node holds.
String data;
// A reference to the previous node in the linked list.
Node prev;
// A reference to the next node in the linked list.
Node next;
public Node(String data) {
this.data = data;
}
}
The following code demonstrates the implementation of the Node class and its usage:
public class DoublyLinkedListExample {
public static void main(String[] args) {
// Creating nodes for each country
Node canada = new Node("Canada");
Node usa = new Node("USA");
Node mexico = new Node("Mexico");
Node brazil = new Node("Brazil");
// Creating the doubly linked list
canada.next = usa;
usa.prev = canada;
usa.next = mexico;
mexico.prev = usa;
mexico.next = brazil;
brazil.prev = mexico;
// Outputting the contents of the doubly linked list
Node currentNode = canada;
while (currentNode != null) {
System.out.println(currentNode.data);
currentNode = currentNode.next;
}
}
static class Node {
// The data that the node holds.
String data;
// A reference to the previous node in the linked list.
Node prev;
// A reference to the next node in the linked list.
Node next;
public Node(String data) {
this.data = data;
}
}
}
Output:
Canada USA Mexico Brazil
The output displays the list of countries in the doubly linked list, which was created by connecting the nodes for each country through their prev and next attributes. The code then iterates through the linked list starting from the head node (canada) and prints out the data attribute of each node until the end of the list is reached (brazil).
Advantages of using a doubly linked list over a singly linked list
1. Bidirectional traversal
A doubly linked list allows both forward and backward traversal of the list, which can be useful in certain situations.
In a singly linked list, you can only traverse the list in one direction (typically from the head or front of the list to the tail or end of the list). This means that if you want to traverse the list in reverse order, you would need to start from the head and iterate through the list until you reach the end, keeping track of each node as you go, and then iterate through that list in reverse order.
In contrast, a doubly linked list allows you to traverse the list in both forward and backward directions. This is because each node in the list has a reference to both the previous and next nodes in the list. With this bidirectional traversal capability, you can iterate through the list in either direction, making it easier to access and manipulate nodes in both directions.
2. Efficient deletion
Deleting a node in a doubly linked list is more efficient than deleting a node in a singly linked list since we don’t need to traverse the list to find the previous node.
In a singly linked list, deleting a node typically requires iterating through the list to find the node that comes before the node you want to delete so that you can update its “next” pointer to skip over the node you are deleting. This process can be time-consuming, especially for large lists.
In contrast, in a doubly linked list, each node has a reference to both the previous and next nodes in the list. This means that when you want to delete a node, you can simply update the “next” reference of the previous node to point to the node that comes after the one you want to delete and update the “prev” reference of the next node to point to the node that comes before the one you want to delete. In other words, you don’t need to traverse the list to find the previous node since you already have a reference to it.
3. Efficient insertion
Inserting a node in a doubly linked list is also more efficient since we can easily update the prev and next pointers of the adjacent nodes.
In a doubly linked list, inserting a new node involves updating the “prev” and “next” pointers of the adjacent nodes to point to the new node, which is a relatively simple operation. Specifically, to insert a new node between two existing nodes (A and B) in a doubly linked list, you would update the “next” pointer of node A to point to the new node and the “prev” pointer of node B to point to the new node, and update the “prev” and “next” pointers of the new node to point to nodes A and B, respectively.
In contrast, in a singly linked list, inserting a new node between two existing nodes typically requires iterating through the list to find the node that comes before the location where you want to insert the new node so that you can update its “next” pointer to point to the new node. This process can be time-consuming, especially for large lists.
Disadvantages of using a doubly linked list over a singly linked list
1. Memory usage
A doubly linked list requires more memory than a singly linked list since each node contains an extra pointer.
In a doubly linked list, each node contains two pointers, one to the previous node and one to the next node, in addition to the data it stores. This means that a doubly linked list requires more memory per node than a singly linked list, which only has one pointer to the next node.
The extra memory usage required by a doubly linked list can be a disadvantage in situations where memory usage is a concern, such as on systems with limited memory or when working with large datasets. In these situations, a singly linked list may be a better choice since it requires less memory per node and can therefore store more nodes with the same amount of memory.
2. More complex
The implementation of a doubly linked list is more complex than a singly linked list since we need to maintain two pointers for each node.
The implementation of a doubly linked list is more complex than a singly linked list because each node in a doubly linked list has to maintain two pointers, one to the previous node and one to the next node. This means that there are more relationships to manage between nodes, and it requires more complex logic to perform operations on the list, such as insertion, deletion, or traversal.
In contrast, a singly linked list only requires one pointer per node, which makes the implementation simpler and easier to understand. The logic for operations on a singly linked list is also more straightforward since each node only has a single reference to the next node, and there is only one direction in which the list can be traversed.
Operations on doubly linked list
1. Insertion
To insert a new node at the beginning of the list, we create a new node and update its prev and next pointers to point to the first node and null, respectively. We also update the prev pointer of the first node to point to the new node.
// Inserts a new node at the beginning of the linked list with the given data and head node
public static void insertFirst(Node newNode, Node head) {
// set the next pointer of the new node to the current head of the list
newNode.next = head;
// set the previous pointer of the new node to null (since it will be the first node)
newNode.prev = null;
// if the list is not empty
if (head != null) {
// set the previous pointer of the current head to the new node
head.prev = newNode;
}
// update the head of the list to be the new node
head = newNode;
}
Now let’s see how we can implement the insertFirst method and utilize it:
public class DoublyLinkedListExample {
public static void main(String[] args) {
// Creating nodes for each country
Node canada = new Node("Canada");
Node usa = new Node("USA");
Node mexico = new Node("Mexico");
Node brazil = new Node("Brazil");
// Creating the doubly linked list
canada.next = usa;
usa.prev = canada;
usa.next = mexico;
mexico.prev = usa;
mexico.next = brazil;
brazil.prev = mexico;
// Inserting a new node at the beginning of the list
Node france = new Node("France");
insertFirst(france, canada);
// Outputting the contents of the doubly linked list
Node currentNode = france;
while (currentNode != null) {
System.out.println(currentNode.data);
currentNode = currentNode.next;
}
}
public static void insertFirst(Node newNode, Node head) {
// set the next pointer of the new node to the current head of the list
newNode.next = head;
// set the previous pointer of the new node to null (since it will be the first node)
newNode.prev = null;
// if the list is not empty
if (head != null) {
// set the previous pointer of the current head to the new node
head.prev = newNode;
}
// update the head of the list to be the new node
head = newNode;
}
static class Node {
// The data that the node holds.
String data;
// A reference to the previous node in the linked list.
Node prev;
// A reference to the next node in the linked list.
Node next;
public Node(String data) {
this.data = data;
}
}
}
Output:
France Canada USA Mexico Brazil
The program demonstrates the use of the insertFirst() method to insert a new node with the country name at the beginning of the list. This method sets the prev attribute of the new node to null since it will be the first node, and updates the prev attribute of the previous head node to the new node. Finally, it updates the head reference to point to the new node.
2. Deletion
To delete a node from the list, we update the prev pointer of the next node to point to the previous node and the next pointer of the previous node to point to the next node. We also free the memory allocated to the deleted node.
// Deletes the given node from the linked list with the given head node
public void deleteNode(Node node, Node head) {
// if the given node is null, do nothing and return
if (node == null) {
return;
}
// if the previous node is not null, update its next pointer to skip over the given node
if (node.prev != null) {
node.prev.next = node.next;
} else {
// if the previous node is null, the given node is the head of the list, so update the head to the next node
head = node.next;
}
// if the next node is not null, update its previous pointer to skip over the given node
if (node.next != null) {
node.next.prev = node.prev;
}
// set the given node to null to delete it from memory (this step may not be necessary in all cases)
node = null;
}
Implementing the deleteNode method and using it is shown below:
public class DoublyLinkedListExample {
// Deletes the given node from the linked list with the given head node
public static void deleteNode(Node node, Node head) {
// if the given node is null, do nothing and return
if (node == null) {
return;
}
// if the previous node is not null, update its next pointer to skip over the given node
if (node.prev != null) {
node.prev.next = node.next;
} else {
// if the previous node is null, the given node is the head of the list, so update the head to the next node
head = node.next;
}
// if the next node is not null, update its previous pointer to skip over the given node
if (node.next != null) {
node.next.prev = node.prev;
}
// set the given node to null to delete it from memory (this step may not be necessary in all cases)
node = null;
}
public static void main(String[] args) {
// Creating nodes for each country
Node canada = new Node("Canada");
Node usa = new Node("USA");
Node mexico = new Node("Mexico");
Node brazil = new Node("Brazil");
Node france = new Node("France");
Node japan = new Node("Japan");
// Creating the doubly linked list
canada.next = usa;
usa.prev = canada;
usa.next = mexico;
mexico.prev = usa;
mexico.next = brazil;
brazil.prev = mexico;
brazil.next = france;
france.prev = brazil;
france.next = japan;
japan.prev = france;
// Outputting the contents of the doubly linked list before deleting a node
System.out.println("BEFORE DELETION :");
Node currentNode = canada;
while (currentNode != null) {
System.out.println(currentNode.data);
currentNode = currentNode.next;
}
System.out.println("------------------------");
// Deleting a node from the linked list
deleteNode(brazil, canada);
// Outputting the contents of the doubly linked list after deleting a node
System.out.println("AFTER DELETION :");
currentNode = canada;
while (currentNode != null) {
System.out.println(currentNode.data);
currentNode = currentNode.next;
}
}
static class Node {
// The data that the node holds.
String data;
// A reference to the previous node in the linked list.
Node prev;
// A reference to the next node in the linked list.
Node next;
public Node(String data) {
this.data = data;
}
}
}
Output:
BEFORE DELETION : Canada USA Mexico Brazil France Japan ------------------------ AFTER DELETION : Canada USA Mexico France Japan
This code creates a doubly linked list of countries and then demonstrates the use of the deleteNode method to delete a node from the list. The deleteNode method takes a Node to delete and the head node of the list. It first checks if the given node is null and if so, does nothing and returns. Otherwise, it updates the previous node’s next pointer to skip over the given node, or if the given node is the head of the list, updates the head to be the next node. It then updates the next node’s prev pointer to skip over the given node. Finally, it sets the given node to null to delete it from memory. The output shows the contents of the doubly linked list before and after deleting a node.
3. Traversal
We can traverse a doubly linked list in both forward and backward directions. To traverse the list forward, we start at the first node and follow the next pointers until we reach the end of the list. To traverse the list backward, we start at the last node and follow the prev pointers until we reach the beginning of the list.
// Traverses the linked list forward and prints the data of each node
public void traverseForward(Node head) {
// start at the head node
Node current = head;
// loop through each node and print its data
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
// print a newline character to separate the output from the rest of the program
System.out.println();
}
// Traverses the linked list backward and prints the data of each node
public void traverseBackward(Node tail) {
// start at the tail node
Node current = tail;
// loop through each node and print its data
while (current != null) {
System.out.print(current.data + " ");
current = current.prev;
}
// print a newline character to separate the output from the rest of the program
System.out.println();
}
Now, we’ll implement the method and see how it practically works in our code:
public class DoublyLinkedListExample {
static class Node {
String data;
Node prev;
Node next;
public Node(String data) {
this.data = data;
}
}
public static void main(String[] args) {
// Creating nodes for each country
Node canada = new Node("Canada");
Node usa = new Node("USA");
Node mexico = new Node("Mexico");
Node brazil = new Node("Brazil");
// Creating the doubly linked list
canada.next = usa;
usa.prev = canada;
usa.next = mexico;
mexico.prev = usa;
mexico.next = brazil;
brazil.prev = mexico;
// Traversing the doubly linked list forward
System.out.println("Traversing the linked list forward:");
traverseForward(canada);
// Traversing the doubly linked list backward
System.out.println("Traversing the linked list backward:");
traverseBackward(brazil);
}
// Traverses the linked list forward and prints the data of each node
public static void traverseForward(Node head) {
// start at the head node
Node current = head;
// loop through each node and print its data
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
// print a newline character to separate the output from the rest of the program
System.out.println();
}
// Traverses the linked list backward and prints the data of each node
public static void traverseBackward(Node tail) {
// start at the tail node
Node current = tail;
// loop through each node and print its data
while (current != null) {
System.out.print(current.data + " ");
current = current.prev;
}
// print a newline character to separate the output from the rest of the program
System.out.println();
}
}
Output:
Traversing the linked list forward: Canada USA Mexico Brazil Traversing the linked list backward: Brazil Mexico USA Canada
This code first creates a doubly linked list of world countries, and then uses the traverseForward and traverseBackward methods to print the data of each node in forward and backward order, respectively.
4. Searching
To search for a specific element in the list, we can start at the first node and follow the next pointers until we find the desired element or reach the end of the list. We can also start at the last node and follow the prev pointers to search in the reverse direction.
//Searches the linked list for a node with the specified data
public Node search(Node head, String data) {
// start at the head node
Node current = head;
// loop through each node and check if its data matches the target data
while (current != null) {
if (current.data.equals(data)) {
// if the data matches, return the current node
return current;
}
current = current.next;
}
// if the target data is not found, return null
return null;
}
Let’s proceed with implementing the method and observing its practical functionality in action:
public class DoublyLinkedListExample {
public static Node search(Node head, String data) {
Node current = head;
while (current != null) {
if (current.data.equals(data)) {
return current;
}
current = current.next;
}
return null;
}
public static class Node {
// The data that the node holds.
String data;
// A reference to the previous node in the linked list.
Node prev;
// A reference to the next node in the linked list.
Node next;
public Node(String data) {
this.data = data;
}
}
public static void main(String[] args) {
// create the nodes for the linked list
Node canada = new Node("Canada");
Node usa = new Node("United States");
Node mexico = new Node("Mexico");
Node brazil = new Node("Brazil");
Node france = new Node("France");
// link the nodes together to form a doubly linked list
canada.next = usa;
usa.prev = canada;
usa.next = mexico;
mexico.prev = usa;
mexico.next = brazil;
brazil.prev = mexico;
brazil.next = france;
france.prev = brazil;
// search for a node in the linked list
Node result = search(canada, "Brazil");
if (result != null) {
System.out.println("Node found: " + result.data);
} else {
System.out.println("Node not found.");
}
}
}
Output:
Node found: Brazil
The search method in this code is used to find a node with a given data value in a doubly linked list. The method takes in the head of the linked list and the target data as parameters, and returns the node containing the data if it is found. If the data is not found in the linked list, the method returns null. The method works by iterating over the nodes in the linked list, checking if the data of each node matches the target data value, and returning the node if a match is found.
Applications of DLL
1. Browser history
The back and forward buttons in a web browser use a doubly linked list to keep track of the user’s browsing history.
As a user navigates from one web page to another, the browser maintains a history of the visited web pages. Each web page visited is stored as a node in a doubly linked list. Each node has a reference to the previous page visited and the next page to be visited.
When the user clicks the back button, the browser goes back to the previous node in the linked list and loads that page. Similarly, when the user clicks the forward button, the browser goes forward to the next node in the linked list and loads that page.
Since a doubly linked list allows both forward and backward traversal, it is a natural choice for implementing the back and forwards buttons in a web browser. By using a doubly linked list, the browser can easily navigate back and forth in the user’s browsing history without needing to reload web pages unnecessarily.
Overall, the use of a doubly linked list to manage browsing history provides a convenient and efficient way for users to revisit previously visited web pages in the order they were visited.
2. Undo/Redo functionality
The undo and redo functionality is a common feature of many applications, such as text editors, graphic design tools, and programming environments. It allows users to undo the last action they performed or redo an action that they previously undid.
A doubly linked list data structure is a commonly used approach to implementing undo and redo functionality. In this approach, each action taken by the user is stored as a node in a doubly linked list. Each node in the list contains information about the action taken, as well as a reference to the previous and next nodes in the list.
When the user performs an undo action, the application goes back to the previous node in the linked list and undoes the action stored in that node. Similarly, when the user performs a redo action, the application goes forward to the next node in the linked list and redoes the action stored in that node.
Since a doubly linked list allows both forward and backward traversal, it provides an efficient way to implement undo and redo functionality. By using a doubly linked list, the application can easily navigate back and forth in the user’s action history without needing to store multiple copies of the application state.
Overall, the use of a doubly linked list to manage undo and redo functionality provides a convenient and efficient way for users to modify their work without fear of losing their progress.
3. Music playlists
Music playlists are a common feature of media players that allow users to create and organize their own personal music collections.
One way to implement a playlist is to use a doubly linked list data structure. In this approach, each song in the playlist is stored as a node in a doubly linked list. Each node contains information about the song, as well as a reference to the previous and next nodes in the list.
By using a doubly linked list, media players can easily implement features such as shuffling and repeating songs, as well as moving songs up or down in the playlist. When a user adds or removes a song from the playlist, the player simply updates the references in the adjacent nodes in the linked list.
Additionally, a doubly linked list allows for efficient traversal of the playlist in both forward and backward directions. This is important when the user wants to skip to the next song or go back to a previous song in the playlist.
Overall, using a doubly linked list to implement music playlists in media players provides an efficient and flexible way for users to manage their music collections. The structure enables a variety of playlist features and provides an intuitive and user-friendly way to navigate and modify the playlist.
Conclusion
A doubly linked list is a versatile data structure that allows bidirectional traversal of the list. While it requires more memory than a singly linked list, it offers efficient insertion and deletion of nodes. It can be used in a variety of applications, such as browser history, undo/redo functionality, and music playlists.