RandomAccess Interface and List Heirarchy

David Lloyd david.lloyd at redhat.com
Mon Sep 30 12:41:17 UTC 2019

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*.


More information about the core-libs-dev mailing list