ArrayList vs LinkedList 차이

public class ArrayList<E> {
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

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

ArrayList는 3개의 생성자가 존재한다.

 

• 아무 것도 매개변수로 받지 않는 생성자
• 초기 용량을 매개변수로 받는 생성자
• Collection 타입을 매개변수로 받는 생성자

 

ArrayList 내부 코드를 보면 초기 디폴트 크기는 10으로 명시되어 있다.

 

private static final int DEFAULT_CAPACITY = 10;

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

여기서 10을 더 늘리면 어떻게 될까?

public class ArrayList<E> {
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

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

 

grow 라는 메서드만 주목하자

결론적으로 10개이상일때 Array.copyOf(elementData, newCapacity); 을 통해 기존 배열의 원소들을 복사를 한다.

 

 

ArrayList 대표적인 메서드

 

1.  Add(E element) : 원소 마지막에 추가 

2. Add(int index, E element) : 원소를 원하는 index에 추가 

 - 예시를 들어보자 3번째 index까지 저장되어 있는 list가 있는데 2번째 값에 추가를 하고 싶어한다 그럼 Add(2, "test"); 이렇게 코드를 짜야한다. 그럼 뒤에 있는 값은 전부 밀려야 자리가 생기는거라 시간이 많이 걸리게 됩니다.

3. remove(int index) : 원소 삭제

 - 마지막 원소는 삭제가 쉬우나 중간에 있는 빈공간은 다시 채워야해서 비효율적

4. get(int index) : index로 해당 원소 가져오기  

 -  인덱스로 가져와서 탐색은 매우 유리하다.

 

 

ArrayList

탐색은 빠르나

중간에 insert, delete 가 빈번하게 일어나면 효율이 좋지 않다.

index 중간에 있는 값을 찾아서 추가, 삭제가 빈번하게 일어나면 비효율적이다.

 

 

 

 

LinkedList는 ArrayList와 다르게 인덱스를 통해서 검색을 하는 것이 아니라

Head에서 부터 해당 원소 까지 검색해야 하기 때문에 O(n)에 찾을 수 있습니다.

 

 

 

 

 

성능 차이의 결론

• 순차적으로 추가/삭제하는 경우에는 ArrayList가 LinkedList보다 빠르다.
  • 단순히 저장하는 시간만을 비교할수록 하기 위해서 ArrayList에서 배열 재배치가 일어나는 상황은 제외하였습니다. 그렇다면 순차적으로 삭제한다는 것은 마지막 데이터부터 삭제할 경우 각 요소들의 재배치가 필요하지 않기 때문에 상당히 빠릅니다.
• 중간 데이터를 추가/삭제하는 경우에는 LinkedList가 ArrayList보다 빠르다.
  • 중간 요소를 추가 또는 삭제하는 경우, LinkedList는 각 요소간의 연결만 변경해주면 되기 때문에 처리속도가 상당히 빠릅니다. 반면에 ArrayList는 각 요소들을 재배치하여 추가할 공간을 확보하거나 빈 공간을 채워야하기 때문에 처리속도가 느립니다.

 

컬렉션읽기(접근시간)추가/삭제비 고

ArrayList	빠르다	느리다	순차적인 추가삭제는 더 빠름. 비효율적인 메모리 사용
LinkedList	느리다	빠르다	데이터가 많을 수록 접근성이 떨어짐

 

 

 

본 내용은 아래 참고 링크에 대한 공부하는 겸 다시 정리한 내용이라 비슷한  내용이 많습니다.

참고 : https://devlog-wjdrbs96.tistory.com/64