Insertion at the Beginning in Doubly Linked List:
To insert a new node at the front of doubly linked list,
Create a new node, say new_node with its previous pointer as NULL.
Set the next pointer to the current head, new_node->next = head.
Check if the linked list is not empty then we update the previous pointer
of the current head to the new node, head->prev = new_node.
Finally, we return the new node as the head of the linked list.
def insert_at_front(head, new_data):
# Create a new node
new_node = Node(new_data)
# Make next of new node as head
new_node.next = head
# Change prev of head node to new node
if head is not None:
head.prev = new_node
# Return the new node as the head of doubly lL
return new_node
To insert a new node after a specific node,
Find the given node in the linked list, say curr.
Once we find it, create a new node say new_node with the given input data.
Set the new node’s previous pointer to given node, new_node->prev = curr.
Set the new node’s next pointer to the given node’s next,
new_node->next = curr->next.
Then, we update the next pointer of given node with new node,
curr->next = new_node.
Also, if the new node is not the last node of the linked list, then update previous
pointer of new node’s next node to new node,
new_node->next->prev = new_node.
def insert_after(head, key, new_data):
curr = head
# Iterate over Linked List to find the key
while curr is not None:
if curr.data == key:
break
curr = curr.next
# If curr becomes None, the given key is not found in the linked list
if curr is None:
return head
# Create a new node
new_node = Node(new_data)
# Set prev of new node to the given node
new_node.prev = curr
# Set next of new node to the next of the given node
new_node.next = curr.next
# Update next of the given node to new node
curr.next = new_node
# Update the prev of new node's next with the new node
if new_node.next is not None:
new_node.next.prev = new_node
return head
To insert a new node at the end,
Allocate memory for a new node, say new_node and assign the
provided value to its data field.
Initialize the next pointer of the new node to NULL, new_node->next =
NULL.
If the linked list is empty, we set the new node as the head of linked list
and return it as the new head of the linked list.
Traverse the entire list until we reach the last node, say curr.
Set the next pointer of last node to new node, curr->next = new_node
Set the prev pointer of new node to last node, new_node->prev = curr
def insert_end(head, new_data):
# Create a new node
new_node = Node(new_data)
# If the linked list is empty, set the new node as the head
if head is None:
head = new_node
else:
curr = head
while curr.next is not None:
curr = curr.next
# Set the next of the last node to the new node
curr.next = new_node
# Set the prev of the new node to the last node
new_node.prev = curr
return head
Deletion at the Beginning in Doubly Linked List
The idea is to update the head of the doubly linked list to the node next to head
node and if the new head is not NULL, then set the previous pointer of new
head to NULL.
To delete a node at the beginning in doubly linked list, we can use the
following steps:
Check if the list is empty, there is nothing to delete, return.
Store the head pointer in a variable, say temp.
Update the head of linked list to the node next to the current
head, head = head->next.
If the new head is not NULL, update the previous pointer of new head
to NULL, head->prev = NULL.
def del_head(head):
# If empty, return None
if head is None:
return None
# Store in temp for deletion later
temp = head
# Move head to the next node
head = head.next
# Set prev of the new head
if head is not None:
head.prev = None
# Return new head
return head
To delete a node after a specific node in a doubly linked list, we can use
the following steps:
Initialize a variable , say curr points to the node with the key value in
the linked list.
if found , check if curr->next is not NULL.
o If it’s NULL then there is no node to delete , return.
o else , set a pointer nodeDelete to curr->next, which is the
node to be deleted.
o Update curr->next to point to nodeDelete->next.
o If nodeDelete->next is not NULL, update
the previous pointer of nodeDelete->next to curr.
Delete nodeDelete to free memory.
def delete_after(head, key):
curr = head
# Iterate over Linked List to find the key
while curr is not None:
if curr.data == key:
break
curr = curr.next
# If curr is None or curr.next is None,
# there is no node to delete
if curr is None or curr.next is None:
return head
# Node to be deleted
node_delete = curr.next
# Update the next of the current node to
# the next of the node to be deleted
curr.next = node_delete.next
# If the node to be deleted is not the last node,
# update the previous pointer of the next node
if node_delete.next is not None:
node_delete.next.prev = curr
return head
To delete a node at the end in doubly linked list, we can use the following
steps:
Check if the doubly linked list is empty. If it is empty, then there is
nothing to delete.
If the list is not empty, then move to the last node of the doubly linked
list, say curr.
Update the second-to-last node’s next pointer to
NULL, curr->prev->next = NULL.
Free the memory allocated for the node that was deleted.
def del_last(head):
if head is None:
return None
if head.next is None:
return None
# Traverse to the last node
curr = head
while curr.next is not None:
curr = curr.next
# Update the previous node's next pointer
if curr.prev is not None:
curr.prev.next = None
# Return the updated head
return head
TRAVERSAL
Algorithm
Recursively traverse the doubly linked list until it reaches the last node.
While backtracking, reverse the links between the nodes. To reverse
the links:
o Change the next pointer of the current node to point to
its previous node.
o Change the prev pointer of the current node to point to
its next node.
Adjust the head of the doubly linked list to point to the last node.
def reverse(curr):
# Base case: if the list is empty or we reach the end
of the list
if curr is None:
return None
# Swap the next and prev pointers
temp = curr.prev
curr.prev = curr.next
curr.next = temp
# If the previous node (after swap) is null, this is
the new head
if curr.prev is None:
return curr
# Recurse for the next node
return reverse(curr.prev)
def print_list(node):
while node is not None:
print(node.data, end=" ")
node = node.next
print()
REVERSE /TRAVERSAL IN SLL
Input : Head of following linked list
1->2->3->4->NULL
Output : Linked list should be changed to,
4->3->2->1->NULL
def reverse(self):
prev = None
current = self.head
while(current is not None):
next = current.next
current.next = prev
prev = current
current = next
self.head = prev
