Re: LinkedList

On Sat, 2006-29-04 at 01:50 -0500, Ben K. wrote:
> On Fri, 28 Apr 2006, Guy Fraser wrote:
>
> >> -- HEAD
> >> insert into linkedlist values(null,1,0);
> >> insert into linkedlist values(1,2,10);
> >> insert into linkedlist values(2,3,20);
> >> insert into linkedlist values(3,4,30);
> >> insert into linkedlist values(4,5,40);
> >> -- TAIL
> >> insert into linkedlist values(5,null,50);
>
>
>
> > Bad example of a double linked list, you also need an id for
> > the current node and the values of prevnode and nextnode do not
> > need to be ordered or contiguous as the example shows.
>
>
>
> Wow. Interesting... I am willing to be corrected, but to me the "node"
> field seems redundant, since it does not add any information. (Since each
> item in the list is already uniquely identifiable without the "node".)
> Certainly so, for traversing, which was the OP's intention.
>
> It may save some steps in case of other operations but at the expense of
> one more field. Please see below.
>

The problem is that your way, there is no indicated way to determine
which node is which. For instance is you update any of your nodes
then the node list would be out of order and your list would not
work.

After I posted the message I realized there is another way to
do this without adding an extra field, and it would be a closer
example to how it is done in C. If you assigned the OID of the
previous and next nodes rather than arbitrary integer, you could
access each node independent of the order they are listed.

I have not messed around much with OIDs. I am not sure if
OIDs change if an entry is updated.

In C you would use a pointer to storage location of previous
and next "node" which is similar to using the OID. In some
cases it can be necessary to use pointers to pointers when
accessing variable length relocatable data, but that goes way
past what this thread is about.

The example I provided, is still feasible and alleviates all
unknowns at the expense of 4 bytes of storage for one integer
used as a fixed address for each node.

>
>
> > create table linkedlist(node int,prevnode int, nextnode int, val int);
> > insert into linkedlist values(1,null,2,0);
> > insert into linkedlist values(2,1,3,10);
> > insert into linkedlist values(3,2,4,30);
> > insert into linkedlist values(4,3,5,20);
> > insert into linkedlist values(5,4,6,40);
> > insert into linkedlist values(6,5,null,50);
>
> > If we now wanted to reorder an item in the set you need
> > make some updates in a block, which I have not done before
> > but should be something like this:
> >
> > Move node 4 between 2 and 3 so that the values from head
> > to tail are ordered.
> >
> > update linkedlist set prevnode = '2',nextnode = '3' where node = '4';
> > update linkedlist set nextnode = '4' where node = '2';
> > update linkedlist set prevnode = '4' where node = '3';
>
>
>
> If the intention is to change it from 0-10-30-20-40-50 to
> 0-10-20-30-40-50, it would have been (in my design) exchanging node 3 and
> node 4 below.
>
> null,1,0
> 1,2,10 <-- node 2
> 2,3,30 <-- node 3
> 3,4,20 <-- node 4
> 4,5,40
> 5,null,50
>
> Now, it can be done by:
>
> begin;
> update linkedlist set prevnode=2 where prevnode=3; -- node 4 = (2,4,20)
> update linkedlist set prevnode=3 where nextnode=3; -- node 3 = (3,3,30)
> update linkedlist set nextnode=3 where prevnode=2; -- node 4 = (2,3,20)
> update linkedlist set nextnode=4 where nextnode=3; -- node 3 = (3,4,30)
> commit;
>
> achieving the same.
> ...
> 2,3,20 <-- node 4, originally
> 3,4,30 <-- node 3, originally
> ...
>
> "node" will be more cost efficient if we insert an item at the beginning
> of a long list, for example insert
> (2,3,100)
> before node 3 (2,3,20), but at least the sql is simple;
>
> update linkedlist set prevnode = prevnode + 1 where prevnode > 1;
> update linkedlist set nextnode = nextnode + 1 where nextnode > 2;
> and then do insert (2,3,xxx)
>
> This method can also be used for reordering.
>
> The usefulness of the "node" will depend on the economics of these update
> operations over keeping one more field.
>
> But I think this is more of an exercise, and functions would be the proper
> way for complex operations.
>

As long as it works in real world use. Without some way of addressing
each node, the idea of a linked list seems wrong, since a linked is
supposed to hold the address of the previous and or next item in the
list, assuming the data is always going to be correctly sorted so that
you can locate the next item by tupple number seems overly assumptive.
If it works for you great, your example may then be useful as a short
cut, but I don't believe in leaving things to chance when programming.