Doubly Linked List

A Doubly Linked List is a type of linked list where each node is connected to both its next and previous node. This makes it easier to move forward and backward in the list. It is more flexible than a Singly Linked List, but it requires extra memory for storing the additional pointer.

Node Structure

Each node in a Doubly Linked List has three parts:

Data: The value stored in the node.
Next Pointer: Points to the next node in the list.
Previous Pointer: Points to the previous node in the list.

Example of a Node in C++:

struct Node {
    int data;   // Stores the value
    Node* prev; // Points to the previous node
    Node* next; // Points to the next node
 
    Node(int d) {
       data = d;
       prev = next = nullptr;
    }
};

By linking nodes together using both next and prev pointers, we can efficiently traverse the list in both directions.

Operations in a Doubly Linked List

1. Traversal

Traversal means moving through the list to access its elements.

Steps to Traverse:

Forward Traversal:
- Start from the head.
- Print or process each node’s data.
- Move to the next node using current = current->next.
- Stop when current == NULL.
Backward Traversal (Optional):
- Start from the tail.
- Process each node’s data.
- Move to the previous node using current = current->prev.
- Stop when current == NULL.

2. Finding the Length

To find how many nodes are in the list:

Start from the head.
Use a counter and set it to 0.
Traverse the list while increasing the counter for each node.
Stop when current == NULL.
The counter value is the length of the list.

3. Insertion

Adding a new node requires adjusting the next and prev pointers.

a) Inserting at the Beginning

Create a new node.
Set its next pointer to the current head.
Update the prev pointer of the old head.
Update head to the new node.

b) Inserting at the End

Create a new node.
If the list is empty, set it as the head.
Otherwise, traverse to the last node.
Set the last node’s next to the new node.
Set the new node’s prev to the last node.

c) Inserting at a Specific Position

Create a new node.
Find the node after which you want to insert.
Adjust pointers to insert the new node in between two existing nodes.

4. Deletion

Removing a node requires adjusting the next and prev pointers properly.

a) Deleting the First Node

Store the current head.
Move head to the next node.
Update the new head’s prev pointer to NULL.
Delete the old head.

b) Deleting the Last Node

Traverse to the last node.
Update the second-last node’s next pointer to NULL.
Delete the last node.

c) Deleting a Node at a Specific Position

Find the node that needs to be deleted.
Update its previous node’s next pointer.
Update its next node’s prev pointer.
Delete the node.

Advantages of a Doubly Linked List

Efficient two-way traversal: You can move both forward and backward. Easy insertion and deletion: No need to traverse the list completely. Useful for complex data structures: Can be used in stacks, queues, and undo-redo functionalities.

Disadvantages of a Doubly Linked List

More memory usage: Each node needs extra memory for storing the prev pointer. Slightly more complex: Requires careful pointer management.

Applications of Doubly Linked List

Undo/Redo Functionality: In text editors, web browsers, etc.
Cache Implementation: Quick insertion and deletion of elements.
Browser History: Allows navigating back and forward.
Music Players: Managing playlists efficiently.
Deque (Double-Ended Queue): Fast insertion and deletion at both ends.

Singly Linked List Introduction to Stack