masyamandev opened a new pull request #129: Indexed tree list URL: https://github.com/apache/commons-collections/pull/129 Here is an implementation of List with optimized indexOf method. Proposed data structure recalculates indexes on the fly when objects are inserted or removed from the middle of the list. There are no O(n) operations on a single element. Add, get, remove and indexOf methods have complexity of O(log(n)) if all elements in the list are different, however performance may degrade up to O(log(n) ^ 2) in cases when all elements in the list are the same. There are 2 data structures implemented. IndexedTreeListSet contains unique elements and implements both List and Set. All operations performs as O(log(n)). Slightly faster than IndexedTreeList. IndexedTreeList is the similar structure, but it does not have restriction for unique objects. Performance may degrade up to O(log(n) ^ 2). This structure is slightly slower than IndexedTreeListSet even if it contains unique objects. Code is based on TreeList adding internal Map for indexing and improved node management. More information can be found in my original project's readme: https://github.com/masyamandev/indexable-set .
---------------------------------------------------------------- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: [email protected] With regards, Apache Git Services
