android ArrayList

ArrayList 는 동적 배열 기반

 @Override 
public boolean add(E object) {
     Object[] a = array;
     int s = size;
     if (s == a.length) {
        Object[] newArray = new Object[s +
            (s < (MIN_CAPACITY_INCREMENT / 2) ?
            MIN_CAPACITY_INCREMENT : s >> 1)];
     System.arraycopy(a, 0, newArray, 0, s);
     array = a = newArray;
     }
     a[s] = object;
     size = s + 1;
     modCount++;
     return true;
}

만약dd 방법으로 데이터를 늘리는 것을 사용한다면 기본 길이는 12입니다

 private static final int MIN_CAPACITY_INCREMENT = 12;

용량에 미치지 못하면 용량이 50% 정도 증가한다.

s+s>>1

그래서 용량의 길이 변화는 0, 12, 18, 27, 40...이렇게 유추하면 (구체적인 값이 반드시 그렇지는 않다.addAll 방법이 존재하기 때문에 둘을 동시에 사용하면 그렇지 않다.) 확장된 후에 원래의 데이터가 System을 통과했다고 말할 것이다.array copy는 new Array에 복사합니다. 그러면 new Array는 확장된 후 원래 데이터가 있는 새로운 그룹입니다. 그 다음에 변수array에 값을 부여해서 다음에 사용하도록 합니다.
그러나ddAll 방법을 사용할 때 기존 그룹의 나머지 용량이 새 데이터의 길이보다 작으면 확장됩니다. 이번에 그 기수는 기존 그룹의 데이터 길이와 새 데이터의 길이입니다.

@Override public boolean addAll(Collection extends E> collection) {
     Object[] newPart = collection.toArray();
     int newPartSize = newPart.length;
     if (newPartSize == 0) {
         return false;
     }
     Object[] a = array;
     int s = size;
     int newSize = s + newPartSize; // If add overflows, arraycopy will fail
     if (newSize > a.length) {
         int newCapacity = newCapacity(newSize - 1);  // ~33% growth room
         Object[] newArray = new Object[newCapacity];
         System.arraycopy(a, 0, newArray, 0, s);
         array = a = newArray;
     }
     System.arraycopy(newPart, 0, a, s, newPartSize);
     size = newSize;
     modCount++;
     return true;
}

 private static int newCapacity(int currentCapacity) {
     int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?
             MIN_CAPACITY_INCREMENT : currentCapacity >> 1);
     return currentCapacity + increment;
}

이 원본 코드에 적힌 주석은 33% 정도 증가했지만 저는 50% 정도 증가한 것 같습니다. 1만 줄였기 때문에currentCapacity+currentCapacity>>> 1을 실행했습니다. 저도 몇 개의 숫자를 시도해 봤는데 이increment 값은 기본적으로 50% 정도입니다.
remove 방법이 사용하는 원리는 index 이후의 데이터를 한 부 복사하여 원래의 수조에 넣는 것이다. 이 데이터가 저장된 시작 위치는 원래의 index이다. 복사가 끝난 후에 마지막 자리를 비운다. (이곳의 마지막 자리는 전체 수조의 마지막 자리가 아니라 끝에 있는 데이터를 비운다)

@Override 
public E remove(int index) {
     Object[] a = array;
     int s = size;
     if (index >= s) {
         throwIndexOutOfBoundsException(index, s);
     }
     @SuppressWarnings("unchecked") E result = (E) a[index];
     System.arraycopy(a, index + 1, a, index, --s - index);
     a[s] = null;  // Prevent memory leak
     size = s;
     modCount++;
     return result;
}

remove 방법은 기존 데이터의 길이를 바꾸지 않습니다