6 ms·

some thoughts: 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 app

some thoughts: 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.

peeters 10y ago
> 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).
- ivan_gammel 10y ago
  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.
  - leecarraher 10y ago
    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).
  - imtringued 10y ago
    You can always swap the current element with the last element and then delete the last element in an unordered list.
    - deleted 10y ago
      [deleted]
    - ivan_gammel 10y ago
      java.util.List is ordered by definition (first sentence in Javadoc, if you want to verify).
jdmichal 10y ago
As cristaloleg pointed out [0], it's an unrolled linked list with variable node sizing. B-tree is, in some sense, an unrolled binary search tree, so that's why it looks familiar. [0] https://news.ycombinator.com/item?id=12274657 https://news.ycombinator.com/item?id=12274657

peeters 10y ago

> 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).

ivan_gammel 10y ago
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.
- leecarraher 10y ago
  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).
- imtringued 10y ago
  You can always swap the current element with the last element and then delete the last element in an unordered list.
  - deleted 10y ago
    [deleted]
  - ivan_gammel 10y ago
    java.util.List is ordered by definition (first sentence in Javadoc, if you want to verify).

jdmichal 10y ago

As cristaloleg pointed out [0], it's an unrolled linked list with variable node sizing. B-tree is, in some sense, an unrolled binary search tree, so that's why it looks familiar. [0] https://news.ycombinator.com/item?id=12274657 https://news.ycombinator.com/item?id=12274657