[ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Rodion Efremov updated COLLECTIONS-797: --------------------------------------- Attachment: (was: AddAtEnd.png) > An indexed, doubly-linked list data structure running some operations in > O(sqrt(n)) time instead of O(n) > -------------------------------------------------------------------------------------------------------- > > Key: COLLECTIONS-797 > URL: https://issues.apache.org/jira/browse/COLLECTIONS-797 > Project: Commons Collections > Issue Type: Improvement > Components: Collection > Reporter: Rodion Efremov > Priority: Minor > Labels: beginner, newbie, performance > Attachments: AddAtRandom.png > > > (The data structure in question lives in > [GitHub|https://github.com/coderodde/LinkedList].) > > IndexedLinkedList, according to discussion on the mailing list, runs most > operations faster than TreeList, while still having smaller memory > fingerprint: in TreeList, for each element there are 3 references, 2 ints and > 2 booleans. In IndexedLinkedList, for each element there is only 3 > references. (Also, IndexedLinkedList maintains ceil(sqrt(N)) so called > "fingers", each consisting of a reference to a linked list node Node and an > int value being the appearance index of Node.) > > What comes to the implemented interfaces, they are Deque, List, Cloneable and > Serializable. All four are implemented fully in accordance to JDK 18. -- This message was sent by Atlassian Jira (v8.20.10#820010)