preface

ArrayList is often the most frequently used List implementation class in business scenarios and daily development, due to its structure and features. ArrayList is, as its name implies, an array implementation, so the query time complexity is constant, and with some minor optimizations, the query is faster. Because of its underlying array implementation, both inserts and deletes are O (n) level. Business scenarios tend to be more read than written, so ArrayList is a good fit. Here’s a look at the source code of ArrayList and the implementation of common methods

  • This article is based on JDK8

The body of the

1. Member variables

Let’s look at its member variables first

  • DEFAULT_CAPACITY = 10: The default capacity is 10, used to initialize the array size when the first element is added to the add method
  • EMPTY_ELEMENTDATA = {}, DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {} : Empty array for capacity expansion
  • ElementData: The array that actually holds the elements
  • Size: number of elements contained

2. Debug source code

2.1 Inserting Elements

I’ll start by debugging the insert process of the Add method with test code, because it’s easy to see what happens when you look at adding elements, member variables, and constructors

import java.util.ArrayList;
public class Test {
    public static void main(String[] args) {
        ArrayList<Object> objects = new ArrayList<>();
        objects.add(1);
        objects.add("qweqweqweqwe");
        objects.add(3);
        objects.add(4);
        objects.add(5);
        objects.add(6);
        objects.add(7);
        objects.add(8);
        objects.add(9);
        objects.add(10);
        objects.add(11); System.out.println(objects.size()); }}Copy the code

The breakpoint is followed by new ArrayList(), which is its default constructor

  • As you can see, the elementData array is initialized. DEFAULTCAPACITY_EMPTY_ELEMENTDATA is the empty array member variable described above

Then we go to the second one and add the first element

There is a small optimization that adds elements between -128 and 127 to the cache to improve query efficiency for frequently used elements

Then you go to the Add method

The ensureCapacityInternal method on the first line of the Add method, as the name suggests, is a way to make sure that you don’t overstep the bounds of adding elements. Of course, the expansion method is included, as described below

As you can see, the first time this method adds an element, it expands its capacity to the default value of the above member variable, 10

  • MinCapacity indicates the minimum capacity required

The expansion is then performed using the grow method. If the above is the preparation for expansion, this is the real expansion method

Since this is the first expansion, the following arrow will be used

Notice the bit operation on the second line of the method, moving the arithmetic to the right by one is the same as dividing by two, so the new capacity calculated by the whole line of code is 1.5 times the old capacity

In the last line, the capacity of elementData is newCapacity, initialized to 0 for use. CopyOf method example

public class Test2 {
    public static void main(String[] args) {
        int[] arr={1.2.3.4.5};
        int[] ints = Arrays.copyOf(arr, 10);
        for (int i : ints) {
            System.out.println(i); //1 2 3 4 5 0 0 0 0 0}}}Copy the code

After performing the expansion, it is time to add elements, which is how the first element is added

For the second element, I chose a string, just to demonstrate that infrequent (large) strings are not cached. And of course I’m going to have capacity 10, size=1, and I’m going to go to ensureCapacityInternal and check if I have enough space, and I’m not going to expand

There is no further expansion until the tenth element is added

The eleventh element, since it has a capacity of ten, will be expanded. Based on the above bit expansion method, the new capacity should be 15, as shown below

At this point, the add method will be demonstrated, summed up a routine, or very simple

  • The default constructor is first called to initialize an empty array of length 0
  • Adding the first element uses the default member variable DEFAULT_CAPACITY=10 for capacity expansion
  • Continue adding elements, check for capacity, and add if there is enough
  • If the capacity is insufficient, expand the capacity by 1.5 times

2.2 Deleting Elements

There are two types of deleted elements

  • Remove (Object O) : If the argument is an Object, such as a string, iterate to remove the first matching element
  • Remove (int index) : deletes the subscript element if the parameter is an integer

First take a look at remove(Object O) source code

As you can see, whether you pass NULL or not, you iterate through the array, find the first element that matches, delete it, and return it. Deleting an element calls the fastRemove() method

FastRemove () source code

We know that if we delete one element in the array, we have to move all the elements that follow, so the time is order n.

The arrayCopy method in the following code is used to move array elements, with the parameters:

  • SRC: source array
  • SrcPos: The starting position from which the source array is copied
  • Dest: destination array
  • DestPos: indicates the starting position of the destination array
  • Length: indicates the length of the replication. NumMoved is calculated here

The entire deletion logic is to copy all elements following index one bit ahead, and then set the last element to NULL, which is automatically collected by GC

In accordance with the subscript to delete elements in much the same way, the source code is as follows, here is no longer described

3. Iterator for ArrayList

Before looking at the iterator source code, also write test code for debugging

public class TestListIterator {

    public static void main(String[] args) {
        ArrayList arrayList = new ArrayList();
        for (int i = 0; i < 10; i++) {
            arrayList.add(i);
        }

        Iterator<Integer> iterator = arrayList.iterator();
        while(iterator.hasNext()) { System.out.println(iterator.next()); iterator.remove(); }}}Copy the code

3.1 Construction method of iterator

As you can see, the iterator() method returns an iterator object

The constructor will initialize some member variables as follows

// cursor, which is used to traverse the collection and +1 each time the next() method is called
int cursor;       
// The index of the element to return is always 1 less than the cursor in the case of just traversing the collection. The iterator deletion method is also useful
int lastRet = -1; 
// Check whether the data is abnormal in multithreading
int expectedModCount = modCount;
Copy the code

3.2 next () method

The modCount variable encountered above but not explained is mentioned here. The addition of ArrayList and deletion of modCount are all +1, which feels like the number of operations, and it is easy to imagine that this is to handle exceptions in multithreading. Debug the test code posted above and analyze the iterator source code

The first is the hasNext() method, which has nothing to say, but does one of the functions of a cursor

Next comes the next() method, which first calls checkForComodification() to check whether the collection has been modified. As mentioned earlier, when the constructor initializes, it assigns the modCount value to the expectedModCount, and if the collection is modified by another thread during the traversal, the modCount value changes, so the following method throws an exception. Of course, single threads can also cause the following exceptions, which are described below

The next() method is simple, simply calling the cursor +1 each time and returning the element under the current (lastRet) index

3.3 the remove () method

If you look at the first line of the try statement, it will call remove of the ArrayList, which, as described above, is actually the final call to the System. arrayCopy method, which moves the element after lastRet one bit forward and assigns the value of null to the last element, which is collected by the GC

After that, lastRet assigns -1. Why -1? So this raises the question, can I call remove twice in one loop?

Finally expectedModCount = modCount, because call the ArrayList. Remove (), modCount must change, so you want to copy, otherwise it will throw ConcurrentModificationException. That is why the iterator cannot call list. Remove the reason, because the list of the remove not modify iterator expectedModCount member variable, will throw ConcurrentModificationException, Therefore, this exception can also occur if a single thread operation is not performed properly

So what happens when we call iterator.remove twice in one loop?

Because lastRet is -1 after the first remove, it will throw an exception. In the next() method, the value of lastRet, the previous value of the cursor, is updated, so the remove method is usually called after the next() method

4. Thread-safe Vector

Vector is no longer recommended because the logic is very similar to ArrayList and the underlying layer is also an array. Here’s a quick comparison. From the source

  • Vector’s add and delete methods are modified with synchronized and thus thread-safe
  • Its expansion method, each time to double the original expansion