ArrayList

• https://medium.com/@basecs101/comparing-arraylist-and-linkedlist-in-java-latest-2b133b29489f
• https://www.geeksforgeeks.org/internal-working-of-arraylist-in-java/

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

• Internally uses Object[] array which is transient

transient Object[] elementData;

• Constructors:
  • ArrayList()
  • ArrayList(int capacity) — Initialize with the given capacity
  • ArrayList(Collection c) — ArrayList with elements from collection

Capacity

• The size of the internal static array
• Default initial capacity is 10 (JDK 17)

Resizing

• If you call new ArrayList<>(), then the capacity is 0
• When you add first element then capacity becomes default capacity: 10
• If you store more elements than current capacity, then current capacity increases by currentCapacity >> 1 which is approx. half the current capacity
• Hence we get following capacities if we keep adding elements:
  • 0 (initially empty)
  • 10 (default)
  • 15 (10 + 10/2)
  • 22 (15 + 15/2)
  • 33 (22 + 22/2)
  • 49 (33 + 33/2) and so on…

add(Object o)

• It has amortized complexity of O(1)
• Resizing operation takes O(N)
• if (size == 0):
  • initialize capacity by default capacity
• else if (size == currentCapacity):
  • resize the array to increase the capacity as defined in Resizing
• add element at the end

remove(int i) or remove(Object o)

• perform search for the object to retrieve index to be removed
• shift all the right elements towards left, reducing size of array by 1

ArrayList vs LinkedList

• ArrayList is similar to vector in C++
• LinkedList is similar to list in C++
• LinkedList is rarely used data structure, and it is better to consider ArrayDeque if possible