Fwd: [(Much) faster java.util.LinkedList]

[-]

---------- Forwarded message ---------
From: - <liangchenblue at gmail.com>
Date: Wed, Aug 18, 2021 at 11:34 PM
Subject: Re: [(Much) faster java.util.LinkedList]
To: Rodion Efremov <coderodd3 at gmail.com>


The main drawback is that this linked list now runs at O(sqrt(N)) than O(1)
time complexity for single-element head/tail modifications, which is
probably the main usage of linked lists.

LinkedList is probably deemed legacy now; in
https://bugs.openjdk.java.net/browse/JDK-8263561 (
https://github.com/openjdk/jdk/pull/4304), existing LinkedList usages have
been either replaced by ArrayList or ArrayDeque dependent on its type as
deque or list. Does this implementation excel either as a list or a deque?

Best

On Wed, Aug 18, 2021 at 10:30 PM Rodion Efremov <coderodd3 at gmail.com> wrote:

> Hello,
>
> I have implemented a heuristic, indexed doubly-linked list data structure
> [1][2] implementing java.util.List and java.util.Deque interfaces that has
> superior performance compared to java.util.LinkedList and
> java.util.ArrayList.
>
> I would like to propose it into the upcoming versions of OpenJDK, but,
> first, I need to know what do you think about it?
>
> Best regards,
> rodde
>
> [1] https://github.com/coderodde/LinkedList
> [2] http://coderodde.github.io/weblog/#eill
>