Write a function to Delete a node from Doubly Linked List ?

In a single linked list, every node has link to its next node in the sequence.
So, we can traverse from one node to another node only in one direction and we cannot traverse back. We can solve this kind of problem by using double linked list.
Double linked list is a sequence of elements in which every element has links to its previous element and next element in the sequence.
In double linked list, every node has link to its previous node and next node. So, we can traverse forward by using next field and can traverse backward by using previous field.

Algorithm

[pastacode lang=”markdown” manual=”Algorithm%20to%20delete%20node%20from%20any%20position%0AInput%20%3A%0A%20head%20%0A%20%7B%0A%20%20%20Pointer%20to%20the%20first%20node%20of%20the%20list%0A%20%7D%0Alast%20%0A%20%7B%0A%20%20%20Pointer%20to%20the%20last%20node%20of%20the%20list%0A%20%7D%0AN%20%0A%20%7B%0A%20%20Position%20to%20be%20deleted%20from%20list%0A%20%7D%0ABegin%20%3A%0A%20%20%20%20current%20%E2%86%90%20head%3B%0A%20%20%20%20For%20i%20%E2%86%90%201%20to%20N%20and%20current%20!%3D%20NULL%20do%0A%20%20%20%20%20%20%20%20current%20%E2%86%90%20current.next%3B%0A%20%20%20%20End%20for%0A%20%20%20%20If%20(N%20%3D%3D%201)%20then%0A%20%20%20%20%20%20%20%20deleteFromBeginning()%0A%20%20%20%20End%20if%0A%20%20%20%20Else%20if%20(current%20%3D%3D%20last)%20then%20%0A%20%20%20%20%20%20%20%20deleteFromEnd()%0A%20%20%20%20End%20if%0A%20%20%20%20Else%20if%20(current%20!%3D%20NULL)%20then%0A%20%20%20%20%20%20%20%20current.prev.next%20%E2%86%90%20current.next%0A%20%20%20%20%20%20%20%20If%20(current.next%20!%3D%20NULL)%20then%0A%20%20%20%20%20%20%20%20%20%20%20%20current.next.prev%20%E2%86%90%20current.prev%3B%0A%20%20%20%20%20%20%20%20End%20if%0A%20%20%20%20%20%20%20%20unalloc%20(current)%0A%20%20%20%20%20%20%20%20write%20(‘Node%20deleted%20successfully%20from%20’%2C%20N%2C%20’%20position’)%0A%20%20%20%20End%20if%0A%20%20%20%20Else%20then%0A%20%20%20%20%20%20%20%20write%20(‘Invalid%20position’)%0A%20%20%20%20End%20if%0AEnd” message=”” highlight=”” provider=”manual”/]

Sample Code in C++

