RandomAccess Interface and List Heirarchy

Cyrus Vafadari cvafadari at gmail.com
Mon Nov 11 21:08:07 UTC 2019


Thanks for the thoughtful responses.

I think my issue with Runtime annotation is that it's just that -- Runtime.
Compiletime is highly preferable.

I also understand the challenges listed by Peter, and the original intended
use of RandomAccess as explained by Remi.

I'd like to propose another solution: A new interface that will be similar
to "RandomAccess", and be properly in the hierarchy, very similar to
RandomAccess but actually inheriting from List. This way, there is no new
syntax, no deprecation issues.
Users could then (at compile time), require that a function is passed an
"IndexableList" (or whatever it ends up being called). Remi points to an
issue where every implementer of list will need to declare its type (e.g.
"RandomImmutableList"), but I'm not sure I'm convinced by this argument:
Guava's ImmutableList, for example, already implements RandomAccess! For
Collections' UnmofidfiableList, of course, just returns a view of the
generic list it's used with, so there's no issue here. Maybe I
misunderstood, but I'm not sure the fanout of interface/class permutations
is not really an issue.

Thoughts?

On Mon, Sep 30, 2019 at 5:41 AM David Lloyd <david.lloyd at redhat.com> wrote:

> On Sat, Sep 28, 2019 at 3:39 AM Peter Levart <peter.levart at gmail.com>
> wrote:
> >
> > On 9/25/19 12:15 PM, Remi Forax wrote:
> > > that said, i believe we should deprecate LinkedList (and any other
> List implementation that doesn't implement RandomAccess) because there are
> too much code out there that suppose that list.get() is O(1).
> >
> > Hi Remi,
> >
> > Deprecating LinkedList as a whole is maybe to harsh. LinkedList is a
> > List, but it is also the only JDK implementation of single-threaded
> > linked Deque, which, although a retrofitted feature, is a perfectly
> > fitted feature of LinkedList.
>
> Surely ArrayDeque is almost universally superior to LinkedList for
> this use, in the same way that ArrayList has been shown to be almost
> universally superior to LinkedList for list use cases?
>
> See also
> https://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist-in-java
>
> The salient point being that in most cases the O(1) of LinkedList is
> effectively slower than the O(n) of Array*.
>
> --
> - DML
>
>


More information about the core-libs-dev mailing list