[발번역]언제 ArrayList 대신 LinkedList을 쓰나요?

질문 : 나는 대부분 간단하게 List<String> names = new ArrayList<String>() 이렇게 사용한다.

나는 이식성이 좋은 인터페이스(Interface) 타입을 사용한다, 그래서 나의 코드가 변경이 필요할 때 변경 할수 있다.

언제 LinkedList를 ArraryList 대신 쓰나요? 또는 반대로 사용해야 하나요?

요약 답변 : 

ArrayList 와 ArrayDeque가 LinkedList 보다 더 많이 사용 되는 것이 선호 된다. 확실하진 않다. ArrrayList 에 대해 이야기 해보자

LinkedList와 ArrayList는 List Interface를 다르게 구현한 것이다.

LinkedList는 이중 연결 목록 방식으로 구현 되어 있고, ArrayList는 동적으로 크기가 변환되는 배열 방식으로 구현 되었다.

LinkedList와 ArrayList의 각 메소드들은 각각 다른 알고리즘으로 실행되도록 되어 있다.

LinkedList<E> 알고리즘

• get(int index) is O(n)
• add(E element) is O(1)
• add(int index, E element) is O(n)
• remove(int index) is O(n)
• Iterator.remove() is O(1) <-- LinkedList<E> 일 경우만
• ListIterator.add(E element) is O(1) <-- LinkedList<E> 일 경우만

ArrayList<E> 알고리즘

• get(int index) is O(1) <-- LinkedList<E> 일 경우만
• add(E element) is O(1) 분활했을 경우, 그러나 배열이 복제 되거나, 크기 변화시 최악의 경우 O(n)이 된다.
• add(int index, E element) is O(n - index) 분활이 완료 되었을 경우 최악의 경우는 위와 같다
• remove(int index) is O(n - index)  (즉 마지막을 제거할 경우는 O(1))
• Iterator.remove() is O(n - index)
• ListIterator.add(E element) is O(n - index)

Big-O 의미

계산 복잡도 이론에서 사용되는 점근 표기법이며, 입력 데이터의 크기와 알고리즘의 소요시간 또는 메모리의 상관관계를 나타낸다.

• O(1) 상수 형태
• O(n) 선형
  (개념의 이해를 돕기위해, 친구네 집 아파트(101동)에 도달했을 때, 친구네 주소를 알고 있으면 O(1)로  친구네 들어갈 수 있다. 그런데 101동밖에 모른다면 최악의 경우 그 101동의 모든 동호수를 뒤져가며 찾아야 한다 이런 경우를 O(n)으로 생각할 수 있다.)

[알고리즘 별 수행 시간 - WIKI 출처]

LinkedList<E> 는 변함없는 시간내에 추가 또는 삭제를 iterators를 이용 할수 있다.. 그러나 오직 순차적인 요소에 대한 접근만 허락한다.

다시 말해서 목록에 대한 전진 과 후진을 할수 있다 그러나 특정 위치에 대한 검색은 목록의 크기에 비래하는 시간이 필요 하다.

ArrayList<E> 는 반면에 빠른 무작위 읽기 접근이 가능하다. 그래서 어느 요소든 변함없는 시간에 가져올수 있다. 그러나 추가 삭제를 어디에 하던, 꺼내거나 채우는 틈이 있을 경우 그 요소 뒤에 있는 모든 요소는 이동을 해야 한다.  또한 배열의 용량을 넘는 요소를 추가할 경우 새로운 배열을 할당하고, 기존의 배열을 복사하여 새로운 것을 만든다. 그래서 ArrayList 의 추가는 O(n) 나쁜 형태를 가진다  그러나, 일반적으로 변하지 않는다.

그래서 당신의 의도에 따라 구현된 것을 선택 하면된다.사실상 반복하는 두 리스트는 비슷하게 적은 리소스를 이용한다.(엄밀히 따지면 반복을 하는 것은 ArrayList가 더 빠르다, 그러나 정확한 성능 분석을 하지 않는 이상  이것에 대한 고민을 할 필요가 없다.)

LinkedList의 가장 큰 이득은 요소의 등록과 삭제를 다시 반복할때 발생한다. 이런 명령은 O(1) 알고리즘으로 지역적인 변경만 있다 

배열 목록은 나머지 배열의 이동이 필요하다(즉-복사경우). 

다른 방향으로는 탬색의 경우 LinkedList는 O(n)을 뜻하고, 다른 ArrayList의 경우 원하는 위치를 수학적으로 산출 하거나 접근을 O(1)로 할수 있다.

또한 큰 사이즈의 목록의 메모리 사용법 또한 다르다는 것을 명심해야 한다. 각 요소별로 LinkedList는 다음과 이전 연결 점들을 가지고 있다.

ArrayList는 이런 연결점이 없다. 아무리 ArrayList 는 요소가 실제로 추가 되었는지 상관 없이 더 많은 메모리의 용량을 할당을 차지한다.

기본 초기 용량은 ArrayList가 확실히 작다(1.4~ 1.7에서는 10개) 그러나, 근본적으로 배열로 구현되어, 많은 요소를 담을 경우에 사이즈 조절이 필요하다. 많은 비용을 들여서 사이즈 조절을 하는 것을 피하려면 ArraryList의 기본 초기 용량을 높게 잡아야 한다.

Vector 역시 List 인터페이스를 구현되었고 ArrayList와 거의 동일한 것은 언급할 가치가 있다. 다른 것은 Vector은 동기화 되어 Thread-safe 하다. 그렇기 때문에 ArrayList보다 약간 느리다. 그래서 대부분 자바 프로그램에서 Vector 를 사용하지 않고, ArrayList를 선호하는 것은 명백하게 동기화를 하지 않는 것이라고 나는 어느 정도 이해한다.

원본 문서 : http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist

Big-O 위키: https://mirror.enha.kr/wiki/Big-O