[pastacode lang=”markdown” manual=”%23include%20%3Cbits%2Fstdc%2B%2B.h%3E%20%0A%20%20%0Ausing%20namespace%20std%3B%20%0A%20%20%0Astruct%20Node%20%7B%20%0A%20%20%20%20int%20data%3B%20%0A%20%20%20%20struct%20Node*%20next%3B%20%0A%20%20%20%20struct%20Node*%20prev%3B%20%0A%7D%3B%20%0A%20%20%0A%2F*%20Function%20to%20delete%20a%20node%20in%20a%20Doubly%20Linked%20List.%20%0A%20%20%20head_ref%20–%3E%20pointer%20to%20head%20node%20pointer.%20%0A%20%20%20del%20%20–%3E%20%20pointer%20to%20node%20to%20be%20deleted.%20*%2F%0Avoid%20deleteNode(struct%20Node**%20head_ref%2C%20struct%20Node*%20del)%20%0A%7B%20%0A%20%20%20%0A%20%20%20%20if%20(*head_ref%20%3D%3D%20NULL%20%7C%7C%20del%20%3D%3D%20NULL)%20%0A%20%20%20%20%20%20%20%20return%3B%20%0A%20%20%0A%20%20%20%20%2F*%20If%20node%20to%20be%20deleted%20is%20head%20node%20*%2F%0A%20%20%20%20if%20(*head_ref%20%3D%3D%20del)%20%0A%20%20%20%20%20%20%20%20*head_ref%20%3D%20del-%3Enext%3B%20%0A%20%20%0A%20%20%20%20%2F*%20Change%20next%20only%20if%20node%20to%20be%20deleted%20is%20NOT%20%20%0A%20%20%20%20%20%20%20the%20last%20node%20*%2F%0A%20%20%20%20if%20(del-%3Enext%20!%3D%20NULL)%20%0A%20%20%20%20%20%20%20%20del-%3Enext-%3Eprev%20%3D%20del-%3Eprev%3B%20%0A%20%20%0A%20%20%20%20%2F*%20Change%20prev%20only%20if%20node%20to%20be%20deleted%20is%20NOT%20%20%0A%20%20%20%20%20%20%20the%20first%20node%20*%2F%0A%20%20%20%20if%20(del-%3Eprev%20!%3D%20NULL)%20%0A%20%20%20%20%20%20%20%20del-%3Eprev-%3Enext%20%3D%20del-%3Enext%3B%20%0A%20%20%0A%20%20%20%20%2F*%20Finally%2C%20free%20the%20memory%20occupied%20by%20del*%2F%0A%20%20%20%20free(del)%3B%20%0A%7D%20%0A%20%20%0A%2F*%20Function%20to%20delete%20the%20node%20at%20the%20given%20position%20%0A%20%20%20in%20the%20doubly%20linked%20list%20*%2F%0Avoid%20deleteNodeAtGivenPos(struct%20Node**%20head_ref%2C%20int%20n)%20%0A%7B%20%0A%20%20%20%20%2F*%20if%20list%20in%20NULL%20or%20invalid%20position%20is%20given%20*%2F%0A%20%20%20%20if%20(*head_ref%20%3D%3D%20NULL%20%7C%7C%20n%20%3C%3D%200)%20%0A%20%20%20%20%20%20%20%20return%3B%20%0A%20%20%0A%20%20%20%20struct%20Node*%20current%20%3D%20*head_ref%3B%20%0A%20%20%20%20int%20i%3B%20%0A%20%20%0A%20%20%20%20%2F*%20traverse%20up%20to%20the%20node%20at%20position%20’n’%20from%20%0A%20%20%20%20%20%20%20the%20beginning%20*%2F%0A%20%20%20%20for%20(int%20i%20%3D%201%3B%20current%20!%3D%20NULL%20%26%26%20i%20%3C%20n%3B%20i%2B%2B)%20%0A%20%20%20%20%20%20%20%20current%20%3D%20current-%3Enext%3B%20%0A%20%20%0A%20%20%20%20%2F*%20if%20’n’%20is%20greater%20than%20the%20number%20of%20nodes%20%0A%20%20%20%20%20%20%20in%20the%20doubly%20linked%20list%20*%2F%0A%20%20%20%20if%20(current%20%3D%3D%20NULL)%20%0A%20%20%20%20%20%20%20%20return%3B%20%0A%20%20%0A%20%20%20%20%2F*%20delete%20the%20node%20pointed%20to%20by%20’current’%20*%2F%0A%20%20%20%20deleteNode(head_ref%2C%20current)%3B%20%0A%7D%20%0A%20%20%0A%2F*%20Function%20to%20insert%20a%20node%20at%20the%20beginning%20%20%0A%20%20%20of%20the%20Doubly%20Linked%20List%20*%2F%0Avoid%20push(struct%20Node**%20head_ref%2C%20int%20new_data)%20%0A%7B%20%0A%20%20%20%20%2F*%20allocate%20node%20*%2F%0A%20%20%20%20struct%20Node*%20new_node%20%3D%20%20%0A%20%20%20%20%20%20%20%20%20(struct%20Node*)malloc(sizeof(struct%20Node))%3B%20%0A%20%20%0A%20%20%20%20%2F*%20put%20in%20the%20data%20%20*%2F%0A%20%20%20%20new_node-%3Edata%20%3D%20new_data%3B%20%0A%20%20%0A%20%20%20%20%2F*%20since%20we%20are%20adding%20at%20the%20beginning%2C%20%0A%20%20%20%20prev%20is%20always%20NULL%20*%2F%0A%20%20%20%20new_node-%3Eprev%20%3D%20NULL%3B%20%0A%20%20%0A%20%20%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20%20%20new_node-%3Enext%20%3D%20(*head_ref)%3B%20%0A%20%20%0A%20%20%20%20%2F*%20change%20prev%20of%20head%20node%20to%20new%20node%20*%2F%0A%20%20%20%20if%20((*head_ref)%20!%3D%20NULL)%20%0A%20%20%20%20%20%20%20%20(*head_ref)-%3Eprev%20%3D%20new_node%3B%20%0A%20%20%0A%20%20%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20%20%20(*head_ref)%20%3D%20new_node%3B%20%0A%7D%20%0A%20%20%0A%2F*%20Function%20to%20print%20nodes%20in%20a%20given%20doubly%20%0A%20%20%20linked%20list%20*%2F%0Avoid%20printList(struct%20Node*%20head)%20%0A%7B%20%0A%20%20%20%20while%20(head%20!%3D%20NULL)%20%7B%20%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20head-%3Edata%20%3C%3C%20%22%20%22%3B%20%0A%20%20%20%20%20%20%20%20head%20%3D%20head-%3Enext%3B%20%0A%20%20%20%20%7D%20%0A%7D%20%0A%20%20%0A%2F*%20Driver%20program%20to%20test%20above%20functions*%2F%0Aint%20main()%20%0A%7B%20%0A%20%20%20%20%2F*%20Start%20with%20the%20empty%20list%20*%2F%0A%20%20%20%20struct%20Node*%20head%20%3D%20NULL%3B%20%0A%20%20%0A%20%20%20%20%2F*%20Create%20the%20doubly%20linked%20list%2010%3C-%3E8%3C-%3E4%3C-%3E2%3C-%3E5%20*%2F%0A%20%20%20%20push(%26head%2C%205)%3B%20%0A%20%20%20%20push(%26head%2C%202)%3B%20%0A%20%20%20%20push(%26head%2C%204)%3B%20%0A%20%20%20%20push(%26head%2C%208)%3B%20%0A%20%20%20%20push(%26head%2C%2010)%3B%20%0A%20%20%0A%20%20%20%20cout%20%3C%3C%20%22Doubly%20linked%20list%20before%20deletion%3An%22%3B%20%0A%20%20%20%20printList(head)%3B%20%0A%20%20%0A%20%20%20%20int%20n%20%3D%202%3B%20%0A%20%20%0A%20%20%20%20%2F*%20delete%20node%20at%20the%20given%20position%20’n’%20*%2F%0A%20%20%20%20deleteNodeAtGivenPos(%26head%2C%20n)%3B%20%0A%20%20%0A%20%20%20%20cout%20%3C%3C%20%22%5CnDoubly%20linked%20list%20after%20deletion%3An%22%3B%20%0A%20%20%20%20printList(head)%3B%20%0A%20%20%0A%20%20%20%20return%200%3B%20%0A%7D%20″ message=”” highlight=”” provider=”manual”/]

Output

[pastacode lang=”markdown” manual=”Doubly%20linked%20list%20before%20deletion%3A%0A10%208%204%202%205%0ADoubly%20linked%20list%20after%20deletion%3A%0A10%204%202%205″ message=”” highlight=”” provider=”manual”/]

Time Complexity

O(n), in worst case where n is the number of nodes in the doubly linked list.

Write a function to Delete a node from Doubly Linked List ?