Hi guys,
I was solving this problem and I came up with somewhat wrong solution. Although my solution was wrong but I came up with new data structure. I don't know if you know this but here it is.
At first, I want to describe what I wanted to do and for what:
1. We are given a linked list in which nodes are numbered from $$$1$$$ to $$$n$$$ and they are all connected ( 1-2-3-4-...-n).
2. I wanted to remove some nodes whenever I want in $$$O(1)$$$.
So we can maintain two arrays here: $$$next$$$ and $$$prev$$$. $$$next[i]$$$ will tell us the next node which $$$i$$$ is connected to and $$$prev[i]$$$ will tell us the previous node which $$$i$$$ is connected to.
So, initially we will have $$$next[i]=i+1$$$ and $$$prev[i]=i-1$$$
Now, to remove some node, we can do the following:
$$$next[prev[i]]=next[i]$$$
$$$prev[next[i]]=prev[i]$$$
So this is the basic remove operation and you can customize it however you like.
Isn't it the normal way to use Linked List?
yes, funny... I just used it for arrays.
Linked lists don’t normally have constant access.
So... a doubly linked list?
yes, but with $$$O(1)$$$ remove operation.
Linked lists also have O(1) remove if you have a reference to the node you want to remove. So this is equivalent to a normal doubly linked list where you initially keep an array of references for each node
I have also done this 2-3 times earlier, you can see 110422403, here i made pre and suff array to store the next and previous element, now to remove an element i just change values in pre and suff array.