Write a function to delete a given node in a doubly linked list
(a) Original Doubly Linked List
(a) After deletion of head node
(a) After deletion of middle node
(a) After deletion of last node
Algorithm
Let the node to be deleted is del.
1) If node to be deleted is head node, then change the head pointer to next current head.
2) Set next of previous to del, if previous to del exixts.
3) Set prev of next to del, if next to del exixts.
Java Programming:
[pastacode lang=”java” manual=”%2F%2F%20Java%20program%20to%20delete%20a%20node%20from%20doubly%20linked%20list%0A%20%0Aclass%20LinkedList%20%7B%0A%20%0A%20%20%20%20static%20Node%20head%20%3D%20null%3B%0A%20%0A%20%20%20%20class%20Node%20%7B%0A%20%0A%20%20%20%20%20%20%20%20int%20data%3B%0A%20%20%20%20%20%20%20%20Node%20next%2C%20prev%3B%0A%20%0A%20%20%20%20%20%20%20%20Node(int%20d)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20data%20%3D%20d%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20next%20%3D%20prev%20%3D%20null%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*Function%20to%20delete%20a%20node%20in%20a%20Doubly%20Linked%20List.%0A%20%20%20%20head_ref%20–%3E%20pointer%20to%20head%20node%20pointer.%0A%20%20%20%20del%20%20–%3E%20%20pointer%20to%20node%20to%20be%20deleted.%20*%2F%0A%20%20%20%20void%20deleteNode(Node%20head_ref%2C%20Node%20del)%20%7B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20base%20case%20*%2F%0A%20%20%20%20%20%20%20%20if%20(head%20%3D%3D%20null%20%7C%7C%20del%20%3D%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20If%20node%20to%20be%20deleted%20is%20head%20node%20*%2F%0A%20%20%20%20%20%20%20%20if%20(head%20%3D%3D%20del)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20head%20%3D%20del.next%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Change%20next%20only%20if%20node%20to%20be%20deleted%20is%20NOT%20the%20last%20node%20*%2F%0A%20%20%20%20%20%20%20%20if%20(del.next%20!%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20del.next.prev%20%3D%20del.prev%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Change%20prev%20only%20if%20node%20to%20be%20deleted%20is%20NOT%20the%20first%20node%20*%2F%0A%20%20%20%20%20%20%20%20if%20(del.prev%20!%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20del.prev.next%20%3D%20del.next%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Finally%2C%20free%20the%20memory%20occupied%20by%20del*%2F%0A%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20UTILITY%20FUNCTIONS%20*%2F%0A%20%20%20%20%2F*%20Function%20to%20insert%20a%20node%20at%20the%20beginning%20of%20the%20Doubly%20Linked%20List%20*%2F%0A%20%20%20%20void%20push(Node%20head_ref%2C%20int%20new_data)%20%7B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20allocate%20node%20*%2F%0A%20%20%20%20%20%20%20%20Node%20new_node%20%3D%20new%20Node(new_data)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20since%20we%20are%20adding%20at%20the%20begining%2C%0A%20%20%20%20%20%20%20%20%20prev%20is%20always%20NULL%20*%2F%0A%20%20%20%20%20%20%20%20new_node.prev%20%3D%20null%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20%20%20%20%20%20%20new_node.next%20%3D%20(head)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20change%20prev%20of%20head%20node%20to%20new%20node%20*%2F%0A%20%20%20%20%20%20%20%20if%20((head)%20!%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20(head).prev%20%3D%20new_node%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20%20%20%20%20%20%20(head)%20%3D%20new_node%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%2F*Function%20to%20print%20nodes%20in%20a%20given%20doubly%20linked%20list%0A%20%20%20%20%20This%20function%20is%20same%20as%20printList()%20of%20singly%20linked%20lsit%20*%2F%0A%20%20%20%20void%20printList(Node%20node)%20%7B%0A%20%20%20%20%20%20%20%20while%20(node%20!%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(node.data%20%2B%20%22%20%22)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20node%20%3D%20node.next%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20public%20static%20void%20main(String%5B%5D%20args)%20%7B%0A%20%20%20%20%20%20%20%20LinkedList%20list%20%3D%20new%20LinkedList()%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Let%20us%20create%20the%20doubly%20linked%20list%2010%3C-%3E8%3C-%3E4%3C-%3E2%20*%2F%0A%20%20%20%20%20%20%20%20list.push(head%2C%202)%3B%0A%20%20%20%20%20%20%20%20list.push(head%2C%204)%3B%0A%20%20%20%20%20%20%20%20list.push(head%2C%208)%3B%0A%20%20%20%20%20%20%20%20list.push(head%2C%2010)%3B%0A%20%0A%20%20%20%20%20%20%20%20System.out.println(%22Original%20Linked%20list%20%22)%3B%0A%20%20%20%20%20%20%20%20list.printList(head)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20delete%20nodes%20from%20the%20doubly%20linked%20list%20*%2F%0A%20%20%20%20%20%20%20%20list.deleteNode(head%2C%20head)%3B%20%20%2F*delete%20first%20node*%2F%0A%20%0A%20%20%20%20%20%20%20%20list.deleteNode(head%2C%20head.next)%3B%20%20%2F*delete%20middle%20node*%2F%0A%20%0A%20%20%20%20%20%20%20%20list.deleteNode(head%2C%20head.next)%3B%20%20%2F*delete%20last%20node*%2F%0A%20%20%20%20%20%20%20%20System.out.println(%22%22)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Modified%20linked%20list%20will%20be%20NULL%3C-8-%3ENULL%20*%2F%0A%20%20%20%20%20%20%20%20System.out.println(%22Modified%20Linked%20List%22)%3B%0A%20%20%20%20%20%20%20%20list.printList(head)%3B%0A%20%20%20%20%7D%0A%7D” message=”” highlight=”” provider=”manual”/]Time Complexity: O(1)
Time Complexity: O(1)