자바 ArrayList 공부

 

https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html

ArrayList (Java Platform SE 8 )

 

Array List 주석

Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector, except that it is unsynchronized.)

 

배열 사이즈가 조정가능한 리스트 인터페이스 구현체이다.  null을 포함한 모든 요소들을 허용하는 모든 리스트 기능 작동 구현을 한다. 

추가적으로 리스트 인터페이스를 구현하는 것 외에도 클래스는 내부적으로 저장되는 배열의 크기의 사이즈 조정 기능을 제공한다. (Vector와 거의 비슷하지만 unsynchronized 하다는 것이 차이다)

 

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.

 

 리스트의 size, isEmpty, get, set, iterator, 반복자 기능들은 상수시간으로 작동한다.  add 기능은 상각시간으로 작동하며 n개의 원소를 추가하는데 O(n)의 시간이 발생한다. 대략 다른 작동들도 linear 한 시간으로 작동한다. 링크드리스트와 비교했을때 상수 요소가 낮다.

 

Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.
An application can increase the capacity of an ArrayList instance before adding a large number of elements using the ensureCapacity operation. This may reduce the amount of incremental reallocation.

 

각각의 ArrayList 객체는 용량을 갖는다. 여기서 용량이란 배열의 저장되는 사이즈를 말한다. 항상 이것은 리스트 사이즈와 최소 크기와 크거나 같다. ArrayList에 요소가 추가될때마다 용량은 자동적으로 늘어단다. 증가 정책은 원소를 추가하는 것이 상각시간에 어긋나지 않는 다는 것외에는 설명되어 있지 않다.  application에서 매우 많은 수를 추가하기전에  ensureCapacity operation 을 통해 ArrayList의 용량을 증가할 수 있다. 이것을 통해 재할당의 양을 감소시킬 수 있다.

 

Note that this implementation is not synchronized. If multiple threads access an ArrayList instance concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more elements, or explicitly resizes the backing array; merely setting the value of an element is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the list. If no such object exists, the list should be "wrapped" using the Collections.synchronizedList method. This is best done at creation time, to prevent accidental unsynchronized access to the list:
     List list = Collections.synchronizedList(new ArrayList(...));

 

중요한 것은 구현체가 synchronized되지 않는 다는 것이다. 만약 멀티 스레드에서 ArrayList 객체에 동시적으로 접근하게 되고, 최소 하나의 스레드가 list를 구조적으로 변경하게 되면 외부적으로는 synchronized해야한다. 구조적 변경은 원소의 추가나 삭제 또는 배열의 크기 조정을 말한다. 보통 이러한 객체의 synchronizing 작업은 list를 캡슐화하는 것이다. 그런한 기능이 없다면 List가 Collections.synchronizedList 의 기능을 통해 wrapped를 하는 것이다. 이게 최선으로 생성시간과 unsynchronized된 접근으로 부터 보호를 할 수 있다. 

     List list = Collections.synchronizedList(new ArrayList(...));

으로 사용한다.

 

The iterators returned by this class's iterator and listIterator methods are fail-fast: if the list is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

 

클래스의 반복자와 리스트 반복기능가 반환하는 반환자는  fail-fast를 리턴한다. 리스트가 생성되고 이후 리스트가 가진 제가나 추가 기능이 아닌 형태로 구조적으로 변경되면  ConcurrentModificationException 를 던진다. 반복자가 빠르고 깔끔하게 실패를 하기때문에 미래에 위험한 행동이나 분명하지 않은 시간의 작동을 감수하지 않는다.

Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

 

중요한 것은 일반적으로 반복자의 fast-fail 행위는 일반적으로 동기화되지 않은 동시성 수정이 있을 때 확실한 보장을 하는 것이 불가능하기 때문이다. Fail-fast 은 최선을 다해 ConcurrentModificationException을 발생시킨다. 따라서 정확성을 위해 ConcurrentModificationException 예외에 의존하는 프로그램을 작성하는 것은 잘못된 것이다. 반복자의 fail-fast은 버그를 감지하는 데만 사용해야 한다.

생성자

//Constructs an empty list with an initial capacity of ten.
    public MyList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    public MyList(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);
        }
    }

배열의 크기가 지정되지 않으면 10개의 크기로 생성이 된다.

초기 배열 값이 들어오면 값이 세팅되며 잘못된 값이 들어오면 IllegalArgumentException 예외를 던진다.

   public MyList(Collection<? extends E> c) {
        Object[] a = c.toArray();
        if ((size = a.length) != 0) {
            if (c.getClass() == ArrayList.class) {
                elementData = a;
            } else {
                elementData = Arrays.copyOf(a, size, Object[].class);
            }
        } else {
            // replace with empty array.
            elementData = EMPTY_ELEMENTDATA;
        }
    }

