Doubly Linked List Data Structure - Revision Notes

Introduction to Doubly Linked List Data Structure

A doubly linked list is a type of linked list in which each node contains a reference to both the next and the previous node in the sequence. This bi-directional linking allows for traversal of the list in both forward and backward directions, enhancing the flexibility of operations compared to a singly linked list.

Importance and Applications of Doubly Linked List Data Structure

→ Bidirectional Traversal: Allows traversal in both directions, making operations like reversing the list more efficient.
Example: Doubly linked lists are useful in applications where elements need to be accessed or modified from both ends, such as in browser history or undo/redo operations.

→ Implementation of Deques: Useful for implementing double-ended queues (deques) where elements can be added or removed from both ends.
Example: Deques are implemented using doubly linked lists to allow insertion and deletion from both the front and rear ends.

→ Improved Deletion: Allows for more efficient deletion of a given node when a reference to that node is provided.
Example: In an ordered list or a priority queue, deleting a specific node is more efficient with a doubly linked list as it can directly access the previous node.

Key Operations of Doubly Linked List Data Structure

→ Insert: Add an element to the doubly linked list.
→ Delete: Remove an element from the doubly linked list.
→ Traverse Forward: Visit each element from the head to the tail.
→ Traverse Backward: Visit each element from the tail to the head.
→ Search: Find a specific element in the doubly linked list.

Insert Operation in Doubly Linked List Data Structure

The insert operation adds an element to the doubly linked list. Here's the algorithm and pseudocode:

Algorithm:

1. Create a new node with the given data.
2. Set the next pointer of the new node to point to the current head of the linked list.
3. Set the previous pointer of the current head to point to the new node (if the list is not empty).
4. Update the head pointer to point to the new node.

Pseudocode:

function insert(head, data):
    newNode = new Node(data)
    newNode.next = head
    if head != null:
        head.prev = newNode
    head = newNode
    

Delete Operation in Doubly Linked List Data Structure

The delete operation removes an element from the doubly linked list. Here's the algorithm and pseudocode:

Algorithm:

1. Find the node to be deleted.
2. If the node to be deleted is the head, update the head pointer.
3. Adjust the next pointer of the previous node to skip over the node to be deleted.
4. Adjust the previous pointer of the next node to skip over the node to be deleted.
5. Delete the node and free memory.

Pseudocode:

function deleteNode(head, key):
    currentNode = head
    while currentNode != null:
        if currentNode.data == key:
            if currentNode.prev != null:
                currentNode.prev.next = currentNode.next
            if currentNode.next != null:
                currentNode.next.prev = currentNode.prev
            if currentNode == head:
                head = currentNode.next
            free(currentNode)
            return head
        currentNode = currentNode.next
    return head
    

Traverse Forward Operation in Doubly Linked List Data Structure

The traverse forward operation visits each element from the head to the tail. Here's the algorithm and pseudocode:

Algorithm:

1. Start from the head of the doubly linked list.
2. Iterate through each node, performing the desired operation.
3. Continue until reaching the end of the doubly linked list (null pointer).

Pseudocode:

function traverseForward(head):
    currentNode = head
    while currentNode != null:
        // Perform operation on currentNode
        currentNode = currentNode.next
    

Traverse Backward Operation in Doubly Linked List Data Structure

The traverse backward operation visits each element from the tail to the head. Here's the algorithm and pseudocode:

Algorithm:

1. Start from the tail of the doubly linked list.
2. Iterate through each node, performing the desired operation.
3. Continue until reaching the start of the doubly linked list (null pointer).

Pseudocode:

function traverseBackward(tail):
    currentNode = tail
    while currentNode != null:
        // Perform operation on currentNode
        currentNode = currentNode.prev
    

Search Operation in Doubly Linked List Data Structure

The search operation finds a specific element in the doubly linked list. Here's the algorithm and pseudocode:

Algorithm:

1. Start from the head of the doubly linked list.
2. Iterate through each node, comparing the node's data with the target data.
3. If found, return the node; otherwise, continue until reaching the end of the doubly linked list.

Pseudocode:

function search(head, target):
    currentNode = head
    while currentNode != null:
        if currentNode.data == target:
            return currentNode
        currentNode = currentNode.next
    return null
    

Time Complexity and Space Complexity of Doubly Linked List

Time Complexity: Insertion, deletion, and search operations have an average time complexity of O(n), where n is the number of elements in the linked list, due to traversal. However, certain operations like deletion can be more efficient if the node reference is provided.

Space Complexity: The space complexity is O(n), where n is the number of elements in the linked list, due to the storage of elements and two pointers (next and previous).

Advantages of Doubly Linked List Data Structure

→ Bidirectional Traversal: Allows for easy traversal in both forward and backward directions.
→ Efficient Deletion: Deletion operations are more efficient when a reference to the node to be deleted is provided.
→ Flexibility: Supports various complex data structures like deques and can be adapted for specific requirements.

Disadvantages of Doubly Linked List Data Structure

→ Memory Overhead: Requires more memory due to the storage of two pointers (next and previous) for each node.
→ Complexity: More complex to implement and manage compared to singly linked lists and arrays.
→ Performance: Operations might be slower due to the overhead of maintaining two pointers.