Doubly Linked List (DLL)
 |
| Anatomy of Doubly Linked List (DLL) |
- Doubly Linked List
- Operations on Doubly Linked List
- Summary
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 allows traversal of the list in both directions—forward and backward. Below is a detailed explanation of a doubly linked list, its structure, and how to implement it in Python.
Structure of a Doubly Linked List
In a doubly linked list, each node has three components:
- Data: The value stored in the node.
- Next: A pointer/reference to the next node in the sequence.
- Prev: A pointer/reference to the previous node in the sequence.
- The first node’s
PrevisNULLbecause there is no previous node. - The last node’s
NextisNULLbecause there is no next node.
Implementation in Python
Below is a step-by-step guide to implementing a doubly linked list in Python.
1. Node Class
The node class will have three attributes: data, next, and prev.
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
 |
| Node Class |
 |
| Doubly Linked List (DLL) Class |
2. Doubly Linked List Class
The doubly linked list class will manage the list, including adding, removing, and traversing nodes.
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 and temp.data != key:
temp = temp.next
if temp is None:
return # Key not found
if temp.prev is None: # The node to be deleted is the head
self.head = temp.next
if self.head:
self.head.prev = None
elif temp.next is None: # The node to be deleted is the last node
temp.prev.next = None
else: # The node to be deleted is in the middle
temp.prev.next = temp.next
temp.next.prev = temp.prev
def display_forward(self):
current = self.head
while current:
print(current.data, end=' ')
current = current.next
print()
def display_backward(self):
current = self.head
while current and current.next:
current = current.next
while current:
print(current.data, end=' ')
current = current.prev
print()
Explanation of the Methods
Append: Adds a node to the end of the list.
- If the list is empty, the new node becomes the head.
- Otherwise, traverse to the end of the list and update the
nextpointer of the last node and theprevpointer of the new node.
Prepend: Adds a node to the beginning of the list.
- If the list is empty, the new node becomes the head.
- Otherwise, update the
prevpointer of the current head and thenextpointer of the new node, then make the new node the head.
Delete: Removes a node from the list based on the given key.
- If the node to be deleted is the head, update the head pointer.
- If the node is in the middle or end, update the pointers of the surrounding nodes to remove the node from the list.
Display Forward: Traverses the list from the head to the last node, printing the data.
Display Backward: Traverses the list from the last node to the head, printing the data.
Advantages of a Doubly Linked List
- Bidirectional Traversal: You can traverse in both forward and backward directions.
- Easier Deletion: Deletion of a node is easier because you have a reference to the previous node.
Disadvantages of a Doubly Linked List
- More Memory: Requires extra memory to store the
prevpointers. - Complexity: Slightly more complex to implement than a singly linked list due to the need to manage two pointers.
A doubly linked list is a powerful data structure for scenarios where bidirectional traversal and easy insertion/deletion at both ends of the list are required.
Operations on a doubly linked list include various ways to manipulate and interact with the list. Below are the key operations, along with explanations and Python implementations.
1. Insertion
Insertion can be done in several ways:
- At the Beginning (Prepend)
- At the End (Append)
- After a Given Node
- Before a Given Node
a. Insert at the Beginning (Prepend)
This operation adds a new node at the start of the list.
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
b. Insert at the End (Append)
This operation adds a new node at the end of the list.
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
c. Insert After a Given Node
This operation inserts a new node after a specified node.
def insert_after(self, prev_node, data):
if prev_node is None:
print("Previous node cannot be NULL")
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
d. Insert Before a Given Node
This operation inserts a new node before a specified node.
def insert_before(self, next_node, data):
if next_node is None:
print("Next node cannot be NULL")
return
new_node = Node(data)
new_node.prev = next_node.prev
next_node.prev = new_node
new_node.next = next_node
if new_node.prev:
new_node.prev.next = new_node
else:
self.head = new_node
2. Deletion
Deletion can also be performed in several ways:
- Delete by Value
- Delete the First Node
- Delete the Last Node
- Delete a Node after a Given Node
a. Delete by Value
This operation removes a node with a specific value.
def delete(self, key):
temp = self.head
while temp and temp.data != key:
temp = temp.next
if temp is None:
return # Key not found
if temp.prev is None: # The node to be deleted is the head
self.head = temp.next
if self.head:
self.head.prev = None
elif temp.next is None: # The node to be deleted is the last node
temp.prev.next = None
else: # The node to be deleted is in the middle
temp.prev.next = temp.next
temp.next.prev = temp.prev
b. Delete the First Node
This operation removes the first node in the list.
def delete_first(self):
if self.head is None:
return
if self.head.next is None:
self.head = None
else:
self.head = self.head.next
self.head.prev = None
c. Delete the Last Node
This operation removes the last node in the list.
def delete_last(self):
if self.head is None:
return
if self.head.next is None:
self.head = None
return
last = self.head
while last.next:
last = last.next
last.prev.next = None
d. Delete a Node after a Given Node
This operation removes a node after a specified node.
def delete_after(self, prev_node):
if prev_node is None or prev_node.next is None:
print("The given node is the last node or is not valid")
return
next_node = prev_node.next
prev_node.next = next_node.next
if next_node.next:
next_node.next.prev = prev_node
3. Traversal
Traversal operations allow visiting each node in the list.
a. Traverse Forward
This operation goes through the list from the head to the end.
def traverse_forward(self):
current = self.head
while current:
print(current.data, end=' ')
current = current.next
print()
b. Traverse Backward
This operation goes through the list from the end to the head.
def traverse_backward(self):
current = self.head
while current and current.next:
current = current.next
while current:
print(current.data, end=' ')
current = current.prev
print()
4. Search
This operation finds a node with a specific value.
def search(self, key):
current = self.head
while current:
if current.data == key:
return True
current = current.next
return False
5. Update
This operation updates the data of a specific node.
def update(self, old_value, new_value):
current = self.head
while current:
if current.data == old_value:
current.data = new_value
return
current = current.next
print("Node with value", old_value, "not found.")
No comments:
Post a Comment