Doubly-linked list/Definition: Difference between revisions

So, first, here is a native J list:

 

 

To implement a doubly linked list, one could create a list of successor indices and another list of predecessor indices.

 

First, let us define a different order for our list element, so we can easily show that our doubly linked list is logically distinct from the built in list. If we use "alphabeted order by names of numbers" we would have the list 11 5 7 3 2

 

3 is followed by 2

To represent this in J, we can define additional lists with the successor index and predecessor index for each node:

 

 

Note that the successor for the end of the list is _ and the successor for the beginning of the list is __

Finally, note that we can remove elements from the doubly linked list without removing them from the data list. We might wish to chain removed elements together to facilitate re-use of their positions. If we want to do this, we will need a place to start:

 

 

When we delete an item we place the old garbage value as its successor index and we define the garbage variable to be the index we just deleted. And when adding to the list we first check if garbage has a valid index and if so we take over that position in the structure and update garbage with the previous value of the successor.

 

 

=={{header|JavaScript}}==