On Wednesday, 27 June 2012 at 19:06:46 UTC, Timon Gehr wrote:
On 06/27/2012 08:46 PM, Roman D. Boiko wrote:
On Wednesday, 27 June 2012 at 18:26:46 UTC, Steven
Schveighoffer wrote:
The thing that makes SList useless is the O(n) removal.
Nobody will
ever use SList when they can write a replacement that has
O(1) removal
in 10 minutes.
Do you mean something like indexed/sorted dictionary? It
doesn't seem to
be that easy to implement. Or some other data structure with
O(1) removal?
O(1) removal works quite ok for a singly linked list. eg:
1.
- Add a sentinel node to the start of your list.
- Represent an iterator into the list as a pointer to the
predecessor
of the respective node.
- Removal: trivial. rebind the 'next' reference of the
pointed-to node.
2.
- Represent the empty list as a sentinel node with null 'next'
field.
- For removal of a node you own a pointer to:
-- case 1: the successor is an empty list:
- destroy the value, set the 'next' reference to null.
-- case 2: else:
- move the successor's value into the node that holds the
value to
be removed, bind the 'next' reference to the successor of
the
successor.
Nice. But forces to use iterators everywhere.
