How does it compare to a simple array or ArrayList? Given modern CPU architecture and caching, I rarely encounter real world use cases where a linked list outperforms an array list, no matter what the data structures textbooks say. Maybe on very large lists with a lot of mutations, though last I checked the size where this came into play was 100K elements and growing. Maybe your algorithm is faster. I don't know.
https://www.reddit.com/r/learnprogramming/comments/10hwrmy/why_arent_linked_lists_more_popular/ On Tue, Apr 9, 2024 at 9:01 AM Rodion Efremov <codero...@gmail.com> wrote: > > Good day, > > I would like to propose a Deque/List that is implemented as a doubly linked > list with a sublinear index speeding up single-element operations to > (likely) O(sqrt(n)). It passes a benchmark faster than TreeList by the > factor of around 5. > > The data structure is hosted in GitHub: > https://github.com/coderodde/IndexedLinkedList > > Does it have potential to be included in Collections? > > Best regards, > rodde -- Elliotte Rusty Harold elh...@ibiblio.org --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
