Ed,

>True - containership is only an issue if you want to contain the namespace of the objects within the list class, rather than burdening the VFP session name table, or if you wish to do things like AddObject() at runtime (and you can even dodge this using AddProperty() and slightly different syntax.)

I'd have to do some more refined digging into the VFP internals, but these objects are all nameless except for the head of the list. There is no way to get to these objects except by traversing the list from the head.

I wouldn't do this with containership, although that would give you a DouleLinkedList for free via the .Parent reference.

>>

define class SingleLinkedList as Relation
>>oNext = .null.
>>enddefine

>Absolutely; very elegant, and easy enough to add a search by overloading equivalence of the node in the node definition and walking through the list in LIFO fashion until oNext is null. One question arises, and that has to do with the deletion of an intermediate node of the SLL; you set the parent's oNext to the Object's oNext, but at what point do we assign the Object's oNext to NULL;

ref the above code fragment, oNext is always initialized to .null. when the node is first created. Given that you have traversed to the node you want to delete (loNode), and you've kept an loPrior pointer:

loPrior.oNext = loNode.oNext && delink loNode out of the list
loNode = .null. && destroy it

>if we don't do this in the right order, we face a difficult problem, in that when we set the parent node's oNext to the current oNext, the sole object reference to the current node is lost, which should destroy the current object, but since the object contains a reference to a live object, Release will fail, and we end up with dangling object refs, correct? I'd guess that assigning a local to 'this' prior to reassignment of the parent gets around the problem and nulling oNext before releasing the local would cure this, but I'm not sure of this. I'll play around with it over the weekend.

Surely what I posted is far from a complete set of methods the SLL needs. And you right if you are not careful you could wipeout the entire rest of the list, during insert or delete operations.

>Agreed - weak data typing gives a clear edge to VFP in this situation. This does move some of the traversal logic into the node class, for example, the concept of equivalence and 'between-ness' must be resolved by a call to the node, since it'd be difficult to inherit the comparator at the class level - you'd need to ask the Node if it satisfies the comparator condition.

Here is where VFP could really benefit from inheritance of interface. We could define iSLL and require that every subclass of SLL also implement iSLL. This would at least ease the task of knowing what needed to be done. But again there is not too much difference between VFP and C# from Nancy's example there is a whole plethora of methods that her subclass needed to implement.

>I'd guess that traversal degrades exponentially as the length increases moving from tail to head because of object resolution; have you benchmarked this? Again, this would only be an issue with a large number of nodes.

I should have also caveated the "adequate performance" statement with yes C++ would have done the same thing probably one or two orders of magnitude faster.

Traversal of linked lists is always O(n²) no matter what language is used, that's why better things like trees were developed. Since VFP is a pcode based interpreter it will get annoyingly slow much sooner than C++ would.

One thing that can be problematic is destruction. One would look at the class and say he's not properly cleaning up with:

function Destroy
this.oNext = .null.
endfunc

Well this fails horribly with a nesting error if there are more than 128 nodes in the list. This can be overcome and actually sped up by using a loop, storing the oNext pointer into a temp array, nulling the oNext through the entire list and then iterate the array nulling the value so the node will really be free to destruct without recursing calls to Destroy().