[COLLECTIONS-797] An indexed, doubly-linked list data structure running some operations in O(sqrt(n)) time instead of O(n)

• Type: Improvement
• Status: Open
• Priority: Minor
• Resolution: Unresolved
• Component/s: Collection
• Labels: beginner newbie performance
• Assignee: Unassigned
• Reporter: Rodion Efremov
• Created: 19/Aug/21 09:28
• Updated: 14/Jul/22 10:02

Description

(The data structure in question lives in GitHub.)

 

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.