This article is the first in a series of Java collections articles, which will start with a step-by-step analysis of the features and implementations of commonly used collections in Java, and then compare which collections should be used in different scenarios.

List

Let’s take a look at the concepts associated with List, the interface ArrayList implements.

• A List can be called an ordered collection or sequence, with elements accessed through an integer index
• Allow the same element to be inserted
• In general, null values are also allowed

A special iterator is also provided in the List interface: ListIterator

ListIterator

ListIterator was built specifically for lists and provides the ability to insert and replace elements and two-way access on top of Iterator. Let’s look at the usage:

List<String> list= new ArrayList<>();
list.add("1");
list.add("2");
list.add("Seven");
list.add("4");
ListIterator<String> iterator = list.listIterator();
while (iterator.hasNext()){
    String next = iterator.next();
    if(next.equals("Seven")){
        iterator.set("3");
        iterator.previous();
    }else{ System.out.println(next); }}Copy the code

ArrayList

Java native provides array data structures, but due to its own design has many problems, such as expansion, type insecurity, and not flexible enough, so most of the time, ArrayList can be used instead, there is no big difference in efficiency.

ArrayList is a resizable array implementation of the List interface.

The size, isEmpty, get, set, the iterator and a listIterator method calls are the execution time of the fixed time.

The ADD operation time is amortized constant time, the time required for adding n elements for O(n). Everything else is linear time.

The capacity parameter in the ArrayList describes the length of the array in the ArrayList. The add operation will expand capacity first, which is a time-consuming operation. If multiple Add operations are going to occur, you can call the ensureCapacity method before scaling to reduce the number of add operations and improve performance.

Note that ArrayList is non-thread-safe. In a multithreaded environment, if you want to modify its structure, you must synchronize. You can also use the wrapper method in Collections to get synchronized objects:

List list = Collections.synchronizedList(newArrayList(...) );Copy the code

Iterator and listIterator are also designed as fail-fast, and using Iterator in a multithreaded environment will throw an exception directly.

The default ArrayList length is 0, and the initial length can be set through the constructor.

The capacity expansion mechanism detects whether an element needs to be expanded each time it is added. The length added each time is half of the current length, which can be expanded to the specified length using the ensureCapacity method.

The source code

Let’s start with constructors

//ArrayList is an array of data stores
transient Object[] elementData;
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity); }}public ArrayList(a) {
    //DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the code

You can see that elementData has a default length of 0, and if you set the default length it will be initialized to an array of varying length.

Let’s look at the add method:

public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}
Copy the code

Note that the size field represents the actual length of the current ArrayList, not the length of elementData. The add method calls ensureCapacityInternal first, passing in the size+1 argument that does not represent the capacity expansion length, but the minimum capacity expansion length. The method then determines whether the array needs to be expanded based on whether there is room to add new elements.

//minCapacity = size + 1
if (minCapacity - elementData.length > 0)
        grow(minCapacity);
Copy the code

So if we look at how the expansion works, we can assume that since we’re using arrays internally to store data, but arrays are immutable, the most feasible solution would be to create a bigger array and copy the data into it, and we can see if we do that.

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // Move one to the right is equal to divisible by 2
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        //hugeCapacity returns a maximum value of integer.max_value
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the code

You can see that each expansion length is 50% of the current length + half of the current length. MAX_ARRAY_SIZE is integer. MAX_VALUE – 8. Generally, the array length cannot exceed this value, but integer. MAX_VALUE will be expanded if expansion continues.

Max_size = MAX_ARRAY_SIZE = MAX_ARRAY_SIZE = MAX_VALUE = array_size = MAX_VALUE = array_size = array_size = array_size = array_size = array_size = array_size = array_size Expanding the array length to integer. MAX_VALUE may cause an OutOfMemoryError.

Well, welcome everyone to pay attention to my public number, there are more exciting content: zhangke_blog