Re:GlueList – Fast New Java List Implementation
by peeters on Friday August 12, 2016 @11:04AM
(#12276259)
> linked list should be able to do inserts and removes in O(1).
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).
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).
remove and add worst case complexity is O(mn) ! that is terrible, linked list should be able to do inserts and removes in O(1).
the test of appending is faster. but is it? I would offer that it's likely java doing some more datatype and bounds checking in their implementations, which is inline with the marginal speedup and relatively linear growth complexity. furthermore there are resize effects that will happen periodically as big malloc+move events.
worse case complexity seems incorrect for worse case search and access. assuming bins, you'd have to traverse the bin as well, so access should be O(m+n) .
but what about a remove test, or an actual search test? this looks somewhat like a b-tree.