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
__init__ method initializes a new node object with a
data field and two pointer fields,
next, that are initially set to
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
DoublyLinkedList class contains methods for appending and prepending nodes, deleting nodes by value, and printing the entire list.
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.
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.
delete method traverses the list to find the node with the given data, then adjusts the
next pointers of the surrounding nodes to skip over the node to be deleted.
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)
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
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
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
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:
- They allow traversal in both directions, making it easier to iterate through the list backwards.
- They allow for easy insertion and deletion of nodes.
- They don’t require a separate function to traverse the list backwards.
However, doubly linked lists also have some disadvantages:
- They require more memory to store the extra
- They require more operations to maintain the integrity of the list, since we need to update both
prevpointers when we insert or delete nodes.
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.