New (?) Data Structure: Array Linked List (for beginners)

Revision en1, by parveen1981, 2021-03-26 10:48:33

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English parveen1981 2021-03-26 10:48:33 1413 Initial revision (published)