Menu
I found other entries for this question that dealt with specific methods, but nothing comprehensive. I'd like to verify my own understanding of the most often used methods of this data structure:
O(1) - Constant Time:
isEmpty() add(x) add(x, i) set(x, i) size() get(i) remove(i) O(N) - Linear Time:
indexof(x) clear() remove(x) remove(i) Is this correct? Thanks for your help.
460
Getting back to complexity analysis, the ArrayList. contains() method requires O(n) time. So the time we spend to find a specific object here depends on the number of items we have in the array.
To remove an element by value in ArrayList and LinkedList we need to iterate through each element to reach that index and then remove that value. This operation is of O(N) complexity.
ArrayList has O(1) time complexity to access elements via the get and set methods. LinkedList has O(n/2) time complexity to access the elements.
TIL that the amortized time complexity of adding an item to an ArrayList in Java is O(1), but that the “worst case” for an add operation is O(n).
The best resource is straight from the official API:
The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.
121
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
