Am 30.03.2011 17:31, schrieb Steven Schveighoffer:
On Wed, 30 Mar 2011 11:27:19 -0400, Daniel Gibson
<[email protected]> 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 ([email protected])'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
