Dynamic Array Implementation

In Java, ArrayList is a dynamic array implemented based on an underlying array. It can store elements of any type, including primitive data types and object references. ArrayList supports the dynamic addition and removal of elements and provides random access capabilities, making it widely used within the Java Collections Framework.

The implementation principle of ArrayList involves storing elements in an internal array. When the number of elements exceeds the current capacity of the array, the list automatically expands (resizes). During expansion, ArrayList creates a new, larger array, copies all elements from the old array to the new one, and appends any newly added element(s) to the end of this new array. When adding or removing elements, ArrayList automatically adjusts the size of the internal array to accommodate the current number of elements.

The primary methods of ArrayList include:

  • add(E e): Adds the specified element to the end of the ArrayList.
  • add(int index, E element): Inserts the specified element at the specified position in the ArrayList.
  • remove(Object o): Removes the first occurrence of the specified element from the ArrayList.
  • remove(int index): Removes the element at the specified position in the ArrayList.
  • get(int index): Returns the element at the specified position in the ArrayList.
  • set(int index, E element): Replaces the element at the specified position in the ArrayList with the specified element.
  • size(): Returns the number of elements in the ArrayList.
  • clear(): Removes all elements from the ArrayList.
  • indexOf(Object o): Returns the index of the first occurrence of the specified element in the ArrayList, or -1 if not found.
  • lastIndexOf(Object o): Returns the index of the last occurrence of the specified element in the ArrayList, or -1 if not found.
  • subList(int fromIndex, int toIndex): Returns a view (sub-list) of the portion of this ArrayList between the specified indices.

It is important to note that since ArrayList is implemented based on an array, its element access and traversal operations are very fast, with a time complexity typically of O(1). However, insertion and deletion operations are relatively slower because they require shifting other elements to maintain continuity, resulting in a time complexity of typically O(n). Additionally, as a dynamic array, ArrayList incurs significant space overhead because it must reserve extra capacity for future expansions. In applications, you should select the appropriate data structure based on specific scenarios to meet your requirements.