RandomAccess Interface and List Heirarchy

Peter Levart peter.levart at gmail.com
Sat Sep 28 08:38:43 UTC 2019


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. That brings me to the question: Is it 
possible and how to deprecate only one aspect of a particular 
implementation - in this case the List interface of the LinkedList? In 
this concrete case, and also because it would be strange to have a class 
called LinkedList implementing only Deque interface, it may be an 
alternative to 1st create a replacement in the form of LinkedDeque 
implements Deque, and then deprecating the whole LinkedList.

As always there are pros and cons to a particular "solution":

1. Do nothing
pros:
- no refactoring of old code needed
cons:
- performance problems continue as inexperienced programmers couple 
LinkedList with typical indexed accesses of List interface
- hard discoverability of single-threaded "linked" Deque implementation 
continues - LinkedList is not a name that comes to mind when searching 
for Deque implementation - this is less of a problem nowadays as we have 
tools like Ctrl-H in IDEA, ...

2a. Deprecate the List aspect of LinkedList and eventually remove the 
List interface from the LinkedList
pros:
- performance problems eventually solved
- at least some of the usages of LinkedList would remain valid: Deque<T> 
d = new LinkedList<>();
cons:
- compatibility risk - all uses of LinkedList that assume it implements 
List interface will have to be refactored
- hard discoverability of single-threaded "linked" Deque implementation 
continues - LinkedList is not a name that comes to mind

2b. Deprecate the List aspect of LinkedList with not planned removal of 
the List interface from the LinkedList
pros:
- performance problems eventually solved
- at least some of the usages of LinkedList would remain valid: Deque<T> 
d = new LinkedList<>(); not even warnings suppression would be needed
- no immediate compatibility risk - only suppressing warnings may be 
needed in short term
cons:
- hard discoverability of single-threaded "linked" Deque implementation 
continues - LinkedList is not a name that comes to mind

3. Create a replacement LinkedDeque implementation of Deque and 
deprecate LinkedList (with no planned removal)
pros:
- performance problems eventually solved as new code typically would 
refrain from using LinkedList for the List purpose and would start using 
LinkedDeque for the Deque purpose
- no refactoring of old code needed (at least not in the near future)
- better discoverability of single-threaded "linked" Deque implementation
cons:
- new type to learn
- code using new type would not compile/run on old JDKs - adoption rate 
of new type would be slow


2b is most promising IMO. But is there an effective way to deprecate the 
List aspect of the LinkedList? What would be needed is a particular use 
of @Deprecated annotation that would cause usages like this:

     List<T> l = new LinkedList<>();

produce compile-time deprecation warnings, but usages like this:

    Deque<T> d = new LinkedList<>();

not produce warnings.

The 1st thing that comes to mind is adding a TYPE_USE to the list of 
@Target(s) of the @Deprecated annotation and then using it like this:

public class LinkedList<E>
     extends AbstractSequentialList<E>
     implements @Deprecated List<E>, Deque<E>, Cloneable, 
java.io.Serializable


Would this make sense?


Regards, Peter




More information about the core-libs-dev mailing list