Remove element from DList

[Russel Winder]

On Sat, 2012-10-06 at 19:42 -0700, Jonathan M Davis wrote:
[…]
> singly-linked lists and doubly-linked lists are completely different beasts. A 
> singly-linked list can't do it sanely, because it has to traverse the list to 
> find the previous node so that it adjust the links. A node in a doubly-linked

Not sure about the D implementation, but in other languages all the
singly-linked list iterator has to do to allow for removal is to
maintain a "front foot"/"back foot" state. This is needed for insert as
well, so it is already there.

> list has a link to the previous node in the list instead of just the next 
> node, so it doesn't have that problem. You can add and remove elements from 
> anywhere in a doubly-linked list in O(1). And if you're dealing with 
> iterators, it won't affect any iterators except if they point at the element 
> being removed (so it's a stable remove). With ranges, it would affect the 
> elements in the range, but unless you're removing an element which is at the 
> front or end of a range, it shouldn't invalidate the range at all. And that 
> can be gotten around by letting that node continue to exist and point to what 
> was the next node in the list (in which case, it would go away once no more 
> ranges referred to it - the GC makes doing that fairly easy).

Removal from a singly-linked list can be O(1) as well, it depends
whether you are deleting using an iterator in progress.

> So, I don't see any reason why remove wouldn't be stable or non-linear. It's 
> actually kind of hard to make it _un_stable in this case. And actually, 
> looking at the code, stableLinearRemove (and linearRemove is an alias for 
> stableLinearRemove in this case) calls remove, so overall, this is a bit 
> bizarre. Regardless, it's a bug that normal remove doesn't work with the 
> result of take.
> 
> - Jonathan M Davis

-- 
Russel.
=============================================================================
Dr Russel Winder      t: +44 20 7585 2200   voip: sip:russel.winder at ekiga.net
41 Buckmaster Road    m: +44 7770 465 077   xmpp: russel at winder.org.uk
London SW11 1EN, UK   w: www.russel.org.uk  skype: russel_winder
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part
URL: <http://lists.puremagic.com/pipermail/digitalmars-d-learn/attachments/20121007/09fb6ac0/attachment.pgp>