[
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].
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 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 + ceil(N/2) fingers, one reference and one int per
finger.
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.
> 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].
>
> 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 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 + ceil(N/2) fingers, one reference and one int
> per finger.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
