A Doubly Linked List is a data structure that consists of a sequence of nodes. Each node contains two pointers, one pointing to the previous node in the sequence and another pointing to the next node in the sequence. These pointers make it possible to traverse the list bidirectionally.

A node in a Doubly Linked List typically contains two fields: a data field that holds the actual value of the node, and two pointer fields that hold the addresses of the previous and next nodes in the list.

Here’s an example of a Node class that could be used to implement a Doubly Linked List in Python:

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

The __init__ method initializes a new node object with a data field and two pointer fields, prev and next, that are initially set to None.

Now let’s take a look at how a Doubly Linked List can be implemented using the Node class:

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

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node

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

    def delete(self, data):
        current_node = self.head
        while current_node is not None:
            if current_node.data == data:
                if current_node.prev is None:
                    self.head = current_node.next
                    self.head.prev = None
                elif current_node.next is None:
                    self.tail = current_node.prev
                    self.tail.next = None
                else:
                    current_node.prev.next = current_node.next
                    current_node.next.prev = current_node.prev
                return
            current_node = current_node.next

    def print_list(self):
        current_node = self.head
        while current_node is not None:
            print(current_node.data)
            current_node = current_node.next

The DoublyLinkedList class contains methods for appending and prepending nodes, deleting nodes by value, and printing the entire list.

The append method creates a new node with the given data, sets its prev pointer to the current tail node, sets the current tail node’s next pointer to the new node, and then sets the new node as the new tail node.

The prepend method works in a similar way, creating a new node with the given data, setting its next pointer to the current head node, setting the current head node’s prev pointer to the new node, and then setting the new node as the new head node.

The delete method traverses the list to find the node with the given data, then adjusts the prev and next pointers of the surrounding nodes to skip over the node to be deleted.

Finally, the print_list method traverses the list and prints each node’s data field.

Here’s an example of how the Doubly Linked List class can be used:

# create a new doubly linked list
my_list = DoublyLinkedList()

# add some nodes
my_list.append(1)
my_list.append(2)
my_list.append(3)

Inserting Nodes into a Doubly Linked List

To insert a new node into a doubly linked list, we need to create a new node and link it to the list. Let’s consider an example where we want to insert a new node after the second node in the list.

# Create a new node
new_node = Node(4)

# Link the new node to the list
temp = second_node.next
second_node.next = new_node
new_node.prev = second_node
new_node.next = temp
temp.prev = new_node

In the code above, we create a new node with a value of 4. We then link this node to the list by updating the next and prev pointers of the surrounding nodes.

Deleting Nodes from a Doubly Linked List

To delete a node from a doubly linked list, we need to update the next and prev pointers of the surrounding nodes to bypass the node we want to delete. Let’s consider an example where we want to delete the second node in the list.

# Update the surrounding nodes' pointers
first_node.next = second_node.next
second_node.next.prev = first_node

# Delete the node
del second_node

In the code above, we update the next and prev pointers of the first and third nodes to bypass the second node. We then delete the second node from memory.

Advantages and Disadvantages of Doubly Linked Lists

Doubly linked lists have several advantages over singly linked lists:

However, doubly linked lists also have some disadvantages:

Conclusion

In this article, we’ve covered the basics of doubly linked lists, including their structure, how to create them, and how to insert and delete nodes. We also discussed the advantages and disadvantages of doubly linked lists compared to singly linked lists. While doubly linked lists may require more memory and operations to maintain, they offer a powerful tool for solving certain problems where traversal in both directions is required.

Leave a Reply

Your email address will not be published. Required fields are marked *