GSoC-2011 project:: Containers

[Daniel Gibson]

Am 30.03.2011 17:31, schrieb 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

Not if you keep a pointer to the last element.
Then it's just  last.next = newElem; last = newElem; or similar.
But deleting the last element is O(n) (So I only supported that for the 
doubly-linked queue).

Cheers,
- Daniel