Menu
Is ArrayList an array or a list in java? what is the time complexity for the get operation, is it O(n) or O(1)?
390
An ArrayList in Java is a List that is backed by an array . The get(index) method is a constant time, O(1) , operation.
ArrayList has O(n) time complexity for arbitrary indices of add/remove, but O(1) for the operation at the end of the list. LinkedList has O(n) time complexity for arbitrary indices of add/remove, but O(1) for operations at end/beginning of the List.
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.
An ArrayList in Java is a List that is backed by an array.
The get(index) method is a constant time, O(1), operation.
The code straight out of the Java library for ArrayList.get(index):
public E get(int index) { RangeCheck(index); return (E) elementData[index]; } Basically, it just returns a value straight out of the backing array. (RangeCheck(index)) is also constant time)
105
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
