I think there might be room for another List implementation in the JDK,
one that fits in between ArrayList and LinkedHashMap. I've been looking
for something to manage lists of listeners (which allow arbitrary
removal), must be called in order, and should handle duplicates (at
their respective positions). Both ArrayList and LinkedHashMap are
close. LinkedHashMap has quite some overhead (Entry instance per
element) and poor cache locality while iterating and doesn't allow
duplicates. ArrayList has poor remove performance.
It should offer O(1) performance for add(Last), contains, remove(T) and
near O(1) performance for operations that operate near the head/tail of
the list (like getFirst, getLast, removeFirst, removeLast). Iteration
performance would be similar to ArrayList. Basically an ArrayDeque, but
with fast contains/remove(T). The sacrifice made is poor index based
access (with the exception of the head/tail).
It should be useful as a queue as well that allows quick removal (in
order to cancel tasks for example, or to move a task up/down the queue).
--John
On 09/07/2022 21:33, Tagir Valeev wrote:
Note that nobody these days cares about LinkedList. Use-cases where
LinkedList outperforms careful use of ArrayList or ArrayDeque are next
to none. So saying that your data structure is better than LinkedList
is totally not a reason to add it to JDK. It should be better than
ArrayList and ArrayDeque.
Having a single data structure that provides list and deque interface
is a reasonable idea. However it would be much simpler to retrofit
existing data structure like ArrayDeque, rather than create a new data
structure. Here's an issue for this:
https://bugs.openjdk.org/browse/JDK-8143850
There were also discussions to enhance collections in general, adding
more useful methods like getFirst() or removeLast() to ArrayList, etc.
See for details:
https://bugs.openjdk.org/browse/JDK-8266572
To conclude, the idea of adding one more collection implementation
looks questionable to me. It will add more confusion when people need
to select which collection fits their needs better. It will require
more learning. This could be justified if there are clear benefits in
using it in real world problems, compared to existing collections. But
so far I don't see the examples of such problems.
With best regards,
Tagir Valeev
сб, 9 июл. 2022 г., 11:22 Rodion Efremov <codero...@gmail.com>:
Hello,
My benchmarking suggests, that, if nothing else, my
IndexedLinkedList outperforms gracefully the java.util.LinkedList,
so the use case should be the same (List<E> + Deque<E>
-interfaces) for both of the aforementioned data structures.
Best regards,
rodde
On Sat, Jul 9, 2022 at 11:19 AM Tagir Valeev <amae...@gmail.com>
wrote:
Hello!
Are there real world problems/use cases where
IndexedLinkedList would be preferred in terms of CPU/memory
usage over ArrayList?
сб, 9 июл. 2022 г., 07:18 Rodion Efremov <codero...@gmail.com>:
Data structure repo:
https://github.com/coderodde/IndexedLinkedList
Benchmark repo:
https://github.com/coderodde/IndexedLinkedListBenchmark
I have profiled my data structure and it seems it’s more
performant than java.util.LinkedList or TreeList, if
nothing else.
So, is there any chance of including IndexedLinkedList to JDK?
Best regards,
rodde
