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. ---------------------------(end of broadcast)--------------------------- TIP 6: explain analyze is your friend
