Deletion In Doubly Linked List

Easy
0/40
Average time to solve is 15m
profile
Contributed by
10 upvotes
Asked in companies
FlipkartTata Consultancy Services (TCS)Zomato

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
1 1 2 3 4 -1
1
1 2 -1
1
Sample Output 1 :
1 2 3 4
1 
Explanation Of Sample Input 1 :
For the first test case,
‘N’ = 5, 'LIST' = [1, 1, 2, 3, 4, -1], ‘POS’ = 1.
After deleting the node at position 1 the list will be:
1 < - > 2 < - > 3 < - > 4.

For the second test case,
‘N’ = 2,  'LIST' = [1, 2, -1], ‘POS’ = 1.
After deleting the node at position 1 the list will be:
1.
Sample Input 2 :
2
1 2 3 -1
0
3 4 4 -1
2
Sample Output 2 :
2 3
3 4
Hint

Can you figure out how to delete a node between two nodes?

Approaches (1)
Naive 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’.
Time Complexity

O(N), where ‘N’ is the size of the linked list.

 

We are traversing the linked list two times in the worst case.

Hence, the overall time complexity will be O(N).

Space Complexity

O(1)
 

We are not using any extra space.

Hence the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Deletion In Doubly Linked List
Full screen
Console