Insertion In Doubly Linked List

Easy
0/40
Average time to solve is 15m
profile
Contributed by
18 upvotes
Asked in companies
Red HatMicrosoftTata Consultancy Services (TCS)

Problem statement

You are given a Doubly linked list, where every node in the linked list contains two pointers ‘next’ and ‘prev’ which point to the next node and previous node in the list respectively. All nodes have some positive integer value associated with them. Your task is to insert an integer value ‘VAL’ in the linked list at a given position ‘K’.

Note:

The position given will always be less than or equal to the length of the linked list.
Assume that the Indexing for the linked list starts from 0.
EXAMPLE: 
Input :
‘K’ = 3, ‘VAL’ = 4
list = [1, 2, 3]
Output: [1, 2, 3, 4]


The ‘VAL’ = 4, is inserted at end of the above doubly linked list.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', the number of test cases.

The first line of each test case contains the integers ‘K’, and ‘VAL’, denoting the position of insertion operation, and the value of the new node to be inserted in the list respectively.

The second line of each test case contains an array of positive integers denoting the nodes of the linked list.
Output format : 
For each test case, print the doubly linked list after the insertion operation.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Here, '-1' marks the end of the linked list.
Constraints : 
1 <= 'T' <= 10
1 <= Length of the list <= 10^4
0 <= ‘K’ <= Length of the list, where ‘K’ is 0-indexed.
1 <= 'VAL' <= 10^5

Time Limit: 1 sec
Sample Input 1:
2
0 0
1 2 3 4 -1
5 5
5 4 3 2 1 -1
Sample Outpu.t 1:
0 1 2 3 4
5 4 3 2 1 5
Explanation Of Sample Input 1 :
For the first test case, ‘K’ = 0 denotes the starting index of the list, so the new element is inserted before the head of the list and the new head will be then a node with ‘VAL’ = 0

Hence, the resulting doubly linked list would be : 0 1 2 3 4

For the second test case, ‘K’ = 5 = size of the list denotes the new element to be inserted at the end of the list. 

Hence, the resulting doubly linked list would be: 5 4 3 2 1 5
Sample Input 2 :
2
2 4
10 11 5 -1
1 5
2 8 -1
Sample Output 2 :
10 11 4 5
2 5 8
Hint

Can we iterate over the list?

Approaches (1)
Naive Approach

Approach: 
 

Iterate the list starting from the ‘HEAD’ to the ‘Kth’ node.

Insert a new node ‘TEMP’ which is pointing to the ‘Kth’ node next and then changing the ‘Kth’ node next to ‘TEMP’, changing the ‘Kth’ node->next->prev to ‘TEMP’ and then making the ‘TEMP’ prev point to ‘Kth’ node. Like:

 

Algorithm :  
 

  • Firstly check if the new is inserted at the beginning:
    • Simply create a ‘TEMP’ node and make ‘TEMP’ and ‘HEAD’ point to each other
    • Return ‘TEMP’ as this is our new ‘HEAD’.
  • Check if the new is inserted at the end:
    • Create a node ‘TEMP’ with values as ‘VAl’
    • Go to the last node in the list ‘ITR’ and make ‘TEMP’ prev point to ‘ITR’ and ‘ITR’ next point to ‘TEMP’
    • Return ‘HEAD’
  • Create an iterator ‘ITR’ pointing to ‘HEAD’ initially to travel the list.
  • For I from ‘0’ to ‘K-1’:
    • Make the ‘ITR’ point to ‘Next’ of ‘ITR’.
  • Create a ‘TEMP’ Node pointer of value ‘VAL’
  • To insert the ‘TEMP’ at the ‘Kth’ position do the following:
    • Assign ‘TEMP->next’ as ‘ITR->next’.
    • If ‘ITR-> next’ is not ‘NULL, then :
      • Assign ‘ITR->next->prev’ as ‘TEMP’
    • Then assign ‘ITR-> next’ as ‘TEMP’
    • Assign ‘TEMP-> prev’ as ‘ITR’
    • This inserts the ‘TEMP’ pointer at the ‘Kth’ position in the list.
  • Return ‘HEAD’
Time Complexity

O(K), Where ‘K’ is the position of the nodes to be inserted in the list.

As we are iterating the list for ‘K’ iterations, the time complexity will be O(K)

Space Complexity

O(1).


As we are using the extra pointers ‘itr’ and ‘temp’ of size ‘4 bytes’, the space complexity will be O(1).

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