Re: Generic Embedded List Nodes

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

On 20/06/2016 04:42, Warren wrote:
> On Sunday, 19 June 2016 16:35:32 UTC-4, Dmitry A. Kazakov  wrote:
>> No, doubly-linked list deletion is O(1).
>
> Ok you're tracking the link in Element, which is fine. However, your
> Element also needs a reference to the separately allocated object (which
> is a problem for me). This requires two allocations instead of one.

No, that is the point. The object and the element (links) are in one 
continuous chunk of memory. I believe this is what you meant under being 
"embedded" nodes.

When an object is allocated, element + object is instead and the address 
to the object's part is returned back from Allocate. Deallocate takes 
the object's address, subtracts the offset and deallocates the whole chunk.

> I only need to insert head, traversal and delete. That's it!

Yes, and the schema above is as effective as it can be.

>>> In the embedded node case, I already have direct access to the
>>> affected link node. To remove the node from a list I simply say:
>>>
>>>     R.Link_Node.Unlink;
>>
>> The operation Delete has the list head parameter (Container) not for
>> traversing the list, but for modifying the list head if the first
>> element is deleted from the list.
>
>> If you don't have it, you must maintain a dedicated list head element
>> with no object attached. That is a less safe and clean because it
>> ultimately leads to run-time type checks in the client code.
>
> I agree with the dedicated list head statement, but not the "less
> safe" part. You either have container or you have a list head (each
> represents one list, though yours potentially several).
>
> There is nothing to check about a list head- you simply begin there.
> If you have no "head.next", you have an empty list.

Not with doubly-linked lists. There is always Next, because the list is 
circular. When you delete an element from the list you always get two 
lists. Deletion of a single element is an idempotent operation unless 
you have a dedicated head or else have the list head pointer corrected.

List traversal when the list head is a pointer is performed like this:

    if Head /= null then
       This := Head;
       loop
          ... -- Do something
          This := This.Next;
          exit when This = Head;
       end loop;
    end if;

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de