<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<p>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.</p>
<p>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).</p>
<p>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).<br>
</p>
<p>--John<br>
</p>
On 09/07/2022 21:33, Tagir Valeev wrote:<br>
<blockquote type="cite"
cite="mid:CAE+3fjYgWPT9cZZCCYUN-hHu_s1=8C85zQahbF+07VFCh-gfig@mail.gmail.com">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<div dir="auto">
<div>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.</div>
<div dir="auto"><br>
</div>
<div dir="auto">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:</div>
<div dir="auto"><a
href="https://bugs.openjdk.org/browse/JDK-8143850"
target="_blank" rel="noreferrer" moz-do-not-send="true"
class="moz-txt-link-freetext">https://bugs.openjdk.org/browse/JDK-8143850</a><br>
</div>
<div dir="auto"><br>
</div>
<div dir="auto">There were also discussions to enhance
collections in general, adding more useful methods like
getFirst() or removeLast() to ArrayList, etc. See for details:</div>
<div dir="auto"><a
href="https://bugs.openjdk.org/browse/JDK-8266572"
moz-do-not-send="true" class="moz-txt-link-freetext">https://bugs.openjdk.org/browse/JDK-8266572</a><br>
</div>
<div dir="auto"><br>
</div>
<div dir="auto">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.</div>
<div dir="auto"><br>
</div>
<div dir="auto">With best regards,</div>
<div dir="auto">Tagir Valeev<br>
<br>
<div class="gmail_quote" dir="auto">
<div dir="ltr" class="gmail_attr">Ñб, 9 июл. 2022 г., 11:22
Rodion Efremov <<a href="mailto:coderodd3@gmail.com"
target="_blank" rel="noreferrer" moz-do-not-send="true"
class="moz-txt-link-freetext">coderodd3@gmail.com</a>>:<br>
</div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr">Hello,
<div><br>
</div>
<div>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.</div>
<div><br>
</div>
<div>Best regards,</div>
<div>rodde</div>
</div>
<div dir="ltr"><br>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Sat, Jul 9, 2022 at
11:19 AM Tagir Valeev <<a
href="mailto:amaembo@gmail.com" rel="noreferrer
noreferrer" target="_blank" moz-do-not-send="true"
class="moz-txt-link-freetext">amaembo@gmail.com</a>>
wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px
0px 0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">
<div dir="auto">Hello!
<div dir="auto"><br>
</div>
<div dir="auto">Are there real world problems/use
cases where IndexedLinkedList would be preferred
in terms of CPU/memory usage over ArrayList? </div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">Ñб, 9 июл. 2022
г., 07:18 Rodion Efremov <<a
href="mailto:coderodd3@gmail.com"
rel="noreferrer noreferrer" target="_blank"
moz-do-not-send="true"
class="moz-txt-link-freetext">coderodd3@gmail.com</a>>:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px
0px 0px 0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">Data structure
repo:Â
<div><a
href="https://github.com/coderodde/IndexedLinkedList"
rel="noreferrer noreferrer noreferrer"
target="_blank" moz-do-not-send="true"
class="moz-txt-link-freetext">https://github.com/coderodde/IndexedLinkedList</a></div>
<div dir="auto"><br>
</div>
Benchmark repo:Â
<div dir="auto"><a
href="https://github.com/coderodde/IndexedLinkedListBenchmark"
rel="noreferrer noreferrer noreferrer"
target="_blank" moz-do-not-send="true"
class="moz-txt-link-freetext">https://github.com/coderodde/IndexedLinkedListBenchmark</a></div>
<div><br>
</div>
<div dir="auto">I have profiled my data structure
and it seems it’s more performant than
java.util.LinkedList or TreeList, if nothing
else.</div>
<div dir="auto"><br>
</div>
<div dir="auto">So, is there any chance of
including IndexedLinkedList to JDK?</div>
<div dir="auto"><br>
</div>
<div dir="auto">Best regards,</div>
<div dir="auto">rodde</div>
</blockquote>
</div>
</blockquote>
</div>
</blockquote>
</div>
</div>
</div>
</blockquote>
</body>
</html>