List source code analysis

Let's take a look at the Collection. List is a sub interface of the Collection, mainly to see several classes under it.

1,AbstractList

2,ArrayList

3,Collections.synchronizedList

4,Vector

5,LinkedList

6,CopyOnWriteArrayList

1, AbstractList

This is an abstract class, which is the basic class for implementing the List interface. ArrayList, LinkedList and Vector all inherit this abstract class.

1> If you want to implement an immutable list, you must implement the get(int) and size() methods

2> If you want to implement a modifiable list, you must implement set(int,E). If the size of the list is variable, you must also implement the add(int,E) and remove(int) methods

It has two built-in iterators, Itr and ListItr. The inheritance relationship is as follows

 

(1)Itr

private class Itr implements Iterator<E> {
    //cursor
    int cursor = 0;
    
    //The current index value of the subscript when the next method is called
    //, reset to - 1 if the remove method is called  
    int lastRet = -1;

    //The number of times the list has been modified, such as adding, deleting, modifying, and expanding
    int expectedModCount = modCount;
    //Are there any elements
    public boolean hasNext() {
        return cursor != size();
    }
    //Returns the next element
    public E next() {
        checkForComodification();
        try {
            int i = cursor;
            //The get method calls the concrete implementation class
            E next = get(i);
            lastRet = i;
            cursor = i + 1;
            return next;
        } catch (IndexOutOfBoundsException e) {
            checkForComodification();
            throw new NoSuchElementException();
        }
    }
    //Delete current element 
    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();
        try {
            AbstractList.this.remove(lastRet);
            if (lastRet < cursor)
                cursor--;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException e) {
            throw new ConcurrentModificationException();
        }
    }
    //Check whether the list structure has been modified by other threads during iteration 
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

  

 

(2)ListItr

private class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {
        cursor = index;
    }

    public boolean hasPrevious() {
        return cursor != 0;
    }
    //Returns the previous element
    public E previous() {
        checkForComodification();
        try {
            int i = cursor - 1;
            E previous = get(i);
            lastRet = cursor = i;
            return previous;
        } catch (IndexOutOfBoundsException e) {
            checkForComodification();
            throw new NoSuchElementException();
        }
    }

    public int nextIndex() {
        return cursor;
    }

    public int previousIndex() {
        return cursor-1;
    }
    //Set value
    public void set(E e) {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();
        try {
            AbstractList.this.set(lastRet, e);
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
    //Add element
    public void add(E e) {
        checkForComodification();
        try {
            int i = cursor;
            AbstractList.this.add(i, e);
            lastRet = -1;
            cursor = i + 1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}

  

These two iterators are called in the indexOf, lastIndexOf, and removarange methods

For example, the removehange method

protected void removeRange(int fromIndex, int toIndex) {
    //Get iterator, fromIndex namely Itr Inside cursor 
    ListIterator<E> it = listIterator(fromIndex);
    for (int i=0, n=toIndex-fromIndex; i<n; i++) {
        it.next();
        it.remove();
    }
}

public ListIterator<E> listIterator(final int index) {
    rangeCheckForAdd(index);
    return new ListItr(index);
}

private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            cursor = index;
        }
}

 

2, ArrayList

This list is the most commonly used. It inherits from AbstractList. It is non thread safe. Concurrent modificationexception will be thrown under multithreading

 

(1) The default capacity is 10

 private static final int DEFAULT_CAPACITY = 10;

  

(2) The underlying data structure is an Object array

transient Object[] elementData;

  

(3) The capacity expansion mechanism is that the capacity expansion is 1.5 times of the current capacity. See the add method

public boolean add(E e) {
      //The key is the method 
      ensureCapacityInternal(size + 1);  
      elementData[size++] = e;
      return true;
  }

  

Look at the ensureCapacityInternal method for capacity expansion

private void ensureCapacityInternal(int minCapacity) {
      ensureExplicitCapacity(
          calculateCapacity(elementData, minCapacity)
        );
  }

  

Let's first look at the calculateCapacity method

private static int calculateCapacity(Object[] elementData, int minCapacity) { 
      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
          return Math.max(DEFAULT_CAPACITY, minCapacity);
      }
      return minCapacity;
 }

  

If no size is specified when creating the list, the maximum is taken from minCapacity and default capacity. Otherwise, minCapacity is returned directly

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        //If minCapacity is greater than the current array length, the capacity will be expanded
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

  

The core method of capacity expansion is the growth (mincapacity) method.

private void grow(int minCapacity) {

    //Current capacity
    int oldCapacity = elementData.length;
    //New capacity, 1.5 times the current capacity 
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

  

It can be seen that the capacity after expansion is 1.5 times of the current capacity

3, Collections synchronizedList

The List obtained with Collections is thread safe, and it is locked on the code block with the synchronized keyword. The specific initial capacity and expansion depends on what kind of List is passed in

 

The returned list is synchronized randomaccesslist or synchronized list, and synchronized randomaccesslist is a subclass of synchronized list

 

Therefore, we mainly look at the Synchronized list. We can see that all methods of this class are locked with Synchronized.

 

4, Vector

Vector is rarely used. It is also a subclass of AbstractList.

(1) The default capacity is 10

public Vector() {
    //Call another constructor  
    this(10);
}

  

The above default empty construction calls the following construction method, which sets capacityIncrement to 0, which is useful in capacity expansion

 

You can also initialize capacity and capacityIncrement with the following structure

 

(2) The underlying data structure is an Object array

protected Object[] elementData;

  

(3) The capacity expansion mechanism is 2 times by default. You can also manually set capacityIncrement capacity expansion

 

(4) Thread safe, lock the method with Synchronized

 

5, LinkedList

The linked list structure is as follows. In addition to inheriting AbstractList, it also implements Queue.

 

(1) The underlying implementation is a Node by Node. There are references of front and rear nodes in the Node, which can be connected into a chain

 

6, CopyOnWriteArrayList

This is more awesome. Its Chinese name is copy when writing. Belonging to JUC and contracting, thread safety is a variant of ArrayList.

 

(1) Initialization is an Object array with a capacity of 0

public CopyOnWriteArrayList() {   
  setArray(new Object[0]);
}

  

This array uses volatile to ensure variable memory visibility.

 private transient volatile Object[] array;

  

(2) Use ReentrantLock (recursive lock, also known as reentrant lock) to lock, expand the capacity to add 1 to the capacity once, and then use arrays Copyof copies the old array into the new array, which consumes more memory.

 

=======================================================

I'm Liusy, a programmer who likes fitness.

Welcome to follow the wechat official account [Liusy01], exchange Java technology and fitness together, and get more dry goods.

Tags: Java

Posted by sm on Sat, 14 May 2022 02:07:29 +0300