Re: LinkedList

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.

> 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.

Regards,

Ben K.
Developer
http://benix.tamu.edu