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

["Rodion Efremov (Jira)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Rodion Efremov updated COLLECTIONS-797:
---------------------------------------
    Description: 
(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.

  was:
The data structure in question lives in [GitHub|https://github.com/coderodde/LinkedList].

 

The idea is that we maintain sqrt(N/2) so called "fingers" along the actual list. Each finger contains a reference to a list node and an index of that node. Now, when we need to access a node via an index, we don't have to scan through the entire linked list, but, instead, only consult all the finger, choose the closest finger, and iterate from the respective node towards the target node. 

 

If the fingers are distributely evenly, also traversal from the node pointed by a finger to the target node will require O(sqrt(N)) time.

 

While not (quite) as efficient as the TreeList, my LinkedList requires less memory: where TreeList requires 3 references, 2 ints and 2 booleans per node, my list requires only 3 references per node +  ceil(sqrt(N/2)) fingers, one reference and one int per finger.


> 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
>
> (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)