Java에서의 ArrayList 구현

Java 1.8

java.util.ArrayList

• 기본 배열 용량: 10개의 데이터

    public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    {
        private static final long serialVersionUID = 8683452581122892189L;
  
        /**
         * Default initial capacity.
         */
        **private static final int DEFAULT_CAPACITY = 10;**
  
            /**
         * Shared empty array instance used for empty instances.
         */
        private static final Object[] EMPTY_ELEMENTDATA = {};
  
        /**
         * Shared empty array instance used for default sized empty instances. We
         * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
         * first element is added.
         */
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  
        /**
         * The array buffer into which the elements of the ArrayList are stored.
         * The capacity of the ArrayList is the length of this array buffer. Any
         * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
         * will be expanded to DEFAULT_CAPACITY when the first element is added.
         */
        transient Object[] elementData; // non-private to simplify nested class access
  
        /**
         * The size of the ArrayList (the number of elements it contains).
         *
         * @serial
         */
        private int size;
    ...

  • elementData: 첫번쨰 요소가 추가될 때 기본적으로 DEFAULT_CAPACITY로 확장

• 삽입: add()

    /**
     * This helper method split out from add(E) to keep method
     * bytecode size under 35 (the -XX:MaxInlineSize default value),
     * which helps when add(E) is called in a C1-compiled loop.
     */
    private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }
  
    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        modCount++; // 리스트가 구조적으로 수정된 횟수
        add(e, elementData, size);
        return true;
    }
  

  • 데이터 개수가 배열 최대치보다 넘어가면 리스트 크기 확장

• 리스트 크기 확장: grow()

    private Object[] grow(int minCapacity) {
          return elementData = Arrays.copyOf(elementData,
                                             newCapacity(minCapacity));
      }
  
      private Object[] grow() {
          return grow(size + 1);
      }
    /**
     * Returns a capacity at least as large as the given minimum capacity.
     * Returns the current capacity increased by 50% if that suffices.
     * Will not return a capacity greater than MAX_ARRAY_SIZE unless
     * the given minimum capacity is greater than MAX_ARRAY_SIZE.
     *
     * @param minCapacity the desired minimum capacity
     * @throws OutOfMemoryError if minCapacity is less than zero
     */
    private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }
  
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE)
            ? Integer.MAX_VALUE
            : MAX_ARRAY_SIZE;
    }

  • 기존 크기의 1.5배의 새로운 배열을 생성 후, 기존의 데이터를 옮김
    (기존 배열은 가비지 컬랙터를 통해 삭제)

      💡 참고
      - Java에서 일반적으로는 기존 용량의 2배를 확장시킨다고 한다
      - 하지만,  Java 1.8버전에서는 기존 용량의 1.5배를 확장시킨다