The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Doubly Linked Lists

Next ►
►

Introduction

A doubly linked list is a type of linked list in which each node contains a data part and two pointers. These pointers are:

  1. Next Pointer: Points to the next node in the sequence.
  2. Previous Pointer: Points to the previous node in the sequence.

This structure allows traversal of the list in both directions, forward and backward, which is a significant advantage over singly linked lists.

Key Concepts

Structure of a Doubly Linked List Node

A typical node in a doubly linked list contains:

  • Data: The value or data stored in the node.
  • Next: A pointer/reference to the next node in the list.
  • Previous: A pointer/reference to the previous node in the list.

Advantages

  • Bidirectional Traversal: You can traverse the list in both directions.
  • Easier Deletion: Deleting a node is easier as you have direct access to the previous node.

Disadvantages

  • More Memory: Requires extra memory for the previous pointer.
  • Complexity: More complex to implement compared to singly linked lists.

Example Implementation in Python

Node Class

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

Doubly Linked List Class

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

    def prepend(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        self.head.prev = new_node
        new_node.next = self.head
        self.head = new_node

    def delete(self, key):
        temp = self.head
        while temp:
            if temp.data == key:
                if temp.prev:
                    temp.prev.next = temp.next
                if temp.next:
                    temp.next.prev = temp.prev
                if temp == self.head:
                    self.head = temp.next
                return
            temp = temp.next

    def display(self):
        nodes = []
        temp = self.head
        while temp:
            nodes.append(temp.data)
            temp = temp.next
        print("Doubly Linked List:", nodes)

Explanation

  1. Node Class: Defines the structure of a node with data, next, and previous pointers.
  2. DoublyLinkedList Class: Contains methods to append, prepend, delete, and display nodes in the list.

Example Usage

dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.prepend(0)
dll.display()  # Output: Doubly Linked List: [0, 1, 2, 3]
dll.delete(2)
dll.display()  # Output: Doubly Linked List: [0, 1, 3]

Practical Exercises

Exercise 1: Insert After a Given Node

Write a method to insert a new node after a given node in the doubly linked list.

def insert_after(self, prev_node, data):
    if prev_node is None:
        print("Previous node cannot be None")
        return
    new_node = Node(data)
    new_node.next = prev_node.next
    prev_node.next = new_node
    new_node.prev = prev_node
    if new_node.next:
        new_node.next.prev = new_node

Solution

dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(4)
dll.insert_after(dll.head.next, 3)
dll.display()  # Output: Doubly Linked List: [1, 2, 3, 4]

Exercise 2: Reverse the Doubly Linked List

Write a method to reverse the doubly linked list.

def reverse(self):
    temp = None
    current = self.head
    while current:
        temp = current.prev
        current.prev = current.next
        current.next = temp
        current = current.prev
    if temp:
        self.head = temp.prev

Solution

dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.append(4)
dll.reverse()
dll.display()  # Output: Doubly Linked List: [4, 3, 2, 1]

Common Mistakes and Tips

  • Forgetting to Update Pointers: Always ensure that both the next and previous pointers are updated correctly when inserting or deleting nodes.
  • Null Checks: Always check for null pointers to avoid runtime errors.
  • Memory Management: Be mindful of memory usage, especially in environments with limited resources.

Conclusion

Doubly linked lists provide a versatile and efficient way to manage collections of data with bidirectional traversal capabilities. Understanding their structure and operations is crucial for implementing more complex data structures and algorithms. In the next module, we will explore stacks, another fundamental data structure in programming.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2024. All rights reserved