---------- Forwarded message --------- From: - <liangchenb...@gmail.com> Date: Wed, Aug 18, 2021 at 11:34 PM Subject: Re: [(Much) faster java.util.LinkedList] To: Rodion Efremov <codero...@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 <codero...@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 >
