Detailed analysis of the ArrayList class [Part 1]

This article will take a detailed look at the ArrayList class from the Collections Framework, which is perhaps the easiest to understand, due to the fact that it is based on a regular array. You will almost certainly be asked a question about this class and its implementation in Java at the interview. In the second part we will analyze the remaining methods and write our own implementation of a dynamic array for numbers. The ArrayList class inherits from the AbstractList class and implements the following interfaces: List, RandomAccess, Cloneable, Serializable. A detailed analysis of the ArrayList class [Part 2] The ArrayList class supports dynamic arrays that can be expanded as needed. Its necessity and effectiveness is explained by the fact that a regular array has a fixed length: once it is created, it cannot grow or shrink, which imposes restrictions if it is not known how large the array will be needed. Essentially, the ArrayList class is a variable-length list array of object references. It is important to understand that the size (number of cells) of the internal array does not automatically decrease when elements are removed from it. In fact, the value of the variable size, which indicates the number of elements actually present in the array, is decreased. Let's say we create a new object of the ArrayList class and add 5 elements to it. By default, an array of 10 elements is created. In this case, the so-called capacity (size/volume) of our object will be equal to 10, but the value of the variable sizewill be equal to five. And when we delete elements, we see changes in the value of the variable size, since we .lengthcannot access the internal array of the ArrayList class and find out its length. The size can be reduced using an additional method trimToSize(), which will be discussed below. Let's look at the class fields.

• Field responsible for the default volume of the dynamic array:

  private static final int DEFAULT_CAPACITY = 10

  When creating a new object new ArrayList<>() (a parameterless constructor), an array of 10 elements is created inside.

• A field in which all elements of the collection are stored:

  transient Object[] elementData

  Marked with a keyword transient- the field is not written to the byte stream when using the standard serialization algorithm. It is worth noting that the field is not marked with the keyword private, but this was done in order to facilitate access to this field from nested classes (for example, SubList).

• A counter field that stores the number of elements actually in the array:

  private int size

  The value is incremented/decremented when performing operations such as insertion and deletion.

There are 3 more fields in the class, but essentially they are additional, so there is no point in considering them. The class has three constructors:

1. public ArrayList()– creates an empty list array of 10 elements;
2. public ArrayList(Collection < ? extends E > c)– creates a list array initialized with elements from the passed collection (if we want to create a new ArrayList based on some collection);
3. public ArrayList(int initialCapacity)– creates a list array with an initial capacity. If the passed parameter initialCapacity is greater than 0, then an array of the specified size is created (the internal field elementData is assigned a link to a new array of type Object of size initialCapacity). If the parameter is 0, then an empty array is created. If the specified parameter is less than 0, then an IllegalArgumentException is thrown.

Creating an Object

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

The newly created object listcontains properties (fields) elementDataand size. A value store elementDatais nothing more than an array of a specific 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 casting to the type, of course). Adding elements Classically adding elements to a list array is done using overloaded variants of the add().

public boolean add(E элемент)

Well, let’s add: list.add("0"); Inside this method, an overloaded version of the method is add()called, marked as private, which in turn takes three parameters as input: the element to be added, the internal array and its size. In the private method, a check occurs: if the passed size parameter is equal to the length of the internal array (that is, the array is full), then the array is assigned the result of the method grow(int minCapacity)(the current value of the field size + 1 is passed to the method, since it is necessary to take into account the element being added), in which the internal the array is assigned a link to the new created array obtained by copying the elements of the original array:

Arrays.copyOf(elementData, newCapacity(minCapacity))

As the second parameter of the method, copyOfwe indicate the result of the method newCapacity(int minCapacity), within which the new array size is calculated. It is calculated using the following formula: int newCapacity = oldCapacity + (oldCapacity >> 1) For an array with the default size, the following will be true: >> 1– bitwise shift to the right by one (an operator that reduces a number to half of it). Essentially, it means dividing by 2 to the power of 1. It turns out that we divide 10 by 2 and add 10. Total, the new capacity of the array is 15, but since we are adding the 11th element, then 15 + 1 = 16. Let's return to our list and suppose that we have already added 10 elements to it and try to add 11. The check will show that there is no space in the array. Accordingly, a new array is created and called Arrays.copyOf, which internally uses the system method System.arraycopy(). Or here’s a clear example from one article on JavaRush: After all these checks and increasing the size of the array if necessary, then in a private method add()a new element is added to the end of the array, and the current parameter sizeis increased by one. The old array will subsequently be processed by the garbage collector. This is how a dynamic array works: when we add elements, we check whether there is still room in it. If there is space, then we simply add the element to the end of the array. The end does not mean the last cell in the array, but the cell that corresponds to the value size. We added the first element to the array; it is placed in the cell with index [0]. The field value sizehas increased by one and = 1. We add the next element: we see that size = 1, accordingly we place the element in the cell with index [1] and so on. There is an overloaded version of the method with two parameters:

