소스 읽기 - ArrayList

0. ArrayList는 무엇입니까?

동적 배열

1. 실현의 본질

동적 수조의 본질은 당연히 수조이다

2. 상용 인터페이스

2.1 구조 함수

참조가 없을 때 빈 그룹을 만들고 처음 저장할 때 10 크기의 그룹을 만듭니다

초기 용량을 지정하고 지정된 크기의 배열을 생성

매개 변수는 Collection 대상이고 대상 크기의 그룹을 만들고 대상을 복사

2.2 add 방법

4가지 방법이 있어요.

public boolean add(E e)
public void add(int index, E element)
public boolean addAll(Collection extends E> c)
public boolean addAll(int index, Collection extends E> c)

절차는 모두 유사하다

용량이 충분하지 않을 경우 1.5배 확장하여 원래 데이터를 복사

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    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);
}

삽입하면 목표 위치 뒤의 데이터를 뒤로 이동한 다음에 새로운 데이터를 추가합니다. 그렇지 않으면 새로운 데이터를 직접 연결합니다.

/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return true (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

2.3 get 메서드

직접 값

2.4 remove 방법

3개의remove 방법

public E remove(int index)
public boolean remove(Object o)
public boolean removeAll(Collection> c)

앞의 두 가지는 매우 간단하다. 원소를 삭제한 후에 뒤의 원소를 대량으로 앞으로 옮긴다. 주의해야 할 것은 remove(Ojbect o)할 때 사용하는 방법equals()이다. 기본 비교를 다시 쓰지 않은 것은 인용이고 주로 세 번째를 본다.

/**
 * Removes from this list all of its elements that are contained in the
 * specified collection.
 *
 * @param c collection containing elements to be removed from this list
 * @return {@code true} if this list changed as a result of the call
 * @throws ClassCastException if the class of an element of this list
 *         is incompatible with the specified collection
 * (optional)
 * @throws NullPointerException if this list contains a null element and the
 *         specified collection does not permit null elements
 * (optional),
 *         or if the specified collection is null
 * @see Collection#contains(Object)
 */
public boolean removeAll(Collection> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

private boolean batchRemove(Collection> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

그룹을 옮겨다니며, 집합을 제거할 필요가 없는 요소를 그룹의 시작 부분에 다시 배열합니다.쉽게 말하면 제거할 필요가 없는 원소를 다시 배열하는 것이다.스케줄러:표식을 연상하다니-정리??finally 부분에서 한 가지 조작은 다 훑어보지 못했을 수도 있다는 것이다contains 방법은 이상을 던지고 뒤에 있는 것은 상관하지 않고 수조 뒤에 직접 연결한다.

2.5 Iterator 스트리밍

Array List에 대한 수정 작업이 있을 때마다modCount가 수정 횟수를 기록하고 Iterator 작업에서 이 값을 검사하여 ConcurrentModificationExceptionListItr 계승Itr을 던지고 ListIterator 인터페이스를 실현할 수 있습니다.ListIterator는 Iterator보다 앞을 옮겨다니며 추가하고 수정하는 기능이 많다.

참고 자료

ArrayList 소스build 1.8.0_121-b13 버전

https://www.cnblogs.com/java-zhao/p/5102342.html

https://blog.csdn.net/u013309870/article/details/72519272

https://blog.csdn.net/ljcitworld/article/details/52041836