Baseline Linked List · Doubly Linked List O(n) · O(1)
A facility adds a new checkpoint to a two-way corridor. The placement rule is relative: the checkpoint must slot in immediately after the p-th one (0-based). Because the corridor is two-way, the crew must wire four links — the newcomer's forward and backward registers, plus updated registers on both of its new neighbours — or patrols will deadlock.
Input: An array arr of node values, a 0-based position p, and an integer x.
Output: The list after inserting x immediately after the p-th node.
1 <= arr.length <= 10^50 <= p < arr.length-10^9 <= arr[i], x <= 10^9Input: {"arr":[2,4,5],"p":2,"x":6}
Output: [2,4,5,6]
Position 2 is the tail, so the newcomer becomes the new tail with only a backward link to wire.
Input: {"arr":[1,2,3,4],"p":0,"x":44}
Output: [1,44,2,3,4]
Inserting after the head rewires both the head's forward link and the old second node's backward link.