ArrayList

Complexity of ArrayList:

Array List	Time Complexity	Space Complexity
Adding Element	O(1) – resize O(log(n))
Removing Element	O(n)
Iterating Elements	O(n)
Retreving Element at Position	O(1)

• ArrayList is one of the implementation of List interface.
• Underlying data structure of ArrayList is Resizable Array or Growable Array.
• Underlying data structure of ArrayList is array, i.e data is stored inside an array.
• ArrayList are equivalent to Vector but ArrayList are not synchronized.
• All operations run in around O(n) time complexity.
• But if you want to remove items, this operation is not so efficient, we have to shift each item in our list O(n), instead we should use linked list.
• Capacity of an ArrayList should be defined during instantiation when ever possible (List<Object> l = new ArrayList<>(5000)), this may reduce the amount of incremental reallocation.
• Implements RandomAccess Interface(Only Array List and Vector), Clonable Interface and Serializable Interface
• Note : Except TreeSet and TreeMap heterogeneous objects are allowed.

Features of ArrayList :

• Best choice if reading at random index is required.
• Worst choice if adding and deleting in middle of list has to be performed.(Use Linkedlist)
• Duplicates are allowed
• Insertion order is preserved.
• Resizable or Growable
• Store heterogeneous object
• null insertion is possible
• Default initial capacity of arraylist is 10
• New capacity of arraylist will be (currentcapacity * 1.5)+1 (Default capacity increment will be 10, 16, 25…)
• Implements RandomAccess Interface which helps to access all the index of an array with the same speed as be it 1st element or 1000th element.

When to use ArrayList ?

• ArrayList provides constant time for search operation.
• it is better to use ArrayList if searching is more frequent operation than add and remove operation.

Constructors of ArrayList :

ArrayList<Object> l = new Arraylist<>(); //size 10 by default
ArrayList<Object> l = new Arraylist<>(int initialCapacity); //predefined capacity
ArrayList<Object> l = new Arraylist<>(Collection c); //create equivalent array list

Example :

public class ArrayListDemo {
	public static void main(String[] args) {
		ArrayList<String> l = new ArrayList<>();
		l.add("A");
		l.add("B");
		l.add(null);
		System.out.println(l);
		l.remove(2);
		System.out.println(l);
		l.add("M");
		l.add("N");
		System.out.println(l);
	}
}

Questions :

• Remove duplicates from ArrayList in Java