Array List:
- ArrayList works on the principle creating arrays and adding elements to it.
- Java
ArrayList class uses a dynamic array for storing the elements. It extends
AbstractList class and implements List interface.
- Java
ArrayList class can contain duplicate elements.
- Java
ArrayList class maintains insertion order.
- Java
ArrayList class is non synchronized.
- Java
ArrayList allows random access because array works at the index basis.
- In
Java ArrayList class, manipulation is slow because a lot of shifting needs
to be occurred if any element is removed from the array list.
- When we create array list in Java, the default size is 10
- After that when we tried to insert 11th value in array list, then bigger array list will created and copy all value from past array list to new array list and reference will indicate new array list.
- The size of new array list will be New arraylist = (current arraylist*3/2) +1
Example:
List<Integer> l = new ArrayList<Integer>();
//Default size 10
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this(10);
}
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this(10);
}
l.add(1); //checks for the size .
private void ensureCapacityInternal(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length >
0)
grow(minCapacity);
}
Here ensureCapacityInternal method
is called when an element is added.
if (minCapacity -
elementData.length > 0)
In our case
minCapacity = 1
elementData.length = 10
So minCapacity - elementData.length
= 1-10 =-9 which is not greater than ‘ZERO ’ and hence the element is added to
the arraylist.
When we insert 11th element
into the array,
minCapacity = 11
elementData.length = 10
So minCapacity - elementData.length
= 11-10 =1 which is true and hence ‘grow’ method will be called.
private void grow(int minCapacity) {
int oldCapacity =
elementData.length;
int newCapacity = oldCapacity +
(oldCapacity >> 1);
if (newCapacity - minCapacity <
0)
newCapacity =
minCapacity;
if (newCapacity - MAX_ARRAY_SIZE >
0)
newCapacity =
hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData,
newCapacity);
}
In our case
minCapacity = 11
elementData.length = 10
So minCapacity - elementData.length
= 11-10 =1 which is greater than zero, hence condition will be true on addition
of 11th element and grow method will be called.
Now let’s explore grow method
int oldCapacity =
elementData.length;
In our case
oldCapacity = 10
int newCapacity = oldCapacity +
(oldCapacity >> 1);
In our case
newCapacity =10 + 0.5*10 =15
Here >> is right shift
operator which reduces a number to its half
If (newCapacity - minCapacity
< 0)
In our case
newCapacity - minCapacity = 15-11 =4
which is not less than zero hence next line inside if statement will not be
called.
newCapacity = minCapacity;
if (newCapacity -
MAX_ARRAY_SIZE > 0)
In our case
newCapacity - MAX_ARRAY_SIZE =
15 - 2147483639 = -2147483624,which is not greater than zero,hence next line
within If statement will not be executed.
newCapacity =
hugeCapacity(minCapacity);
Note : MAX_ARRAY_SIZE is defined in
ArrayList class as below
private static final int
MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
Next control will reach on below
line and this line will create new Array object with capacity 15 using static
copyOf method of Arrays class.It will copy the elements of old array to this
new array and elementData will start referring to this new Array. Hence there
is increase in capacity from 10 to 15 now.
elementData =
Arrays.copyOf(elementData, newCapacity);
Next time when 16th element will be
added, new size will be calculated as below
15+0.5*15 = 22 and so on.
add(index
i, E element)
When an element is inserted into the arraylist at a particular position, which is already filled with some other value, then a new array is created with the index kept vacant and the remaining element shifted to right.
List<Integer> l = new ArrayList<Integer>();
l.add(1);
l.add(2);
l.add(1,3);
l.add(4);
Here above we are trying to add 3 and position 1, since position 1 already has value '2'. A new array is created with value at index 1 kept vacant and the remaining elements are shifted to right. Than the element 3 is added at index 1.
get(int index)
The element present at that index in that array is returned. This is very fast.
When to use ArrayList
When the requirement is fetch data frequently and adding data is one time activity.
When not to use ArrayList
When the list is updated frequently
The element present at that index in that array is returned. This is very fast.
When to use ArrayList
When the requirement is fetch data frequently and adding data is one time activity.
When not to use ArrayList
When the list is updated frequently
