【 source code 解析】 undress ArrayList

A thousand miles kuibu, thousands of rivers; Make a little progress every day, and one day you’ll be a big shot.

In this paper, the content

Of course, there are more methods in ArrayList, but this article focuses on some common methods

Methods the variable

The main method variables in an Arraylist are the following

1. Construction method

1.1 Structure with parameters

1.1.1 Passing in the size of the array

1.1.1.1 Code implementation

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

Copy the code

1.1.1.2 Source code parsing

1.1.2 Pass a list object

This is essentially copying the data from the passed list object to the new ArrayList object

1.1.2.1 Code implementation

List<String> list=new ArrayList<>(Arrays.asList("z"."m"."h"));

Copy the code

The asList method from the Arrays utility class, which returns a List directly in the source code, will not be introduced here

1.1.2.2 Source code parsing

1.2 No-parameter structure

This one’s a little easier, just assign an empty array

1.2.1 Code implementation

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

Copy the code

1.2.2 Source code parsing

2. The add method

Add (E E) adds data to the end, and add(int index,E element) inserts the element at the specified position

2.1 the add (E, E)

This is the main method of Arrayist, and one of the most commonly used methods, so the source code is more complex and longer

2.1.1 Code implementation

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

list.add("Gray HK");

Copy the code

2.1.2 Source code parsing

• EnsureCapacityInternal (int minCapacity) ensures that the array is full

• calculateCapacity(Object[] elementData, int minCapacity)

• Go back toensureExplicitCapacity(int minCapacity)This method, this method firstThe number of changes is increased by 1And then judgesize+1Is the capacity larger than the current array capacity? If the capacity is larger than the current array capacity, expand the capacity to the original array capacity1.5 times

If size+1=2 and elementData.length=10, why is that equal to 10? Since the array is expanded from 0 to 10 by default the first time, size+1 is smaller than elementData.length, no expansion is performed

• Grow (int minCapacity) expansion

The arrays.copyof () method of arrays.copyof () is called for the replication operation. When we go further into this method, we find that the replication function is realized by the system.arrayCopy () method. This method is modified by the keyword native, which means that it is not implemented by the Java language, but generally c/ CPP

2.1.3 summary

At this point, the add method flow is complete, its core steps:

• Determine if the array is full each time you add an element

• The first time you add an element, expand the array to 10

• During the capacity expansion, except for the first time, each subsequent capacity expansion is 1.5 times the original size

• Call the system.arrayCopy () method after the expansion to copy the elements of the original array to the new expanded array

2.2 Add (int index, E element)

This method inserts an element at the specified position, and the position and all subsequent elements are moved back

2.2.1 Code implementation

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

list.add("hk");

list.add(0."Gray");

Copy the code

2.2.2 Source code parsing

As you can see, the system.arrayCopy () method is used again

• RangeCheckForAdd (int index) determines whether a line has been crossed

Here he is comparing with the size, not with the length of the array. Personally, I think this saves space first and facilitates the operation of moving behind

• System.arraycopy() copies an array

public static native void arraycopy(Object src,  int  srcPos,

                                     Object dest, int destPos,

                                    int length)

Copy the code

• SRC Specifies the array object
• SrcPos Start position of the original array
• Dest target array
• DestPos Start position of the destination array
• Length How many pieces of data to copy

2.2.3 summary

The main steps of the insert method are as follows:

• Check whether the insertion position is out of bounds
• Check whether the array capacity is sufficient. If not, perform operations related to expansion
• callSystem.arraycopy()forindexAnd the following elements are moved back

3. The get method

3.1 the get (int index)

3.1.1 Code implementation

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

list.add("hk");

list.get(0);

Copy the code

3.1.2 Source code parsing

• RangeCheck (int index) determines if the line is crossed

If I get an add method, I’m going to say index>=size, so I’m going to say index>=size, so I’m going to say index>=size. Because the array starts at 0, and size is the same thing as starting at 1

private void rangeCheck(int index) {

    if (index >= size)

        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

}

Copy the code

• ElementData (int index) directly returns the array element with the corresponding index

E elementData(int index) {

    return (E) elementData[index];

}

Copy the code

3.1.3 summary

Get method is relatively simple, the main steps are:

• Check for boundaries
• Return the corresponding element

4. Set method

4.1 Set (int index, E element)

4.1.1 Code implementation

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

list.add("hk");

list.set(0."Gray");

Copy the code

4.1.2 Source code parsing

5. The remove method

5.1 remove (int index)

5.1.1 Code implementation

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

list.add("hk");

list.remove(0);

Copy the code

5.1.2 Source code parsing

When the last element is deleted, numMoved is less than 0, and the element will not be moved

5.2 remove (Object o)

This method is rarely used in practice because AraryList can hold duplicate elements, so deleting is deleting the earliest element added

5.2.1 Code implementation

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

list.add("hk");

list.remove("hk");

Copy the code

5.2.2 Source code parsing

• FastRemove (int index) removes an element

This method is similar to the operation inside remove(int index), except it does not hold the deleted element

private void fastRemove(int index) {

    modCount++;

    int numMoved = size - index - 1;

    if (numMoved > 0)

        System.arraycopy(elementData, index+1, elementData, index,

                         numMoved);

    elementData[--size] = null; // clear to let GC do its work

}

Copy the code

6. The clear methods

6.1 the clear ()

6.1.1 Code implementation

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

list.add("hk");

list.clear();

Copy the code

6.1.2 Source code analysis

conclusion

System.arraycopy() is called when ArrayList is being expanded or moved. Arraycopy () is called when ArrayList is being expanded or moved. Arraycopy () is called when ArrayList is being expanded or moved.

The modCount++ operation appears several times in this article. This modCount is primarily an iterator of the user’s inner class