ArrayList in Java is an implementation of the List interface. Few points about ArrayList
1. Internally uses array but can be dynamically resized.
2. Allows duplicate elements
3. Maintains the insertion order.
4. Is not synchronized.
ArrayList in Java
In this article we will see the basics of ArrayList in java. Some of the topics covered are
1. How ArrayList works internally
2. Methods of ArrayList
3. When to use an ArrayList.
How ArrayList works internally
ArrayList internally uses an array of Object to store the elements.
|
1 |
private transient Object[] elementData; |
You will notice that the Object[] is marked as transient, hence serialization doesn’t happen automatically. ArrayList has its own methods private void readObject(java.io.ObjectInputStream s) and private void writeObject(java.io.ObjectOutputStream s)
ArrayList can be created using either of the 2 constructors provided
|
1 |
public ArrayList() |
|
1 |
public ArrayList(int initialCapacity) |
The default constructor creates an ArrayList with the capacity of 10, but you can customize the capacity using the other constructor and provide the capacity you need.
As earlier stated, ArrayList is an re-sizable List, so lets see how ArrayList dynamically grows when elements are added.
When a new element is added, the add method in ArrayList first checks the capacity. If ArrayList has space it will add the new element, else it will call the grow() method for increasing the capacity.
From java 7, the capacity is increased using a shift operator. A new array is created with new capacity and old data is copied into the new array.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
private void ensureCapacityInternal(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } |
Constructors
ArrayList()
Constructs an empty list with an initial capacity of ten.
ArrayList(Collection c)
Constructs a list containing the elements of the specified collection, in the order they are returned by the collection’s iterator.
ArrayList(int initialCapacity)
Constructs an empty list with the specified initial capacity.
ArrayList methods
Below are few of the methods that are mostly used for ArrayList manupilation
1. public boolean add(E e)
Appends the specified element to the end of this list.
2. public void add(int index, E element)
Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).
3. public E remove(int index)
Removes the element at the specified position in this list. Shifts any subsequent elements to the left (subtracts one from their indices).
4. public boolean remove(Object o)
Removes the first occurrence of the specified element from this list,if it is present.
5. public void ensureCapacity(int minCapacity)
6. public List
7. void clear()
It is used to remove all of the elements from this list.
8. boolean removeAll(Collection c)
It is used to remove all the elements from the list.
When to use ArrayList
For deciding when to use an ArrayList, lets see the internal implementations of add and remove methods.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // Let gc do its work return oldValue; } public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } public E get(int index) { rangeCheck(index); return elementData(index); } |
If you see the add(int index, E element) you will see that once the element is added at the specified location, the other elements are shifted to the right. This creates an overhead while adding elements to a specific position in ArrayList. Similarly for remove(int index), once the element is removed, the other elements after that location are shifted to left. So clearly using ArrayList for adding/removing elements from a specific position is not advisable. But if you see get(int index) directly gives you to the element from the array (elementData[]). Hence using ArrayList is effective if you have frequent search operation.
This was some basics on ArrayList. You can also go through few examples on
1. How to Iterate ArrayList in java
2. Sorting of ArrayList in Java using Comparators
Reference:
1. ArrayList Java Docs