LinkedList 와 ArrayList의 차이

LinkedList 와 ArrayList 는 둘다 List 인터페이스를 따르지만, 구현방법은 서로 다릅니다. LinkedList 는 이중 연결 리스트(doubly-linked list) 이고, ArrayList 는 동적으로 크기가 변경되는 배열로 되어 있습니다.

링크드 리스트 와 배열의 속성 때문에, 어떤 일을 하는지에 따라 실행 속도가 달라지게 됩니다.

LinkedList

• 특정 원소에 접근하는 것은 O(n)
• 원소를 추가하는 것은 O(1)
• 특정 원소를 제거하는 것은 O(n)
• Iterator.remove 는 O(1)

For ArrayList

• (역주: 특정 인덱스에) 접근 하는 것은 O(1)
• 원소를 추가하는 것은 평균적으로 O(1), 하지만 최악의 경우엔, 어레이 크기를 늘리고 복사해야 되기 때문에 O(n)
• 특정 원소를 제거하는 것은 O(n)

LinkedList 를 쓰면 constant(역주 O(1)) 시간안에 추가 와 제거(역주: Iterator.remove) 를 할 수 있지만, 원소를 접근 할 때, 순차적(역주: 리스트의 처음부터 링크를 따라가서) 으로 접근 할 수 밖에 없다. 다시말하면, 리스트 어딘가에 있는 특정 원소를 접근하는데는 리스트 크기에 비례하는 시간이 걸린다.

ArrayLists 는 반대로, 임의 접근(random access) 가 가능하다. 즉 어떤 원소도 (역주: index로) 즉각 얻어올 수 있다. 하지만, 젤 끝이 아닌 곳에 원소를 더하거나 빼는 것은, 그 원소 이후의 모든 원소를 옮기는 일을 수반하게 된다. 그리고 현재 배열 사이즈를 초과해서 원소를 더하려고 하면, 새로운(보통 두배 크기의) 배열이 생성되고, 원래 배열에서 값들이 새로운 배열로 복사되어야 한다. 따라서 ArrayList 에 원소를 더하는 것은, 최악의 상황에선 O(n) 이고, 평균적으론 O(1) 이다.

따라서, 하고자 하는 바에 따라서, 어떤 리스트를 쓸지 잘 정해야 한다. 원소들을 순차적으로 접근하는 것은 양쪽이 크게 차이가 나지 않는다. (ArrayList 를 순회하는 것이 사실 조금 빠르지만, 정말 이 차이를 걱정해야 할만한 일은 많지 않다.)

또한, 큰 리스트를 만든다면, 메모리 사용량에도 관심을 가져야 할 것이다. LinkedList 는 앞과 뒤 원소를 가리키는 포인터를 저장해야 하기 때문에 원소 하나에 대한 메모리 사용량이 ArrayList 보다 더 많다. 하지만 ArrayList 는 실제 가지고 있는 원소 갯수가 아닌, capacity 만큼의 메모리를 잡아먹는다는 단점이 있다.

ArrayList 의 기본 capacity 는 매우 작다. (java 1.4-6 에서 10이다) 하지만, 구현방식이 배열이기 때문에, 원소를 더하면서 배열의 크기를 조정하게 된다. 많은 원소를 추가할 것이라고 예상할 수 있을 때에는, 처음부터 크기를 크게 잡아서, 배열을 늘릴때 드는 비용을 피해갈 수도 있다.

Vector 도 List 인터페이스를 따르고 ArrayList 와도 매우 비슷하다. 차이점은 Vector 는 동기화 되기때문에 thread-safe(여러 thread 에서 사용해도 안전하다) 라는 점이다. 동기화 때문에 ArrayList 보다 약간 느리기도 하다. 내가 알기론, 대부분 자바 개발자들은 Vector 보단 ArrayList 를 선호한다. thread 환경에서 동기화를 걱정해야되면 아마 더 명시적인 동기화 방법을 사용하는 경우가 많은 것 같다.