ArrayList's add(index,object) method throw IndexOutOfBoundException

Question

On creating an arrayList using the below mentioned code snippet:

List arrayList = new ArrayList(16);

The internal implementation of ArrayList creates an array elementData of size 16 and assigns nullat every location. On doing something like arrayList.add(2,"HelloWorld") gives an IndexOutOfBoundException as the index at which the element is being added (i.e 2) is greater than the size attribute of the arrayList .

As clear from the javaDocs, the size attribute of the arrayList is initialized to 0 when the arrayList is initialized and is incremented by 1 everytime a new element is added to the arrayList

Can someone please explain, why the ArrayList dataStructure was designed this way in the first place. Even tho' the internal dataStructure elementData was initialized with 16 null values at the creation of arrayList, still it does not allow to add value at indeces > size; (assuming index <16 in this case). What was the idea to implement the add(index,object) funtionality to be governed by the size attribute of the arrayList?

Answer 1

In fact, the default constructor of ArrayList constructs a list with an initial capacity of 10.

public ArrayList() {
    this(10);
} 

But why we need such an allocation? As you understand, if you indicate the size of ArrayList in advance, you can provide efficient for the list. Otherwise, after the number of elements exceeds the initial capacity of ArrayList, a new reallocation operation is performed for each element.

The documentation says:

public void add(int index, E element)

Throws:

IndexOutOfBoundsException - if the index is out of range (index < 0 || index > size())

As you can see, it throws IndexOutOfBoundsException if (index > size()). Since ArrayList's "public int size()" returns elements which are not equal to null, your size equals to 0 (not 16 as you said in your example). In other words, if null values were counted as well, the size of each ArrayList that was created with default constructor would be 10.

Consequently, "arrayList.add(2, "HelloWorld")" throws IndexOutOfBoundsException since index = 2 but size() = 0.

Edit:

I think when you mount your argument, you use this as base:

String[] arr = new String[5];
arr[3] = "hello";

System.out.println(arr[3]); 

Then, you think why you can give a value in an array element directly but why you cannot do the same thing while using add(int index, E element) method of ArrayList. Actually, it is true but there is no condition to implement ArrayList as complete counterpart of Array. In other words, this method is conditioned with that rule since it is nature of ArrayList. As we all know, when you create an array, you specify its size in square brackets. The constructor of ArrayList which takes int as parameter does not do the same thing. It performs just an imaginary allocation. Yes, it could specify its initial size with this allocation or after add(int index, E element) is called, size could be increased by one. However, ArrayList is implemented to provide an array-like structure which has continuity with respect to index number but has no fixed size. Thence, there are some other higher level of abstraction examples do this task. To exemplify, LinkedHashMap structure.

Answer 2

See the java doc of ArrayList's add(int index, E element) method. Here you can find the ArrayIndexOutOfBound exception occurred when if the index is out of range (index < 0 || index > size()).

You declared an ArrayList with an initial capacity 16. It doesn't mean that each of the 16 indexed position of the ArrayList contains element. It just mention the initial capacity and when it necessary it will grow it's size dynamically.

See the source code the constructor from the ArrayList class -

/**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param   initialCapacity   the initial capacity of the list
     * @exception IllegalArgumentException if the specified initial capacity
     *            is negative
     */
    public ArrayList(int initialCapacity) {
    super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
           this.elementData = new Object[initialCapacity];
    }

Here we can not find anything that told us - ArrayList will initiated with null value.

Update: Based on your comment I have done some experiment, since I'm not sure about whether an array of reference/non-primitive type will initialized with null. See the following code below. Run the the code by uncommenting each of line at per execution -

import java.util.List;
import java.util.ArrayList;

public class ArrayListTest{

    public static void main(String[] args){

        List<String> list1 = new ArrayList<String>(); //default with initial capacity 10
        List<String> list2 = new ArrayList<String>(5);
        List<String> list3 = new ArrayList<String>(5);

        list2.add(null);
        list2.add(null);
        list2.add(null);

        list3.add("zero");
        list3.add("one");
        list3.add("two");

        //System.out.println(list1.get(4)); //IndexOutOfBoundException

        //System.out.println(list2.get(0)); //null
        //System.out.println(list2.get(2)); //null;
        //System.out.println(list2.get(3)); //IndexOutOfBoundException

        //System.out.println(list3.get(0)); //zero
        //System.out.println(list3.get(2)); //two;
        //System.out.println(list3.get(3)); //IndexOutOfBoundException
        //list3.add(4, "four"); //IndexOutOfBoundException

    }

}

Here you can see list2.get(0) and list2.get(2) gives you null. Because we put null at these index. But list2.get(3) doesn't give null since we didn't put null at index 3. So it seems array of reference/non-primitive type won't initialize with null. list2.get(3) gives IndexOutOfBoundException.

You found the same scenario for the list3. where I didn't put any null in this list. Even when we are trying to add some value at index 4 of list3 it gives IndexOutOfBoundException. Since the index 4 is not available for the list3. But you can add some value at index 2 of list2. Cause at index 2 of this list I have inserted null manually.

So in long story short (I think) - new ArrayList<SomeType>(givenSize) wouldn't initialize an array with givenSize with all element setting to null.

Hope it will Help.
Thanks.

Answer 3

You rarely need to specify the capacity of an ArrayList, it can improve the performance only if you know how many elements your ArrayList will hold.

ArrayList is simply a List that can automatically be grown or shrink. Using List, you never need to add an element in the place n if the list is empty, you simply link it to the previous node (unless it's the head of course) - that's the idea of ArrayList except the fact that it can be grown/shrink automatically.

Answer 4

You can not add object at a specific index till it contains null. You just need to add object using add method and then you can update values on a index.

For Example.

 ArrayList<Integer> arrlist = new ArrayList<Integer>(5);

// use add() method to add elements in the list
arrlist.add(15);
arrlist.add(22);
arrlist.add(30);
arrlist.add(40);

// adding element 25 at third position
arrlist.add(2,25);

Answer 5

The purpose of having an internal array with a size greater then List.size() is to avoid re-allocating the array unnecessarily. If the internal array always had the same size as the List, then every time a new element is added, the internal array would have to be re-allocated, causing a performance penalty.