I think that LinkedList should be a private class nobody should use :).
Better use DoubleLinkedList which should be packaged with extended
collection.
Le 14/4/15 17:07, Henrik Johansen a écrit :
On 14 Apr 2015, at 2:09 , Marcus Denker <marcus.den...@inria.fr> wrote:
On 14 Apr 2015, at 14:00, Sven Van Caekenberghe <s...@stfx.eu> wrote:
Peter,
On 14 Apr 2015, at 13:52, Peter Uhnák <i.uh...@gmail.com> wrote:
I was surprised to learn that DoubleLinkedList is descendant of Object, while
LinkedList is descendant of SequencableCollection. Is there a particular reason
behind this? Are they really so conceptually different that DLL is not even
considered a collection?
Thanks,
Peter
DoubleLinkedList was added to help the implementation of [LRU|TTL]Cache. It was
kept small and independent.
Inheriting from [Sequenceable]Collection is a larger responsibility, entails
more requirements.
I would not be against this, although I am not 100% sure it is easy (some
methods return the link nodes, not the elements, a distinction unknown to
collections in general - LinkedList is a bit ugly in this respect too). In any
case, it would have to be supported by enough tests. It could be a nice project
for Pharo 5.
One problem with LinkedList is that it is used by the scheduler and carefully
written to be intererrupt-check free in some (undocumented) cases… in the past
this has already lead to very bad side-effects when people wanted to improve it
or change it.
Marcus
IIRC, #removeLink:ifAbsent: is the only method (... that we've noticed) that
needs to be atomic for the scheduler to work.(in other words, it can end up
trying to remove the same process from different threads at the same time)
The change was made during a sprint to allow adding arbitrary objects and
create links on the fly (inspired by Ruby, or so I was told), in the process
the old remove:ifAbsent: turned into removeLink:ifAbsent, and a suspension
point was introduced in the process, which meant, once in a blue moon, the
scheduler would get stuck trying to remove a process that had already been
removed.
In other words; it's not a pleasant class to change.
WRT being a subclass of SequenceableCollection; while technically true, that
API is much wider than what you'd expect from a classic link list, and the
inherited implementations mostly assume O(1) #at: performance. Very little is
reimplemented, so most of it is rather slow if you try to actually use any of
it:
ll := LinkedList withAll:#(a b c d e f g h i j k l m n o p q r s t u v x y z).
[ll allButFirst: 15] bench '150,365 per second'
aa := Array withAll: #(a b c d e f g h i j k l m n o p q r s t u v x y z).
[aa allButFirst: 15] bench 10,055,029 per second
Aside from pure bugs, there's also other oddities like the species being Array,
but iteration methods reimplemented using self class.
IOW: If you are looking for a LinkedList actually worth using, look elsewhere.
DoubleLinkedList may not be a Collection, but at least the API is small enough
to grasp, and the parts that are there act as you expect them to.
Cheers,
Henry
