GSoC-2011 project:: Containers

[Steven Schveighoffer]

On Wed, 30 Mar 2011 11:27:19 -0400, Daniel Gibson <metalcaedes at gmail.com>  
wrote:

> Am 30.03.2011 16:15, schrieb spir:
>> On 03/30/2011 10:41 AM, Daniel Gibson wrote:
>>> Am 30.03.2011 10:27, schrieb KennyTM~:
>>>> On Mar 30, 11 16:18, Daniel Gibson wrote:
>>>>> Am 30.03.2011 01:55, schrieb Jonathan M Davis:
>>>>>> On 2011-03-29 14:50, dsimcha wrote:
>>>>>>> == Quote from Jonathan M Davis (jmdavisProg at gmx.com)'s article
>>>>>>>
>>>>>>>> The fancier stuff would be nice, but we don't even have a
>>>>>>>> doubly-linked
>>>>>>>> list yet. We should get the simpler stuff sorted out before we get
>>>>>>>> particularly fancy, not to mention that it's usually the simple
>>>>>>>> stuff
>>>>>>>> that gets heavily used.
>>>>>>>
>>>>>>> For the most part I agree, but a doubly linked list might be  
>>>>>>> **too**
>>>>>>> simple. Linked lists are so trivial to implement that I'd tend to
>>>>>>> roll my
>>>>>>> own that does exactly what I need with regard additional behavior  
>>>>>>> on
>>>>>>> insertion, etc. rather than wrapping a library solution to get  
>>>>>>> these
>>>>>>> features.
>>>>>>
>>>>>> A doubly-linked list is on the list of containers that every  
>>>>>> standard
>>>>>> library
>>>>>> should have or it's likely to be considered lacking. I can  
>>>>>> understand
>>>>>> rolling
>>>>>> your own for specific uses, but _I_ sure don't want to be doing that
>>>>>> if I
>>>>>> don't have to. If I want a doubly-linked list, I want to be able to
>>>>>> just
>>>>>> create a standard one and use it. C++, C#, and Java all have
>>>>>> doubly-linked
>>>>>> lists in their standard libraries.
>>>>>>
>>>>>> If no one else ever implements a doubly-linked list for Phobos, I'll
>>>>>> probably
>>>>>> do it eventually simply because it's one of the containers that is  
>>>>>> on
>>>>>> the
>>>>>> short list of containers that pretty much every standard library  
>>>>>> has.
>>>>>>
>>>>>> - Jonathan M Davis
>>>>>
>>>>> It may be feasible to enhance the single-linked list to support both
>>>>> single- and double linking, via an additional template-parameter  
>>>>> "bool
>>>>> doubly" or something like that and some static-ifs in the
>>>>> implementation.
>>>>> I once created a simple single/double-linked queue for D1 like that.
>>>>>
>>>>> Cheers,
>>>>> - Daniel
>>>>
>>>> It is always possible to combine types together with 'static if', but
>>>> the structure and interface is sufficiently different that  
>>>> doubly-linked
>>>> list should better be a separate type.
>>>
>>> Is it? It's just a few additional functions and the functions do some
>>> additional stuff (mostly handling prev-pointers) for double-linked
>>> lists. Much
>>> of the single-linked list code can (probably) be reused - so why
>>> duplicate code?
>>
>> The internal mechanisms are different when one has 2-side pointers
>> available (actually simpler, that's why I guess singly-linked lists are
>> rare outside the cons-based functional realm).
>>
>> Denis
>
> Deleting within the list is different, yes, at least if you want to  
> support something else than "delete next element" - in that case you  
> only have to care about the additional pointers.
> Inserting (at least "insert after this element") is pretty similar,  
> apart from some additional prev-pointers.
> I mostly thought about the other stuff (insert/remove at front/back)  
> because that were my usecases in my single/double linked queue

Insert at back for a singly-linked list is O(n).

-Steve