public void add(int index, E element)

We can specify the position (index) of the cell where we want to add the element. First, the correctness of the specified index value is checked, since there is a possibility that an incorrect index will be specified, which will point to a cell where there is nothing, or which simply does not exist. Checking indexes: index > size || index < 0– if the specified index is greater than the current size of the array or it is less than 0, then an exception is thrown IndexOutOfBoundsException. Then, if necessary, the size of the array is increased, similar to the example above. You've probably heard that during add/remove operations in an array, something is shifted somewhere (either to the right or to the left). So, the shift is carried out by copying the array: System.arraycopy(elementData, index, elementData, index + 1, s - index); All elements located to the right of the specified index will be shifted one position to the right (index+1). And only after that a new element is added to the internal array at the specified index. Since we have shifted part of the array to the right by one (a new array is not created), the cell we need will be free for writing. The link to the old array is erased and in the future it will be taken over by the garbage collector. Paste "maserati" into cell [3], which is already occupied: Thus, when an element is inserted at index and there are no free spaces in the array, the call System.arraycopy()will happen twice: the first in grow(), the second in the method itself add(index, value), which will clearly affect the speed of the entire adding operation. As a result, when it is necessary to write another element to the internal array, but there is no space there, then this is what happens inside the ArrayList:

• A new array is created with a size 1.5 times larger than the original one, plus one element.
• All elements from the old array are copied to the new array
• The new array is stored in the internal variable of the ArrayList object, and the old array is declared garbage.

The capacity of objects of the ArrayList type can be increased manually using the method:

public void ensureCapacity(int minCapacity)

By increasing the array capacity in advance, you can avoid additional redistribution of RAM later. The method increases the size of the internal array to accommodate the number of elements passed to minCapacity. The method ensureCapacity()does not affect the field size, it affects the capacity(size of) the internal array. Once again I emphasize that sizeboth are capacitydifferent things and it is very important not to confuse them! If you want to reduce the size of the underlying array from which the ArrayList is built to the current number of elements actually stored, you should call the trimToSize(). After removing elements from the collection, size()it will show the number of actually existing elements, and capacitywill not decrease! Suppose: we entered 100 elements, deleted the first 50, sizeit will become equal to 50, and so capacityit will remain 100. To reduce and capacity, we need to use the method trimToSize(), which adjusts our entire capacity to the current size. How does it fit? Copies our array so that there are no empty cells left (the length of the new array is simply equal to the size field). You can also add elements to our collection using the addAll.

public boolean addAll(Collection< ? extends E> c)
public boolean addAll(int index, Collection< ? extends E> collection);

The first option allows you to add all elements from the collection specified in the method parameter (for example, another sheet) to the original collection (insert at the end) for which the method call was made. The passed collection (it can also be a set) is converted into an array using the toArray(). Naturally, the adding operation is also carried out using copying. The second is to add all elements collectionto the list, starting from index index. In this case, all elements will shift to the right by the number of elements in the list collection. Removing elements First, let's look at the classic options for removing elements from an ArrayList.

public E remove(int index)

Performs deletion by index and shifts all subsequent (after the element at the specified index) elements to the left, thereby closing the “holes”. It also returns the deleted element (E), which is previously written to an additional variable before deletion, the value of which we obtain as a result of the method call. To understand what E is, you will need to become familiar with the so-called generic types. The notation E indicates that the method returns the data type that was specified when creating the ArrayList object (remember: List <String> list, accordingly, in this case, E will be “substituted” String). For a general understanding, I strongly recommend that you familiarize yourself with generic types. The correctness of the entered index is checked, and then inside the method, the element is not completely deleted, but a private method is called fastRemove(Object[] es, int i), in which the deletion already occurs. We pass our array and the specified index to the method as input. The elements are copied using System.arraycopy(), the size of the array is reduced, and then we assign null to the last element. It is worth noting that a new array is not created: System.arraycopy(es, i + 1, es, i, size - 1 - i); The part that is to the right of the position under the specified index (i+1) is copied into our original array (es), and it is located starting from the very position (i) where the element was located to be deleted. Thus, we performed a shift to the left and erased our element. Let's try to remove the element at index 3 from the array below: Let's consider the second version of the method:

