ArrayList

Complexity of ArrayList:

Array ListTime ComplexitySpace Complexity
Adding ElementO(1) – resize O(log(n))
Removing ElementO(n)
Iterating ElementsO(n)
Retreving Element at PositionO(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

Leave a Comment