Last Updated: 22 Apr, 2022

Deletion In Doubly Linked List

Easy

Asked in companies

Solve now

Problem statement

You are given a Doubly Linked List of ‘N’ positive integers. Your task is to delete a node at position ‘POS’ in the linked list.

Note:

Assume that the Indexing for the linked list starts from 0.

EXAMPLE:

Input: ‘N’ = 5, 'LIST' = [1, 1, 2, 3, 4, -1], ‘POS’ = 1.

Output: 1 < - > 2 < - > 3 < - > 4 

Here in the given list, we can see that the node at position 1 is deleted.

Input Format :

The first line of input contains a single integer T, representing the number of test cases or queries to be run. 

The second line of the test case contains space-separated integers which are the nodes of the linked list and each line ends with -1 to indicate that the sublist is over. Thus, -1 will never be a linked list element.

The third line of each test case contains a single integer ‘POS’ denoting the position at which the node has to be deleted.

Output format :

The first and only line of each test case in the output contains the linked list after deleting the required element.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= ‘T’ <= 10 
2 <= ‘N’ <= 10^4 
0 <= ‘POS < N  
1 <= ‘data’ <= 10^7
Where 'N' is the size of the doubly linked list, and ‘data’ is the Integer data of the doubly linked list.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

If ‘POS’ is 0 means that we have to delete a node at the beginning of the linked list means we have to make the 2nd node as the head node so just set ‘head’ = ‘head → next’ and ‘head → prev’ = ‘NULL’.

If ‘POS’ is ‘N - 1’ means that we have to add a node at the end of the linked list so just traverse to position ‘N - 2’ of the linked list and set the ‘NEXT’ of the node as ‘NULL’.

If ‘POS’ is in the range [1, N - 2] then we simply traverse to position ‘POS’ and link the previous node of the current node to the next node of the current node by setting ‘curr->prev->next’ = ‘curr->next’ and ‘curr->next->prev’ = ‘curr->prev’.

Algorithm :

If ‘POS’ is 0
- Set ‘head’ = ‘head->next’.
- ‘head->prev’ = ‘NULL’.
- Return.
Declare a variable ‘len’ and initialize it with 0, denoting the length of the linked list.
Assign ‘temp’ to ‘head’.
while ‘temp’ is not equal to NULL
- ‘len += 1’
- ‘temp = temp -> next’.
Assign ‘temp’ to ‘head’.
If ‘POS’ is ‘len - 1’
- Move ‘temp’ to second last node of the list (say iterator ‘i’)
  - ‘temp = temp -> next’.
- ‘temp -> next = NULL’.
- Return.
Move ‘temp’ at ‘POS’ (say iterator ‘i’)
- ‘temp = temp -> next’.
‘temp->prev->next’ = ‘temp->next’.
‘temp->next->prev’ = ‘temp->prev’.

Solve now