parveen1981's blog

By parveen1981, history, 4 years ago, In English

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
  • Vote: I like it
  • +3
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes, funny... I just used it for arrays.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Linked lists don’t normally have constant access.

»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

So... a doubly linked list?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      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

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.