How will you delete a node in a doubly-linked list (DLL)?

1.	How will you delete a node in a doubly-linked list (DLL)?
Answer» The following is the process to delete a node in a doubly-linked list (DLL): STEP 1: Create a function that takes as arguments a linked list and a node that needs to be deleted, and deletes the node. Step 2: To delete a HEAD node: Move the head pointer to the next node in the current node (head here). Set the previous pointer of the next node to the previous pointer of the current node. Step 3: If you wish to remove the centre node, follow these steps. Set the previous pointer of the next node to the previous pointer of the current node. Move the previous node's next pointer to the current node's next pointer. Remove the node. (the most recent node) You do not need to delete previous or next if they are NULL. (for removing the final node) Step 4: Call the function on the given linked list and specify the node you want to delete. Code to delete a node in a doubly-linked list: import gc # Node of the doubly linked listclass Node: def __init__(self, data): self.data = data self.next = NONE self.prev = None class DoublyLinkedList: def __init__(self): self.head = None # A function to delete a node in a Doubly Linked List. def deleteNode(self, todelete): if self.head is None or todelete is None: return # If node to be deleted is the head node if self.head == todelete: self.head = todelete.next # Change next only if node to be deleted is NOT # the last node if todelete.next is not None: todelete.next.prev = todelete.prev # Change prev only if node to be deleted is NOT # the first node if todelete.prev is not None: todelete.prev.next = todelete.next gc.collect() # Given a reference to the head of a list and an # integer, inserts a new node on the front of list def push(self, new_data): # Allocates node and inserts the data in it new_node = Node(new_data) # MAKE next of new node as head and previous as None new_node.next = self.head # Change prev of head node to new_node if self.head is not None: self.head.prev = new_node # Move the head to point to the new node self.head = new_node def printList(self, node): while(node is not None): print(node.data,end=' ') node = node.next # Start with an empty listdll = DoublyLinkedList()dll.push(2);dll.push(4);dll.push(8);dll.push(10); print ("\n The original linked list",end=' ')dll.printList(dll.head) # delete nodes from doubly linked listdll.deleteNode(dll.head)dll.deleteNode(dll.head.next)dll.deleteNode(dll.head.next)# Updated linked list will be NULL<-8->NULLprint("\n The updated linked list",end=' ')dll.printList(dll.head)Useful Resources: Networking Interview Data Structure Interview Algorithm Interview Compilers Interview Resources

Answer»

The following is the process to delete a node in a doubly-linked list (DLL):

STEP 1: Create a function that takes as arguments a linked list and a node that needs to be deleted, and deletes the node.
Step 2: To delete a HEAD node:
- Move the head pointer to the next node in the current node (head here).
- Set the previous pointer of the next node to the previous pointer of the current node.
Step 3: If you wish to remove the centre node, follow these steps.
- Set the previous pointer of the next node to the previous pointer of the current node.
- Move the previous node's next pointer to the current node's next pointer.
- Remove the node. (the most recent node)
- You do not need to delete previous or next if they are NULL. (for removing the final node)
Step 4: Call the function on the given linked list and specify the node you want to delete.

Code to delete a node in a doubly-linked list:

import gc # Node of the doubly linked listclass Node: def __init__(self, data): self.data = data self.next = NONE self.prev = None class DoublyLinkedList: def __init__(self): self.head = None # A function to delete a node in a Doubly Linked List. def deleteNode(self, todelete): if self.head is None or todelete is None: return # If node to be deleted is the head node if self.head == todelete: self.head = todelete.next # Change next only if node to be deleted is NOT # the last node if todelete.next is not None: todelete.next.prev = todelete.prev # Change prev only if node to be deleted is NOT # the first node if todelete.prev is not None: todelete.prev.next = todelete.next gc.collect() # Given a reference to the head of a list and an # integer, inserts a new node on the front of list def push(self, new_data): # Allocates node and inserts the data in it new_node = Node(new_data) # MAKE next of new node as head and previous as None new_node.next = self.head # Change prev of head node to new_node if self.head is not None: self.head.prev = new_node # Move the head to point to the new node self.head = new_node def printList(self, node): while(node is not None): print(node.data,end=' ') node = node.next # Start with an empty listdll = DoublyLinkedList()dll.push(2);dll.push(4);dll.push(8);dll.push(10); print ("\n The original linked list",end=' ')dll.printList(dll.head) # delete nodes from doubly linked listdll.deleteNode(dll.head)dll.deleteNode(dll.head.next)dll.deleteNode(dll.head.next)# Updated linked list will be NULL<-8->NULLprint("\n The updated linked list",end=' ')dll.printList(dll.head)Useful Resources:

Networking Interview
Data Structure Interview
Algorithm Interview
Compilers
Interview Resources

How will you delete a node in a doubly-linked list (DLL)?

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment