Doubly LinkedList

Now that you all have learned about singly LinkedList, understanding doubly LinkedList will be much easier. But, before actually getting into the technical aspects of Doubly LinkedList let us solve a brain teaser.

Here it is :

Why did the doubly linked list always get invited to programming parties?

Because it was known for its exceptional ability to "link" up with any data structure and "double" the fun!

Hehe 😂

What is doubly LinkedList?

A doubly linked list is a data structure that consists of a sequence of nodes, where each node contains two references or pointers: one pointing to the previous node and another pointing to the next node in the sequence.

In contrast to a singly linked list, which only has a reference to the next node, a doubly linked list allows for traversal in both directions.

Here are some key characteristics and operations of a doubly linked list :

✅ Nodes: Each node in a doubly linked list contains two pointers: a "previous" pointer and a "next" pointer. Additionally, nodes typically store some data or value.

✅ Head and Tail: A doubly linked list has a head node, which is the first node in the list, and a tail node, which is the last node. The previous pointer of the head node is usually null, indicating the beginning of the list, and the next pointer of the tail node is null, indicating the end of the list.

✅ Bidirectional traversal: With the presence of both previous and next pointers, you can traverse the list in both forward and backward directions. This allows efficient navigation and enables operations such as iterating from the beginning to the end or vice versa.

✅ Insertion and deletion: Insertion and deletion operations in a doubly linked list are more flexible compared to a singly linked list. You can insert or delete nodes at the beginning, end, or at any position within the list by adjusting the pointers appropriately.

✅ Memory overhead: Compared to a singly linked list, a doubly linked list requires additional memory to store the previous pointers. This increased memory usage is the trade-off for the ability to traverse the list in both directions.

Given below is the representation of Doubly LinkedList :

// Class for Doubly Linked List
public class DoublyLL {

// 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 value) {
data = value;
}
}
}

Applications of Doubly LinkedList

Doubly linked lists find applications in various areas of computer science and programming.

Their ability to traverse both forward and backward, along with efficient insertion and deletion operations, makes them suitable for specific scenarios.

Some common applications of doubly linked lists include:

👉 Browser history: Web browsers use doubly linked lists to keep track of the user's browsing history. Each visited webpage is stored as a node in the list, allowing users to navigate backward and forward through the visited pages.

👉 Undo/Redo functionality: Many software applications provide the ability to undo or redo operations performed by the user. Doubly linked lists can be employed to maintain a history of actions, enabling easy reversal or reapplication of changes.

👉 Music and video playlists: Media players often utilize doubly linked lists to manage playlists. Each song or video is represented by a node, allowing users to navigate through the playlist in both directions and make modifications such as adding or removing items.

👉 Text editors: Doubly linked lists can be used in text editors to implement features such as cursor movement, text selection, and undo/redo functionality. The list structure facilitates efficient navigation and modification of the text content.

These are just a few examples of how doubly linked lists are applied in different domains.

Their flexibility and functionality make them a valuable tool for various programming and data management tasks.

Homework

Learn about advantages and disadvantages of Doubly LinkedList

Hope you enjoyed reading

Happy learning

Now what ?

Check the following blog for LinkedList

Introduction to LinkedList

https://madalgos.in/blog-space/27

https://madalgos.in/blog-space/28

https://madalgos.in/blog-space/29

Basic opertaions on LinkedList

https://madalgos.in/blog-space/30

https://madalgos.in/blog-space/32