List is one of common collections in Java. Here we are going to discuss about list and how it works internally in java.
1. List/ArrayList/LinkedList
A List is an ordered Collection. Lists may contain duplicate elements. In addition to the operations inherited from Collection, the list interface includes operations for the following:
- Positional access (random access): manipulates elements based on their numerical position in the list. This includes methods such as
get,set,add,addAll, andremove. - Search: searches for a specified object in the list and returns its numerical position. Search methods include
indexOfandlastIndexOf. - Iteration: extends
Iteratorsemantics to take advantage of the list’s sequential nature. The listIterator methods provide this behavior. - Range-view: The sublist method performs arbitrary range operations on the list.
There are two List implementations. ArrayList, which is usually the better-performing implementation, and LinkedList which offers better performance under certain circumstances.
In the example below, an object of ArrayList has been created. The add() method is invoked to add the element to the list. Then, the result are displayed. The question is how add() method works internally to add the elements to the list?
public static void main(String[] args) throws IOException {
List<> list = new ArrayList<>();
list.add(20);
list.add("Java Code Geeks");
list.add("ArrayList implementation in java");
System.out.println(list);
}
Output:
[20, Java Code Geeks, ArrayList implementation in java]
There are two overloaded add() methods in ArrayList class:
- add(Object): adds the element to the end of the list.
- add(int index, Object): adds the element at the specified position in the list.
Both methods have a similar implementation. So, we are going to look at add(Object) method here.
2. ArrayList implementation inside Java
In the ArrayList class in java, the following array is defined to store the elements of the ArrayList.
private transient Object[] elementData;
There are two different ways to create an ArrayList object.
2.1 Create an empty list with initial capacity
When an object of ArrayList is created without initial capacity, the default constructor of the ArrayList class is invoked. It uses empty array instance to create the new object.
List<> list = new ArrayList<>();
the following code is executed:
private static final Object[] EMPTY_ELEMENTDATA = {}; // empty array instance
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
When an object of ArrayList is created with an initial capacity, the ArrayList constructor is invoked to create the array internally.
List<> list = new ArrayList<>(20);
and the following code is executed:
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
The size of the array will be equal to the argument passed in the constructor. Then, size of the array will be 20 in above example
2.2. Create a non empty list containing the elements of a specified collection.
An object of ArrayList also can be created based on a specific collection.
List list = new ArrayList<>(Collection c);
then, the following code is executed:
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
The above ArrayList constructor will create an non empty list containing the elements of the collection passed in the constructor.
2.3. How the size of ArrayList grows dynamically?
In the add(Object), the capacity of the ArrayList will be checked before adding a new element. Here is the implementation of the add() method.
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
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);
In the above code, minCapacity is the size of the current elements (including the new element to be added to the ArrayList).
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.
3. 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.
4. Conclusion
Now that you know how List works internally in Java, you might want to know about the implementation of Set or Map inside Java and how they work. Because these sort of questions shows that candidate has a good knowledge of Collection. You can checkout these examples:
