Remove element from DList

Steven Schveighoffer schveiguy at yahoo.com
Tue Oct 9 07:29:46 PDT 2012


On Sun, 07 Oct 2012 05:15:05 -0400, Jonathan M Davis <jmdavisProg at gmx.com>  
wrote:

> On Sunday, October 07, 2012 10:09:06 Russel Winder wrote:
>> Removal from a singly-linked list can be O(1) as well, it depends
>> whether you are deleting using an iterator in progress.
>
> IIRC that dcollections' singly-linked list is like this

dcollections does not have singly-linked lists.

> , but
> std.container.SList definitely isn't. I'm not a big fan of singly-linked  
> lists
> in the first place and tend to think that they're useless, but  
> std.container's
> is particularly bad in that regard.

They are definitely not useless.  But IMO, they are difficult to write in  
a generic way.  Typically they are very tightly coupled to whatever it is  
you need them for.  If you are using singly linked lists, it's because  
doubly-linked lists are too bloated, or cannot implement what you are  
trying to do, so there is already a necessary optimization based on your  
particular situation that is difficult to provide as a generic container.

But I agree a singly linked list is near useless without O(1) removal.  I  
think that there has been some improvement in SList in that regard  
though...

-Steve


More information about the Digitalmars-d-learn mailing list