I have created a Doubly linked list Insertion at a given position program using JavaScript. It is supposed to append at the beginning, middle, and end of the node.
Here is the problem: all test cases are not working fine, like for this input:
2 4 5
2 6
My output is 2 6 4 5 and the expected output is 2 4 5 6.
Could you please rectify my mistake and modify that so all the edge cases will work fine here? head, pos, and data are the starting pointers. pos means in which position you want to enter the new node, and data is new data. The code is given below.
Input:
2<->4<->5p = 2, x = 6Output:
2 4 5 6Explanation:
p = 2, and x = 6. So, 6 is inserted after p, i.e, at position 3.
Input:
1<->2<->3<->4p = 0, x = 44Output:
1 44 2 3 4Explanation:
p = 0, and x = 44 . So, 44 is inserted after p, i.e, at position 1.
class Solution {
addNode(head, pos, data) {
const newHead = { data: data, prev: null, next: null };
if (head === null) {
return newHead;
}
let temp = head;
for (let i = 1; i < pos - 1 && temp.next !== null; i++) {
temp = temp.next;
}
if (pos > 1 && temp === null) {
return head;
}
newHead.next = temp.next;
if (temp.next !== null) {
temp.next.prev = newHead;
}
temp.next = newHead;
newHead.prev = temp;
return head;
}
}
There are a few issues here:
The for loop does not make enough iterations to meet the definition of pos. For instance, if pos is 1, then the loop should make one iteration so that temp references the second node (at index 1).
The if statement after the loop checks the value of pos as if it had changed in the loop, but obviously it didn't. Moreover, this means that if pos is less than 2, and temp happens to be null, you'll run into an error when accessing temp.next. This if condition should not check the value of pos.
There is no provision for inserting a node in front of the list so that it becomes the first node. With the interpretation of pos you would have to pass a value of -1 to insert a new node in front of the list, but your code has no provision for this case.
There is an inconsistency in behaviour when the list is empty and when it is not. When it is empty, your code does not validate the pos argument, but when the list is not empty, and the value for pos is too great, your function does not (intend to) append the new node. This is not consistent. You should also make this check when the list is empty, i.e. when you're inserting the very first node. Given the above observations, pos should have the value -1 when you want to insert the first node.
Here is the code with corrections for the above listed points:
addNode(head, pos, data) {
const newHead = { data: data, prev: null, next: null };
if (pos == -1) { // Insert at start
newHead.next = head;
if (head) {
head.prev = newHead;
}
return newHead;
}
if (!head) { // Invalid value for pos argument
return head;
}
let temp = head;
// Number of iterations corrected
for (let i = 0; i < pos && temp.next; i++) {
temp = temp.next;
}
// Check only temp
if (!temp) { // Invalid value for pos argument
return head;
}
newHead.next = temp.next;
if (temp.next) {
temp.next.prev = newHead;
}
temp.next = newHead;
newHead.prev = temp;
return head;
}
Final remark: this is an uncommon way of specifying pos. It would make more sense if pos reflected the index that the new node would have once it was inserted in the list. So then pos should be one more than your specifications currently specify.