"Super detailed! ArrayList source code graphic analysis"

"Super detailed! ArrayList source code graphic analysis"

An unpoetic female program lady is not a good cook~ Please indicate the source for reprinting, From Li Shiyu---[ blog.csdn.net/cjm24848365... ]

Yesterday we played arraycopy for a long time, today let's take a look at the source code of ArrayList.

Yes, it's time to use my poor drawing skills again~

First preview the outline of this article:

Let's start the journey of ArrayList's source code diagram. Let's start with the addition, deletion, modification and investigation, and then talk about the source code of ArrayListIterator. Of course, we will intersperse and talk about several major pits and precautions~

1. increase

ArrayList element addition operation involving two methods add(E object)and add(int index, E object).

1.1 add(E object) adds an element directly at the end

add(E object)This method is to add an element directly, and to insert it at the end.

If the size of the original array is not enough, it will be expanded first.

Finally, the data is added at the end, and the size is increased by 1.

The source code is as follows:

1.2 add(int index, E object) Add an element at the specified position

add(int index, E object)This function refers to inserting a new element at the index position.

  • Let's first look at the core steps of the insert operation:

    All the data starting from the position to be inserted must be moved one by one; then the data to be inserted is put in.

    Draw a picture for everyone to understand:

  • Learn the core after the insertion step, we take a look at add(int index, E object)the source code, insert an element to a specified location specifically how to achieve it.

    1. 1. check whether the index of the position to be inserted is legal.

    2. determine whether the array is sufficient:

    a. If the array enough, that is s<a.length, the direct call arraycopy(), all of the data from the index start are moved back one. (I have already talked about the use of arraycopy in detail in the previous article, so here we should know that he moved one digit from back to front in turn).

    b. If the array is full, that is, s>=a.lengthwhen, where necessary

    (1) First expand the original array to generate a new array;

    (2) Copy the data before index in the original array to the corresponding position of the new array.

    (3) Move the data after index in the original array one bit back to the new array.

    (4) Assign the new array to array.

    3. Place the element to be added at the index position, and the number of valid data size+1 at the same time.

    The source code is shown below:

Supplement: Expansion rules

We all know that the size of an array is immutable, while the size of an ArrayList is variable. The bottom layer of ArrayList also uses arrays, so how does the size of ArrayList change dynamically?

The answer is through expansion.

It is Object[] newArray = new Object[newCapacity(s)];this code.

Now let's take a look at newCapacity(s)the implementation in detail :

Here we do an explanation:

When the current capacity is currentCapacity<6, increment=12;

Otherwise, increment is equal to half of currentCapacity, that is, 0.5 times.

The size of the final return is currentCapacity+increment.

In other words, after the expansion, it is either +12 on the original basis, or it is expanded to 1.5 times the original.

2. Delete

ArrayList delete operation, we also look at two remove(Object object)and remove(int index).

2.1 remove(int index) delete the element at the specified position

  • Similarly, let's take a look at the core operation of deletion:

    The corresponding code is System.arraycopy(a, index + 1, a, index, --s - index);this code,

    That is: If you want to delete elements [index] position, it would have to put all the elements after the [index] are moved forward one , overwriting index the original location.

    Also draw a picture to help everyone understand:

  • After understanding the core of the operation, we take a look at remove(int index)the source code for it:

2.2 remove(Object object) delete a known element

remove(Object object) Delete a known element.

We have already known the operation of deleting an element at a specified position, so if we want to delete a known element, should we also find its corresponding position first, and then delete it.

  • So the question is, how to find the corresponding position of the element?

    Yes, traverse through the loop and compare to find the corresponding index.

There is a pit!

Note :

Calling the remove method will, and only delete the first element that is equal to the passed object through the equals method.

If null is passed in, the first null element is deleted.

Therefore, if a custom class wants to use the remove method to delete a specified value object from the list, it also needs to implement its own equals method for that type!

There is still a pit!

ArrayList can delete nodes sequentially, but! If you use a normal for loop, it must be deleted from the back to the front. Cannot delete from front to back.

Let's take a look at the [error demonstration]:

ArrayList list=new ArrayList();
list.add("a");
list.add("b");
list.add("c");

System.out.println(" "+list.toString());

//---- 
for (int i=0;i<list.size();i++){
    list.remove(i);
}
System.out.println(" "+list.toString());
 

[Wrong result display]:

[Analysis of the cause of the error]:

To delete all the nodes of the ArrayList in order, if we delete from the front-to-back order, first delete the data at the [0] position, but because the deletion is done by moving one bit from the back to the front, the position of the [0] It will be overwritten by the data of the next position, in fact [0] still has data. Draw another picture to make it easier for everyone to understand:

