Skip to content

Latest commit

 

History

History
72 lines (60 loc) · 5.14 KB

25.md

File metadata and controls

72 lines (60 loc) · 5.14 KB

배열과 ArrayList, LinkedList 의 차이점은 무엇인가요?

  1. 배열 배열은 데이터가 메모리공간에서 연속적으로 위치합니다. 배열은 데이터들이 메모리에 인접하게 위치하고, 모든 데이터의 타입이 같다는 특징이 있습니다. 따라서 접근하고자 하는 데이터가 몇번째인지 인덱스만 알면 O(1)의 시간으로 접근이 가능합니다. 하지만 처음 배열을 할당할 때 전체 메모리 공간을 미리 할당해야하며 이 때문에 메모리 비효율적인 상황이 생깁니다. 배열은 데이터 조회시 시간 복잡도 O(1)이지만, 삽입/삭제 시 중간에 데이터를 넣거나 삭제하면 기존 데이터들을 이동시켜야 하므로 O(n)의 시간복잡도를 가진다.

  2. LinkedList 링크드리스트는 필요할 때마다 메모리를 동적할당하여 데이터를 추가하므로 필요한 데이터만큼만 사용한다는 장점이 있습니다. 그러나 데이터를 조회/삽입/삭제 시 대상 노드까지 한 노드씩 이동해야하므로 시간복잡도 O(n)을 가진다.

  3. ArrayList ArrayList는 배열의 인덱스 접근 장점은 살리고, 최초 할당된 고정 메모리를 사용해야 하는 단점은 극복한 자료구조이다. 데이터의 개수가 많아지거나 적어질 때 배열의 크기를 늘리거나 줄여서 데이터의 개수에 맞춰 내부 배열의 크기를 변경한다.

        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);

자바에서는 ArrayList의 처음 디폴트 사이즈는 10이고 그 후 필요할 때마다 1.5배씩 늘어난다.

질문

1. 배열은 삽입, 삭제 시 중간에 데이터를 넣거나 삭제하면 O(n)이라고 했는데 이를 좀 더 설명해주세요.

처음에 배열에 [1, 2, 3, 4, ] 이런식으로 데이터가 있는데 중간에 5를 넣는다고 가정해보겠습니다. 그러면 [1, 2, 5, 3, 4]가 되는데 3과 4가 한칸씩 밀려났습니다. 이 밀려나는 과정에서 다음 인덱스로 데이터를 덮어쓰게 됩니다. 따라서 시간 복잡도 O(n)을 가지게 됩니다.

2. LinkedList랑 ArrayList랑 각각 어떤 장단점이 있나요? 언제 어떤 자료구조를 써야하나요?

LinkedList의 경우 필요한만큼의 데이터 공간만 할당해서 사용할 수 있다는 장점이 있습니다. ArrayList의 경우 비록 크기가 동적이기는 하지만 항상 할당된 크기 딱 맞게 사용한다는 보장이 없으므로 할당받고 사용하지 않는 메모리 공간이 있을 수 있습니다. 하지만 배열이므로 인덱스로 접근시 성능이 좋다는 장점이 있습니다.

또한 LinkedList의 경우 조회를 할 때 시간이 많이 걸리지만 제일 뒤에 순차적으로 데이터를 저장할 때는 O(1)의 시간을 보장합니다. 그럴 경우에는 LinkedList를 사용하는게 좋을 수도 있습니다. 데이터의 조회/삽입 등의 비율까지 고려해서 상황에 맞게 사용을 해야할 것 같습니다.

3. 자바의 ArrayList는 어떻게 Concurrent 문제를 감지할까요?

/**
     * The number of times this list has been <i>structurally modified</i>.
     * Structural modifications are those that change the size of the
     * list, or otherwise perturb it in such a fashion that iterations in
     * progress may yield incorrect results.
     *
     * <p>This field is used by the iterator and list iterator implementation
     * returned by the {@code iterator} and {@code listIterator} methods.
     * If the value of this field changes unexpectedly, the iterator (or list
     * iterator) will throw a {@code ConcurrentModificationException} in
     * response to the {@code next}, {@code remove}, {@code previous},
     * {@code set} or {@code add} operations.  This provides
     * <i>fail-fast</i> behavior, rather than non-deterministic behavior in
     * the face of concurrent modification during iteration.
     *
     * <p><b>Use of this field by subclasses is optional.</b> If a subclass
     * wishes to provide fail-fast iterators (and list iterators), then it
     * merely has to increment this field in its {@code add(int, E)} and
     * {@code remove(int)} methods (and any other methods that it overrides
     * that result in structural modifications to the list).  A single call to
     * {@code add(int, E)} or {@code remove(int)} must add no more than
     * one to this field, or the iterators (and list iterators) will throw
     * bogus {@code ConcurrentModificationExceptions}.  If an implementation
     * does not wish to provide fail-fast iterators, this field may be
     * ignored.
     */
    protected transient int modCount = 0;

        private void checkForComodification() {
            if (root.modCount != this.modCount)
                throw new ConcurrentModificationException();
        }

내부 구현을 보면 modCount라는 것을 가지고 있습니다.

checkForComodification()에서 modCount를 체크하는데 만약 for-each 문을 돌다가 사이즈가 변경하는 코드가 있거나, 다른 스레드가 크기를 변경하면 예외를 발생시킵니다.