[A linked list data structure running some operations in O(sqrt(n)) time instead of O(n)]

[Rodion Efremov]

Hello,

I was kindly directed to this mailing list in order to discuss this data
structure:

https://github.com/coderodde/LinkedList

The README of that repository contains a table of running times for
different methods and different List implementations (ArrayList,
LinkedList, my version of the LinkedList).

Basically, if all we want to do is to add/remove from the head/tail of a
List, my implementation won't provide any performance gain. However, in
case we want to work on the List in a versatile way (many add(int),
addFirst/addLast, get(int), remove(int), removeFirst, removeLast,
addAll(int, coll)) my version beats that of java.util package by a factor
of 35 in a benchmark I wrote.

I understand that ArrayList/LinkedList have a status of legacy code in JDK,
but how about including my work with a different name (perhaps, FingerList
or something like IndexedList/IndexedLinkedList)?

Now, I would like to discuss my work with you. Did I write mature JDK code?
Or, can it make it to the JDK in the first place?

Best regards,
rodde