컬렉션이 들어올 수 있다. 컬렉션이 들어오면 배열로 변경하고 사이즈 여부를 체크한다.

ArrayList클래스라면 들어온 값으로 세팅 아니라면 Array 복사를 통해 값을 넣는다.

빈 사이즈 컬렉션이면 빈값으로 세팅된다.

 

- trimToSize 

: 배열의 사이즈가 내부 크기 보다 크면 배열 크기를 내부 크기로 조절한다.

 public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

- ensureCapacity

필요하다면 현재 ArrayList의 용량을 증가한다. 최소한 인자로 들어오는 크기만큼 받을 수 있도록 용량을 조절한다.

 public void ensureCapacity(int minCapacity) {
        if (minCapacity > elementData.length
                && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
                && minCapacity <= DEFAULT_CAPACITY)) {
            modCount++;
            grow(minCapacity);
        }
    }

현재 배열의 크기보다 인자로 받은 최소 용량 크게되면(디폴트 용량인 값보다 최소 용량이 크면) modCount를 늘리고

grow를 호출해 크기를 늘린다.

 

    private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,
                newCapacity(minCapacity));
    }

    private Object[] grow() {
        return grow(size + 1);
    }

newCapacity는 용량 조절 메서드다.

 

 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

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);
    }

새로운  용량이 MAX_ARRAY_SIZE보다 크다면 hugecapacity를 호출한다.

 

 private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE)
            ? Integer.MAX_VALUE
            : MAX_ARRAY_SIZE;
    }

Integer.MAX_VALUE로 두고나 Integer.MAX_VALUE - 8값으로 둔다.

 

 public int size() {
        return size;
    }

    /**
     * Returns {@code true} if this list contains no elements.
     *
     * @return {@code true} if this list contains no elements
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * Returns {@code true} if this list contains the specified element.
     * More formally, returns {@code true} if and only if this list contains
     * at least one element {@code e} such that
     * {@code Objects.equals(o, e)}.
     *
     * @param o element whose presence in this list is to be tested
     * @return {@code true} if this list contains the specified element
     */
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

 

- indexOf

: 처음으로 발견하는 인덱스의 위치를 리턴한다. 없으면 -1을 리턴한다.

 public int indexOf(Object o) {
        return indexOfRange(o, 0, size);
    }

    int indexOfRange(Object o, int start, int end) {
        Object[] es = elementData;
        if (o == null) {
            for (int i = start; i < end; i++) {
                if (es[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = start; i < end; i++) {
                if (o.equals(es[i])) {
                    return i;
                }
            }
        }
        return -1;
    }

사이즈는 알고 있기때문에 사이즈만큼 반복하며 값을 찾는 것이다.

 

-lastIndexOf

: 마지막으로 나타나는 요소의 위치를 리턴하고 없으면 -1을 리턴한다.

 

    public int lastIndexOf(Object o) {
        return lastIndexOfRange(o, 0, size);
    }

    int lastIndexOfRange(Object o, int start, int end) {
        Object[] es = elementData;
        if (o == null) {
            for (int i = end - 1; i >= start; i--) {
                if (es[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = end - 1; i >= start; i--) {
                if (o.equals(es[i])) {
                    return i;
                }
            }
        }
        return -1;
    }

-clone

: ArrayList의 얕은 복사를 하여 리턴한다.

 

 public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }

 

- toArray()

   @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

 

 

    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

    @SuppressWarnings("unchecked")
    static <E> E elementAt(Object[] es, int index) {
        return (E) es[index];
    }

 

-get

    /**
     * Returns the element at the specified position in this list.
     *
     * @param  index index of the element to return
     * @return the element at the specified position in this list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
        Objects.checkIndex(index, size);
        return elementData(index);
    }

get 사용시 checkIndex를 통해 인덱스를 검증한다.

   @HotSpotIntrinsicCandidate
    public static <X extends RuntimeException>
    int checkIndex(int index, int length,
                   BiFunction<String, List<Integer>, X> oobef) {
        if (index < 0 || index >= length)
            throw outOfBoundsCheckIndex(oobef, index, length);
        return index;
    }

 

set

   public E set(int index, E element) {
        Objects.checkIndex(index, size);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

 

add

  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;
    }

    public void add(int index, E element) {
        rangeCheckForAdd(index);
        modCount++;
        final int s;
        Object[] elementData;
        if ((s = size) == (elementData = this.elementData).length)
            elementData = grow();
        System.arraycopy(elementData, index,
                elementData, index + 1,
                s - index);
        elementData[index] = element;
        size = s + 1;
    }

    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

add(e)의 경우 내부 add 함수를 사이즈와 함께 호출한다. 

사이즈가 가득 차게 되면 배열의 크기를 늘린다.

 

인덱스와 함께 add를 할경우 Array 복사를 통해 진행한다.