[The correct way]:

To delete all the nodes in order ArrayList, and the ordinary for loop, it can only move forward from deleted, so you will not go wrong.

3. Change and check

ArrayList is very simple to modify the data, the set(int index, E object)method is called , and the data in the corresponding position can be directly modified.

ArrayList is easy to get data. Since the sequence table has subscripts, just take out the corresponding subscript data directly.

4. 3.traversal methods of ArrayList

ArrayListThere are three ways we traverse: for circulation , enhanced for loops and iterators in three ways.

(Of course, the enhanced for loop is actually implemented with iterators. This can be verified by decompilation.)

ArrayList arrayList = new ArrayList();
arrayList.add(" ");
arrayList.add(" ");
arrayList.add(" ");
arrayList.add(" ");
arrayList.add(" ~");

System.out.println("for ");
for (int i = 0; i < arrayList.size(); i++) {
    System.out.print(arrayList.get(i));
}

System.out.println();
System.out.println("---------------------------------");
System.out.println(" for ");
for (Object s : arrayList) {
    System.out.print((String) s);
}

System.out.println();
System.out.println("---------------------------------");
System.out.println(" ");
Iterator<String> iterator = arrayList.iterator();
while (iterator.hasNext()) {
    System.out.print(iterator.next());
}
 

Let's take a look at the print result:

5. Interpretation of the iterator ArrayListIterator source code

Okay, we learned above that we ArrayListcan use iterators to traverse.

  • So why can it use iterators this way?

    For this we have to look at the source code again. Following arrayList.iterator()the iterator() method, we will find that ArrayList has an internal class ArrayListIterator. ArrayListIterator implements the Iterator interface, so it can be iterated in this way.

Now let's take a look at ArrayListIteratorthe relevant source code and precautions in detail .

1. we can see ArrayListIteratorthat Iteratorthis interface is implemented .

5.1 What is Iterator(iterator)?

We all know that in Java, there are many data containers, and these operations have many commonalities. The iterator is to provide a common operation interface for various containers. This makes the operation of the container standardized.

3.methods are defined in the Iterator interface:

  • hasNext(): Returns true if there are still elements to iterate over.

  • next(): Returns the next element of the iteration.

  • remove(): Remove the last object returned from the collection. (Optional operation)

The source code is as follows:

5.2 Pit in ArrayListIterator

The source code of ArrayListIterator is actually not difficult to understand, that is, it implements the three methods in Iterator.

But there is a pit, everyone needs to pay attention to, that is:

Whenever we use an iterator to traverse an element, if the content of the element is modified by a method other than the iterator (such as deleting an element), ConcurrentModificationExceptionan exception will be thrown .

Let me look at the phenomenon first, and then find the reason from the source code point of view.

Examples of error codes:

		ArrayList arrayList = new ArrayList();
        arrayList.add("a");
        arrayList.add("b");
        arrayList.add("c");

        System.out.println(" " + arrayList);
        Iterator<String> iterator = arrayList.iterator();
        while (iterator.hasNext()) {
            if ("c".equals(iterator.next())) {
                arrayList.remove("c");
            }
        }
        System.out.println(" " + arrayList);

        //for 
        //ConcurrentModificationException
        //for (Object o : arrayList) {
        //   arrayList.remove(o);
        //}
        //System.out.println(" 2 " + arrayList);
 

Error display:

Okay, we have seen the phenomenon, so now let's look at the cause of the error.

We must first understand the meaning of these variables:

Then let's take a look at what circumstances will report an error:

First analyze the reason for the error:

In our use of ArrayLis iterator()time method to get to the iterator to traverse, in the current state of the ArrayList will modCountbe assigned to ArrayListIteratorclasses of expectedModCountproperty.

If we are in an iterative process, using the ArrayList remove()method, then modCountit will add 1, but the iterator expectedModCountdoes not change, when we use an iterator next()when the method, it will be reported ConcurrentModificationExceptionfault.

Finally, let us compare ArrayListIteratorthe remove()methods and ArrayListtheir remove()different from the method to verify what the cause of error:

So the enlightenment we got is:

Whenever we use an iterator to traverse elements, we must use the iterator's own delete method, and cannot use methods other than the iterator to modify the content of the element, otherwise the values of expectedModCount and modCount will be inconsistent, and ConcurrentModificationExceptionan exception will be thrown .

In addition, we should also note that the enhanced for loop is actually an iterator used, so we should pay attention to the same problem.

Accumulate bit by bit, be yourself~