Java Collection - List

가장 자주 비교되는 ArrayList와 LinkedList 그리고 Array하고는 어떻게 다른지 확인해보자

ArrayList의 경우 실제 내부에 Array구조를 가져가고 있다.

class ArrayList<E> {
    Object[] data;
    
    E get(int index) {
      return (E) data[index];
    }
}

 

결국 ArrayList도 내부적으로 Array형태를 가져가고 있지만, 핵심은 동적인 리사이징 기능이다.

Array의 경우 최초에 선언한 사이즈에서 조절이 불가능하다. ArrayList의 경우 초기 설정한 size보다 더 많은 양의 데이터가 들어올 경우 자동으로 사이즈를 조절하여 새로운 배열에 데이터가 쌓인다.

그렇다면 ArrayList에 무작정 데이터를 적재하면 어떻게 될까?

배열의 사이즈는 기본값 10으로 시작한다. 그리고 데이터가 초과될 때 마다 1.5배로 사이즈를 확장한다. 10 -> 15 -> 22 이렇게 사이즈가 커지고 당연히 여기서는 그만큼의 성능을 요구한다.(만약 사이즈가 변경되는 시점에 같이 사용하는 Thread가 있다면 동시성 문제 또한 있을 수 있다.)

 

그러니 사이즈가 얼마큼 커질지 알고 있다면 당연히 사이즈를 지정해서 선언하는것이 유리하다.

List<String> list = new ArrayList(255);

 

그에 비해서 LinkedList의 경우에는 아래와 같이 이중 연결 리스트 구조로 되어있다.

class LinkedList<E> {
    Node<E> first;
    Node<E> last;
}

그렇기에 탐색을 할 경우 시작부터 index위치까지 순회해야한다(O(n)). 대신 삽입/삭제가 빈번한 경우 다음 Node의 포인터만 변경해주면 되기 때문에, 중간 위치에 있는 데이터도 빠른 변경이 가능하다. 만약 데이터가 많고 삽입/삭제가 빈번하다면 ArrayList 보다 유리할 수 있다.