[java] Java에서 ArrayList보다 LinkedList를 사용하는 경우는 언제입니까?

요약 ArrayList 와 함께 ArrayDeque에서 바람직하다 많은 보다 더 많은 사용 사례 LinkedList. 확실하지 않은 경우로 시작하십시오 ArrayList.

LinkedList및 ArrayListList 인터페이스의 두 가지 구현입니다. LinkedList이중 연결 목록으로 구현합니다. ArrayList동적 크기 조정 배열로 구현합니다.

표준 링크리스트 및 배열 연산과 마찬가지로 다양한 메소드는 서로 다른 알고리즘 런타임을 갖습니다.

에 대한 LinkedList<E>

• get(int index)인 O (N) (와 N / 4 평균과 같이), 그러나 O (1) 시 index = 0또는 index = list.size() - 1(이 경우, 또한 사용 getFirst()하고 getLast()). 의 주요 장점 중 하나 LinkedList<E>
• add(int index, E element)되고 O (N) (와 N / 4 평균과 같이), 그러나 O (1)이 때, index = 0또는 index = list.size() - 1(이 경우, 또한 사용 addFirst()하고 addLast()/ add()). 의 주요 장점 중 하나 LinkedList<E>
• remove(int index)인 O (N) (와 N / 4 평균과 같이), 그러나 O (1) 시 index = 0또는 index = list.size() - 1(이 경우, 또한 사용 removeFirst()하고 removeLast()). 의 주요 장점 중 하나 LinkedList<E>
• Iterator.remove()인 O (1) . 의 주요 장점 중 하나 LinkedList<E>
• ListIterator.add(E element)인 O (1) . 의 주요 장점 중 하나 LinkedList<E>

^{참고 : 많은 작업이 필요합니다 에는 평균 n / 4 단계 , 최상의 경우 일정한 수의 단계 (예 : 인덱스 = 0), 최악의 경우 n / 2 단계 (중간 목록)가 필요합니다.}

에 대한 ArrayList<E>

• get(int index) 이다 O (1) . 주요 장점 ArrayList<E>
• add(E element)인 O (1) 상각 있지만, O (n)이 최악의 배열을 조정하여 복사되어야하므로
• add(int index, E element) 이다 O (N) (와 N / 2 평균 단계)
• remove(int index) 이다 O (N) (와 N / 2 평균 단계)
• Iterator.remove() 이다 O (N) (와 N / 2 평균 단계)
• ListIterator.add(E element) 이다 O (N) (와 N / 2 평균 단계)

^{참고 : 많은 작업 에는 평균 n / 2 단계 가 필요 합니다. 하며 최상의 경우에는 일정한 수의 단계 (목록 끝), 최악의 경우에는 n 단계 (목록의 시작)가 필요합니다.}

LinkedList<E>반복자를 사용하여 일정한 시간에 삽입하거나 제거 할 수 있지만 요소의 순차적 액세스 만 가능합니다. 즉, 목록을 앞뒤로 걸을 수 있지만 목록에서 위치를 찾는 것은 목록의 크기에 비례하여 시간이 걸립니다. Javadoc에 따르면 “목록에 색인을 생성하는 작업은 목록의 시작 또는 끝에서 더 가까운 쪽을 통과 할 것” 이므로 이러한 방법은 O (n) ( N / 4 , 비록 평균 단계) O (1) 에 대해 index = 0.

ArrayList<E>반면에 빠른 임의 읽기 액세스를 허용하므로 일정한 시간에 모든 요소를 ​​가져올 수 있습니다. 그러나 끝을 제외하고 어디에서나 추가하거나 제거하려면 개구부를 만들거나 간격을 채우기 위해 후자의 모든 요소를 ​​이동해야합니다. 또한 기본 배열의 용량보다 많은 요소를 추가하면 새 배열 (1.5 배 크기)이 할당되고 이전 배열이 새 배열에 복사되므로ArrayList 최악의 에는 O (n) 을 더합니다 평균이지만 일정합니다.

따라서 수행하려는 작업에 따라 구현을 선택해야합니다. 두 종류의 List를 반복하는 것은 실질적으로 저렴합니다. ( ArrayList기술적으로 반복하는 것이 더 빠르지 만 실제로 성능에 민감한 작업을 수행하지 않는 한 걱정하지 않아도됩니다. 두 가지 모두 상수입니다.)

LinkedList기존 반복기를 재사용 하여 요소를 삽입하고 제거 할 때 발생 하는 주요 이점이 있습니다. 그런 다음 목록을 로컬로만 변경하여 O (1) 에서 이러한 작업을 수행 할 수 있습니다 . 배열 목록에서 나머지 배열을 이동 (즉, 복사)해야합니다. 다른 한편으로, 최악의 경우 O (n) ( n / 2 단계) LinkedList의 링크를 따르는 수단을 찾는 반면 원하는 위치에서 수학적으로 계산되고 O (1) 에서 액세스 할 수 있습니다 .ArrayList

사용 a의 또 다른 장점 LinkedList은리스트의 머리에서 추가하거나 제거 할 때 그 작업이기 때문에, 발생하는 O (1) 가있는 동안, O (n)에 대한 ArrayList. 그 ArrayDeque대신에 좋은 대안 이 될 수 있습니다LinkedList헤드에서 추가 및 제거 위한 있지만 이는 아닙니다 List.

또한 큰 목록이있는 경우 메모리 사용량도 다릅니다. LinkedList다음 및 이전 요소에 대한 포인터도 저장되므로 a의 각 요소 에는 더 많은 오버 헤드가 있습니다. ArrayLists이 오버 헤드가 없습니다. 그러나 ArrayLists요소가 실제로 추가되었는지 여부에 관계없이 용량에 할당 된만큼의 메모리를 차지하십시오.

의 기본 초기 용량 ArrayList은 매우 작습니다 (Java 1.4-1.8에서 10). 그러나 기본 구현은 배열이므로 많은 요소를 추가하면 배열의 크기를 조정해야합니다. 많은 요소를 추가 할 것임을 알 때 높은 크기 조정 비용을 피하려면 ArrayList초기 용량이 더 높은 구성 요소를 구성하십시오 .

답변

Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)