Data structures in pictures. ArrayList

Greetings to you, habra people!

It occurred to me to write a few articles about how some data structures are implemented in Java. I hope the articles will be useful for visuals (our pictures are all), aspiring java-visuals, as well as those who already know how to write new ArrayList (), but have little idea what happens inside.


')
Today we will talk about ArrayList

ArrayList - implements the List interface. As you know, in Java, arrays have a fixed length, and after an 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 an object. ArrayList elements can be absolutely any type including null.

Object creation

ArrayList<String> list = new ArrayList<String>(); 

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 conversion 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 is checked whether 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 whole method ensureCapacity (minCapacity) , we’ll dwell only on a couple of interesting places. If there is not enough space in the array, the new capacity is calculated using the formula (oldCapacity * 3) / 2 + 1 . The second point is copying items. 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 cycle demonstrates 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 this, the addition of elements continues.



...

 list.add("14"); 

Adding to the "middle" list

 list.add(5, "100"); 

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

1) it is checked whether there is enough space in the array to insert a new element;

 ensureCapacity(size+1); 

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

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

3) overwrites the value of the element with the specified index.

 elementData[index] = element; size++; 

As you can guess, in cases when an element is inserted by index and there is no free space in your array, the call to System.arraycopy () happens twice: the first one is to ensureCapacity () , the second one in the add method itself (index, value) , which will obviously affect the speed of the whole operation of adding.

In cases where you need to add another collection to the source list, and also to the “middle”, you should use the addAll method (index, Collection) . And although this method is likely to call System.arraycopy () three times, in the end it will be much faster than elementwise adding.

Deleting items

You can delete items in two ways:
- by index remove (index)
- by value remove (value)

Deleting an item by index is pretty easy.

 list.remove(5); 

First, determine how many elements need to be copied

 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, all elements of the list are scanned in the loop until a match is found. Only the first found item 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.

Results

- Quick access to elements by index in time 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.

Links

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


Write in the comments wishes / comments and whether it makes sense to continue.