[
https://issues.apache.org/jira/browse/COLLECTIONS-797?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Rodion Efremov updated COLLECTIONS-797:
---------------------------------------
Attachment: IndexedLinkedListTest.java
FingerListTest.java
> 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: AddAtBeginning.png, AddAtEnd.png, AddAtRandom.png,
> FingerListTest.java, GetAtRandom.png, IndexedLinkedList.java,
> IndexedLinkedListTest.java, Iterate.png, IterateAndModify.png,
> RemoveAtRandom.png, RemoveFromBeginning.png, RemoveFromEnd.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)
