Блог пользователя parveen1981

Автор parveen1981, история, 3 года назад, По-английски

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.

code
  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Isn't it the normal way to use Linked List?

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

So... a doubly linked list?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    yes, but with $$$O(1)$$$ remove operation.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится

      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

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.