-
Notifications
You must be signed in to change notification settings - Fork 1
List
ArrayList internally uses array object to add(or store) the elements. In other words, ArrayList is backed by Array data -structure.The array of ArrayList is resizable (or dynamic).
In the ArrayList class in java, the following array is defined to store the elements of the ArrayList.
- It ensure default capacity 10 only when you add first element in List.
- If you are adding element on index which is more than the size it will throw java.lang.IndexOutOfBoundsException
private transient Object[] elementData;
**1. Using Default Constructor **
List<> list = new ArrayList<>();
The Following code will executed.
private static final Object[] EMPTY_ELEMENTDATA = {}; // empty array instance
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
**1. With Initial Capacity **
List<> list = new ArrayList<>(20);
The Following code will executed.
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
};
}
EnsureCapacity ensureCapacityInternal() determines what is the current size of occupied elements and what is the maximum size of the array. If the size of the current elements (including the new element to be added to the ArrayList) is greater than the maximum size of the array then increase the size of array. But the size of the array can not be increased dynamically. So, what happens internally is, a new Array is created and the old array is copied into the new array. The new capacity of the array will be calculated as below:
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
Tip :ArrayList uses shallow copy to copy the reference of the object to the new ArrayList instance.
When an ArrayList instance with no initial capacity is created and is empty, then, the add() method is invoked to add an element to the ArrayList instance, the following code is executed to apply a default size to the array.
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
In the above code, minCapacity is the size of the current elements (including the new element to be added to the ArrayList). DEFAULT_CAPACITY is 10 in ArrayList class and DEFAULTCAPACITY_EMPTY_ELEMENTDATA is an empty array object.
Runtime performance of ArrayList The size, isEmpty, get, set, iterator, and listIterator operations run in constant time O(1). 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. The constant factor is low compared to that for the LinkedList implementation.