Search code examples
javaarraylistdata-structuresabstract-data-type

ArrayList: insertion vs insertion at specified element


Consider an Arraylist. Internally it is not full, and the number of elements inserted so far is known. The elements are not sorted. Choose the operations listed below that are fast regardless of the number of elements contained in the ArrayList. (In other words, takes only several instructions to implement).

Insertion

Insertion at a given index

Getting the data from a specified index

Finding the maximum value in an array of integers (not necessarily sorted)

Deletion at the given index

Replacing an element at a specified index

Searching for a specific element

I chose Insertion at specified index, Getting the data from a specified index, and replacing an element but answer key says Insertion. As I usually understand it, in an ArrayList, the insert operation requires all of the elements to shift left. If we did this at the beginning of the list, we would have $O(n)$ time complexity. However, if we did it at the end, it would be $O(1)$.

My question comes down to: (1) what, if any, difference is there between insertion and insertion at specified index and (2) given this particular time complexity for insertion why is it considered "fast"


Solution

  • First take a look at these two methods defined in java.util.ArrayList

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
    public void add(int index, E element) {
        rangeCheckForAdd(index);
    
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
    
    1. Now if you see the first method (just adding element), it just ensures whether there's sufficient capacity and appends element to the last of the list.
      So if there's sufficient capacity, then this operation would require O(1) time complexity, otherwise it would require shifting of all elements and ultimately time complexity increases to O(n).
    2. In the second method, when you specify index, all the elements after that index would be shifted and this would definitely take more time then former.