public boolean remove(Object o)

The method removes the passed element from the list o, or more precisely, the object at the specified link. If an element is present in the list, it is removed and all elements are shifted to the left. If the element exists in the list and is successfully removed, the method returns true; otherwise, false. Similar to the option with deleting by index, the method is called fastRemove(), where exactly the same actions occur. The difference is that the method remove(Object o)additionally searches for the desired object through a method equals()of the Object class. When removing by value, the loop goes through all the elements of the list until a match is found. Only the first element found will be deleted. Let's summarize: when deleting elements from a dynamic array, there are no holes left as in a regular array (the deleted cell will not be empty). All subsequent elements (that were to the right of the index) are shifted one position to the left. There are several additional methods that can be used to remove elements from the list to varying degrees. Let's look at them briefly. Cleaning out our collection:

public void clear()

A simple loop foriterates through all the elements of an array, assigning null to each element. You can remove those elements from our collection that are contained in another transferred collection like this:

public boolean removeAll(Collection< ?> c)

If you need to remove several elements, you probably shouldn’t do it in a conditional loop: it’s more convenient and safer to use the method removeAll(). It accepts a collection of elements that will be removed from the list. The collection must contain elements of the same type that the target list stores. Otherwise it will be thrown away ClassCastException. The method will return true if the list was changed as a result of the method call. Removes elements that do not belong to the passed collection:

public boolean retainAll(Collection< ?> c)

Let's say we have a collection:

List< String> listFirst = new ArrayList<>();
listFirst.add("White");
listFirst.add("Black");
listFirst.add("Red");

And the second:

List< String> listSecond = new ArrayList<>();
listSecond.add("Green");
listSecond.add("Red");
listSecond.add("White");

Then after listSecond.retainAll(listFirst)in listSecondwill remain:

"White"
"Red"

Since "Green" was removed, which is not in listFirst. But after listSecond.removeAll(listFirst)that it listSecondwill remain:

"Green"
Удалorсь все элементы, которые есть в listFirst.

Not belonging to the passed collection - means that if there are elements that are not in the passed collection, then you need to remove them from the first one (to which the method is applied). Belonging to the transferred collection - accordingly, if there is an element in both the first and second (transferred) collections, then the duplicate from the first is destroyed.

protected void removeRange(int fromIndex, int toIndex)

Removes from the list all elements that are between the starting specified index (inclusive) and the ending specified index (not inclusive). It's worth noting that the method cannot be called directly on an ArrayList object. To use it you need to inherit from AbstractList/ArrayList. The method is also used by another method (subList, which will be discussed later).

public boolean removeIf(Predicate< ? super E> filter)

Removes elements from a collection based on a given predicate. The predicate itself is a certain function/algorithm/condition on the basis of which one or more elements corresponding to a given condition will be removed. Predicate— a functional interface (contains only one method, so it can be used as a lambda), works on the principle “received one parameter - returned boolean”. Essentially, the method overrides the implementation from the interface Collectionand implements the following "strategy": it loops through the elements and marks those that match our Predicate; it is then run through a second time to remove (and shift) the elements that were marked in the first iteration. Let's implement an interface Predicatethat will return true if two objects are equal:

class SamplePredicate< T> implements Predicate< T>{
  T varc1;
  public boolean test(T varc){
     if(varc1.equals(varc)){
       return true;
  }
  return false;
  }
}

In another class, let's create an ArrayList from Stringand an object of our class that implements Predicate:

ArrayList< String> color_list = new ArrayList<> ();
SamplePredicate< String> filter = new SamplePredicate<> ();

varc1Let's write the value "White" to the variable :

filter.varc1 = "White";

Let's add a few lines to the list:

color_list.add("White");
color_list.add("Black");
color_list.add("Red");
color_list.add("White");
color_list.add("Yellow");
color_list.add("White");

Let's execute the method on the list removeIf, to which we will pass our object with the condition:

color_list.removeIf(filter);

As a result, all rows with the value "White" will be removed from the list, since our "predicate" compares them for equality. Final list: [Black, Red, Yellow]. Replacing elements

public E set(int index, E element)

Replaces the element at the specified position indexwith the passed one element. The index must also be greater than zero and less than the index of the last element, otherwise an exception will be thrown IndexOutOfBoundsException. No copies of the internal array occur. Simply, instead of the element at the specified index, a new element is inserted, i.e. overwrite the value.

public void replaceAll(UnaryOperator<e> operator)

Changes all elements of the collection (possible with a condition). Mostly used in combination with lambdas or an anonymous class (but for clarity, in the example we will simply use a class that implements the interface) that implements the interface UnaryOperatorand defines its methods. Let's implement the interface:

