In the last blog post we saw the implementation of Singly Linked List. Now in this post, we'll have detailed a look at his brother the Doubly Linked List.
Understanding Doubly Linked Lists
Just like singly linked lists, a doubly linked list is a data structure that consists of a collection of nodes. Each node, in this case, is a separate object, but what makes it unique is that each node is linked not only to the next but also to the previous node. This two-way linkage allows for more efficient traversal in both directions.
In contrast to the singly linked list, which only points to the next element, a doubly linked list has two pointers in each node, one pointing to the next element and one pointing to the previous element.
Adding a Node
Adding a node in a doubly linked list is a bit more intricate than in a singly linked list. Suppose we have a node cur that we want to insert between the prev node and the next node. To achieve this, we must perform the following steps:
- Set the reference field of the
prevnode to point to thecurnode. - Set the reference field of the
curnode to point to thenextnode. - Adjust the reference field of the
nextnode to also point back to thecurnode, completing the two-way linkage.
The insertion process in a doubly linked list still maintains its efficiency, and you can insert a new node in O(1) time complexity when you have references to the prev and next nodes.
Deleting a Node
Deleting a node in a doubly linked list, much like insertion, requires a bit more work due to the two-way linkage. Let's consider a node cur that we want to delete:
- Find the
curnode's previous nodeprevand next nodenextfirst. - Adjust the reference field of the
prevnode to point to thenextnode, breaking the linkage from thecurnode. - Adjust the reference field of the
nextnode to point back to theprevnode.
In a doubly linked list, finding the next node using the reference field is simple. However, finding the previous node prev is equally efficient since we can traverse the list in both directions. The time complexity for deleting a node remains O(1).
Implementation with Python
Now, let's dive into the implementation of a doubly linked list in Python:
# ListNode class represents a node in the doubly linked list.
class ListNode:
def __init__(self, val):
self.val = val # Value of the current node
self.prev = None # Reference to the previous node
self.next = None # Reference to the next node
# MyLinkedList class implements the doubly linked list with the specified methods.
class MyLinkedList:
def __init__(self):
self.head = None # Reference to the head node (the first node)
self.tail = None # Reference to the tail node (the last node)
self.size = 0 # Number of nodes in the linked list
# Get the value of the node at the specified index in the linked list.
def get(self, index):
if index < 0 or index >= self.size:
return -1 # Return -1 for an invalid index
current = self.head
for _ in range(index):
current = current.next
return current.val
# Add a new node with the given value to the head of the linked list.
def addAtHead(self, val):
new_node = ListNode(val)
if self.size == 0:
self.head = self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
self.size += 1
# Append a new node with the given value to the tail of the linked list.
def addAtTail(self, val):
new_node = ListNode(val)
if self.size == 0:
self.head = self.tail = new_node
else:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
self.size += 1
# Add a new node with the given value before the node at the specified index.
def addAtIndex(self, index, val):
if index < 0 or index > self.size:
return # Do nothing for an invalid index
if index == 0:
self.addAtHead(val)
elif index == self.size:
self.addAtTail(val)
else:
new_node = ListNode(val)
current = self.head
for _ in range(index - 1):
current = current.next
new_node.prev = current
new_node.next = current.next
current.next.prev = new_node
current.next = new_node
self.size += 1
# Delete the node at the specified index in the linked list.
def deleteAtIndex(self, index):
if index < 0 or index >= self.size:
return # Do nothing for an invalid index
if self.size == 1:
self.head = self.tail = None
elif index == 0:
self.head = self.head.next
self.head.prev = None
elif index == self.size - 1:
self.tail = self.tail.prev
self.tail.next = None
else:
current = self.head
for _ in range(index):
current = current.next
current.prev.next = current.next
current.next.prev = current.prev
self.size -= 1
Now that's about Doubly Linked Lists. See you in the next one. Until then, Sayonara!
SOCIAL SHARE CARD GENERATOR