4 ms·
> 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 no
by 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 agoYou 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 agomy 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 agoYou 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 agojava.util.List is ordered by definition (first sentence in Javadoc, if you want to verify).