class MyOperator< T> implements UnaryOperator< T>{
   T varc1;
   public T apply(T varc){
     return varc1;
  }
}

In another class, let's create an ArrayList from Stringand an object of our class that implements UnaryOperator:

ArrayList< String> color_list = new ArrayList<> ();
MyOperator< String> operator = new MyOperator<> ();

varc1Let's write the value "White" to the variable :

operator.varc1 = "White";

Let's add a few lines to the list:

color_list.add("White");
color_list.add("Black");
color_list.add("Red");
color_list.add("White");
color_list.add("Yellow");
color_list.add("White");

Let's execute a method on the list replaceAllto which we will pass our object operator:

color_list.replaceAll(operator);

As a result, all values ​​in the list were replaced with "White": [White, White, White, White, White, White]. And this is how, for example, you can remove all spaces from the strings that are in the collection:

ArrayList< String> list = new ArrayList<>(Arrays.asList("A   ", "  B  ", "C"));
list.replaceAll(String::trim);

Other methods: You can convert the ArrayList list array into a regular array using the method:

public Object[] toArray()

or

public < T> T[] toArray(T[] a)

- here the type of the returned array is determined in runtime This method will allow:

1. speed up some operations;
2. pass an array as a parameter to a method that is not overloaded to accept the collection directly;
3. Integrating new collection-based code with legacy code that does not recognize collections.

Return a copy object of the array:

public Object clone()

Please note that the method clone()returns the Object type, so after calling it you will need to cast to the required class. Cloning creates a new independent object. Check the collection for the presence of an object:

public boolean contains(Object o)

Checks for the presence of an object in the list (internally using the equals method of the Object class, i.e. compares references), returns true/false depending on the result. In addition to the usual loops, you can iterate through (access each element, as well as perform some action) a collection using:

public void forEach(Consumer< ? super E> action)

This is how we can display our list:

List< Integer> numbers = new ArrayList<>(Arrays.asList(10, 20, 50, 100, -5));
numbers.forEach((number)-> System.out.println(number));

Without using lambdas you need to use an anonymous class and override the acceptinterface method Consumer:

numbers.forEach(new Consumer< Integer>() {
  @Override
   public void accept(Integer integer) {
      System.out.println(integer);
          }
});

Get an element by its index:

public E get(int index)

Used for random access to collection elements. Returns the element located in the list at the specified index. If index < 0or is index >=the maximum number of elements in the list, an exception will be thrown IndexOutOfBoundsException. This is the basic method of retrieving an element from a list, and the time to retrieve an element by index will always be the same, regardless of the size of the ArrayList, since it is accessing a specific array cell. Finding indexes for specified objects:

public int indexOf(Object o);
public int lastIndexOf(Object o);

The methods return the index of the first (when the given object is first encountered) or last occurrence (when the given object is last encountered) element in the list. If the element does not exist in the list, the methods will return -1. Check the collection for elements:

public boolean isEmpty();

The method returns true if the list is empty (looks to see if the field is equal size 0), otherwise false. If the list contains only null elements, the method will return false. In other words, null elements are also taken into account by this method. Find out the number of elements in a list:

public int size();

Returns the number of elements in the list (size field values). The number of elements may differ from the list capacity (capacity). Get an iterator for a list:

public Iterator< E> iterator();

Returns an iterator for a list for later use in a loop or any other processing. The iterator implements fail-fast behavior. If it runs through the collection and notices some modifications to it (that were not obtained using the iterator methods), it immediately throws an exception ConcurrentModificationException. The iterator has something called modification count. When the iterator iterates through the collection after each next/hasNext/remove, it checks this counter. If it does not match what the iterator expected to see, it throws an exception. I will not consider iterators in detail here.

public ListIterator< E> listIterator() и public ListIterator< E> listIterator(int index)

Returns a list iterator for a list for later use in a loop or any other processing. The interface ListIteratorextends the interface Iteratorfor two-way traversal of the list and modification of its elements. In the overloaded version, you can pass the index from which the “traversal” will begin. The index in this case denotes the first element from which the method will begin its work next(), and when the method is called, previous()the traversal will begin from the element under the index “passed index - 1”.

public Spliterator <E> spliterator()

Java 8 introduces a new type of late binding and fail-fast iterator called a delimiter iterator. Separator iterators allow you to iterate over a sequence of elements, but they are used in a different way. The most important feature of the Spliterator interface is its ability to support parallel iteration of individual parts of a sequence of elements, and therefore parallel programming.