ArrayList in Java
ArrayList is one of the implementation of the List interface. It is internally a resizable-array under the hood. ArrayList is equivalent to Vector but the only difference is it is not synchronized.
- ArrayList uses Array internally to store the data. Hence as like Array, random access is possible and it is very fast. The operation is O(1) constant time complexity.
- Other operations like add, remove is O(N) linear time complexity approximately.
|
1 2 3 4 5 6 |
List<String> names = new ArrayList<String>(3); // Add elements to list names.add("Kidzee"); names.add("funKids"); names.add("KidsPlay"); |
- For remove operation, ArrayList is not so efficient since the elements has to be shifted in this case. For example, if the 1st element in the list is removed then all other elements has to be shifted by one position and this operation is O(N) complexity. Hence if there is a need for lot of remove operations, LinkedList is better suited for this purpose.
- ArrayList supports other operations like size(), isEmpty(), sort(), toArray().
|
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 |
package com.rayfocus.datastructures.arraylist; import java.util.ArrayList; import java.util.List; public class ArrayListDS { public static void main(String[] args) throws NoSuchFieldException, SecurityException, IllegalArgumentException, IllegalAccessException { // Initializing the ArrayList; If number of elements known before then provide it during initialization List<String> names = new ArrayList<String>(3); // Add elements to list names.add("Kidzee"); names.add("funKids"); names.add("KidsPlay"); // Iterate the values in the list for(String val: names) { System.out.println("name : "+val); } // Element retrieval using random index - Very fast O(1) complexity System.out.println("Element at index (0) is "+names.get(0)); // Remove values from list // Not so efficient since the elements has to shifted internally in the array. // LinkedList serves better for this purpose System.out.println("Remove element at index (1)"); names.remove(1); System.out.println("After remove, now the name in index (1) is : "+names.get(1)); // will print out "KidsPlay" // Size of ArrayList System.out.println("Size : "+names.size()); // Check isEmpty System.out.println("List isEmpty? "+names.isEmpty()); } } |
Capacity re-allocation when adding elements
Since ArrayList is a re-sizable array, if the capacity of the Array reaches the maximum a new Array is created and elements are copied to new Array. So in general, if the number of elements to be stored is known ahead it’s better to initialize the ArrayList using the size itself.
For example, if 200 items to be stored in list, then
List<String> names = new ArrayList<String>(200);
so that an Array is created with initial capacity of 200.
Summary
ArrayList is a good choice, when
- The elements are going to be added and retrieved using the random index value. It is O(1) complexity.
- The applications don’t need to remove the elements which are added.
- You have to avoid the hassle of creating a new Array and copy the elements into it.
ArrayList is not so efficient, when
- There is lot of remove operations to be performed. This operation is O(N) time complexity.
- There is a need to synchronize the operations for concurrent access. Since ArrayList is not designed to be thread safe.
