Re: PATCH: More collections List updates

[Stuart Ballard]

Bryce McKinlay wrote:
> 
> I have rewritten most of LinkedList. The new implementation is simpler,
> faster and conforms to the spec more closely.

As the original author of LinkedList - thanks! I think I was trying to
be too clever with my original code, resulting in an obfuscated mess.
Thanks for cleaning up after me :)

However, there is one feature of my implementation which I would like to
see preserved: In a naive implementation (including yours, and also
Sun's), every call to listIterator(i) on the result of
subList(fromIndex, toIndex) is O(fromIndex + i), because it goes through
AbstractList.SubList.listIterator(fromIndex). My implementation included
an override of LinkedList.subList() to store a pointer to the Entry
objects of the first-1 and last+1 nodes. Thus listIterator(i) on the
subList is only O(i). 

You can tell that Sun does not make this optimization because the
JavaDocs for LinkedList (as of 1.3) show the subList() method as being
inherited from AbstractList.

One way to implement this would be to make LinkedList.subList() itself
return a LinkedList (and set its first and last pointers accordingly).
In order to get the correct ConcurrentModification behavior, you may
need to make this a *subclass* of LinkedList, including the appropriate
modifications to modCount.

Now, obviously since Sun has this flaw in their implementation, I'm not
sure that we *need* to do this, but it does seem to me that we should
take every opportunity to be better than Sun's implementation where we
can.

> While working on this I
> realised the flaw in my previous change (removal of) the SubList
> iterator in AbstractList: Although correct, it resulted in poor
> performance for iterators on sublists of linked lists, as the iterator
> would ultimately traverse the linked list via its get() method,
> requiring quadratic-ish time. The fix was to restore the existing
> iterator wrapper approach. A few other minor bugs are also fixed by this
> patch.

Yes, this is the reason behind the original implementation (and it
applies even if you make the change above, because there could be other
"sequential" lists than LinkedList).

FWIW, I noticed recently that you changed AbstractList.iterator() to
simply return this.listIterator(). I agree with this change, but it's
worth mentioning that (at least as of the late betas of JDK1.2) Sun did
not agree with it, because I sent that very question to Sun before I
made the original implementation. With 2 years of hindsight, I don't
think I agree with their answer (which amounted to "users might assume
it's a ListIterator and cast to it, which would sort of be a security
hole because then they could do things they can't do with a regular
iterator" - I'll see whether I can dig up the message from the Sun guy)
but it is at least worth noting.

Stuart.