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.
