Data structures in pictures. Arraylist

    I greet you, habralyudi!

    It took me the head to write several articles about how some data structures are implemented in Java. I hope the articles will be useful to visuals (our pictures are everything), beginner java visuals, and also to those who already know how to write new ArrayList (), but have little idea of ​​what is happening inside.



    Today let's talk about ArrayList

    ArrayList - implements the List interface. As you know, in Java arrays have a fixed length, and after the array is created, it cannot grow or shrink. ArrayList can change its size during program execution, and it is not necessary to specify the dimension when creating the object. ArrayList elements can be of absolutely any type, including null.



    Object Creation


    ArrayList list = new ArrayList();

    The newly created list object contains the elementData and size properties .

    The storage of elementData values is nothing more than an array of a certain type (specified in generic), in our case String [] . If a constructor without parameters is called, then by default an array of 10 elements of type Object will be created (with a cast to a type, of course).

    elementData = (E[]) new Object[10];



    You can use the ArrayList (capacity) constructor and specify your initial list capacity.


    Adding Items


    list.add("0");




    The following things happen inside the add (value) method :

    1) it checks to see if there is enough space in the array to insert a new element;

    ensureCapacity(size + 1);

    2) an element is added to the end (according to the size value ) of the array.

    elementData[size++] = element;

    We will not consider the entire ensureCapacity (minCapacity) method , we will focus only on a couple of interesting places. If there is not enough space in the array, the new capacity is calculated by the formula (oldCapacity * 3) / 2 + 1 . The second point is copying the elements. It is implemented using the native System.arraycopy () method , which is not written in Java.

    
    // newCapacity - новое значение емкости
    elementData = (E[])new Object[newCapacity];
    // oldData - временное хранилище текущего массива с данными
    System.arraycopy(oldData, 0, elementData, 0, size);
    


    The following demonstrates a loop alternately adding 15 elements:
    list.add("1");



    ...

    list.add("9");




    list.add("10");

    When adding the 11th element, the check shows that there is no space in the array. Accordingly, a new array is created and System.arraycopy () is called. After that, adding elements continues ...









    list.add("14");





    Adding to the "middle" of the list


    list.add(5, "100");

    Adding an element to a position with a specific index occurs in three stages:

    1) it checks to see if there is enough space in the array to insert a new element;

    
    ensureCapacity(size+1);
    

    2) prepare a place for a new element using System.arraycopy () ;

    
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    



    3) the value of the element with the specified index is overwritten.

    
    elementData[index] = element;
    size++;
    




    As you might guess, in cases where an element is inserted by index and there are no empty seats in your array, the call to System.arraycopy () will happen twice: the first in ensureCapacity () , the second in the add (index, value) method , which will obviously affect the speed of the whole add operation.

    In cases when you need to add another collection to the source list, and even to the "middle", it is worth using the addAll (index, Collection) method . And although this method is likely to call System.arraycopy () three times, in the end it will be much faster than adding one by one.


    Delete items


    There are two ways
    to remove elements: - by remove (index) index
    - by remove (value) value.

    Removing an element by index is quite simple.

    list.remove(5);

    First, determine how many items to copy.

    
    int numMoved = size - index - 1;
    

    then copy the elements using System.arraycopy ()

    
    System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    

    reduce the size of the array and forget about the last element

    
    elementData[--size] = null; // Let gc do its work
    


    When deleting by value, in a loop all elements of the list are scanned until a match is found. Only the first item found will be deleted.

    Addition 1: As MikeMirzayanov correctly noted , when deleting elements, the current value of capacity does not decrease, which can lead to peculiar memory leaks. Therefore, do not neglect the trimToSize () method .


    Summary


    - Quick access to items by index during O (1);
    - Access to elements by value in linear time O (n);
    - Slow when elements are inserted and deleted from the "middle" of the list;
    - Allows you to store any values ​​including null;
    - Not synchronized.


    References


    Source ArrayList
    Source ArrayList from JDK7
    JDK sources OpenJDK & trade 6 Source Release - Build b23


    Write comments / suggestions in the comments and does it make sense to continue.

    Also popular now: