Re:GlueList – Fast New Java List Implementation
by ivan_gammel on Friday August 12, 2016 @11:10AM
(#12276315)
You probably forgot that it's possible to remove current element via Iterator, which indeed gives us O(1) for LinkedList in best case. Removal from ArrayList is more expensive except the case when you remove the last element.
Re:GlueList – Fast New Java List Implementation
by imtringued on Friday August 12, 2016 @01:03PM
(#12277132)
You can always swap the current element with the last element and then delete the last element in an unordered list.
Re:GlueList – Fast New Java List Implementation
by ivan_gammel on Saturday August 13, 2016 @12:22PM
(#12281998)
java.util.List is ordered by definition (first sentence in Javadoc, if you want to verify).
Re:GlueList – Fast New Java List Implementation
by leecarraher on Friday August 12, 2016 @11:45AM
(#12276560)
my thoughts exactly. removing where you need random access to elements to me always = array list. Things i iterate through and manipulate = linked list, otherwise every get() is an O(n).
That assumes you have a reference to the node, which isn't true in Java's LinkedList, as the nodes are encapsulated. The remove() operation in List either takes the object you want to remove (by equality) or an index. Both require an O(n) scan to find the node, then it can be removed in O(1).