Java에서 ArrayList보다 LinkedList를 언제 사용합니까?

질문자 :sdellysse

나는 항상 단순히 사용하는 사람이었습니다.

 List<String> names = new ArrayList<>();

나는 이식성을 위한 유형 이름으로 인터페이스를 사용하여 이와 같은 질문을 할 때 내 코드를 재작업할 수 있습니다.

LinkedList 는ArrayList 와 그 반대로 언제 사용해야 합니까?

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

---

TLDR, ArrayList에서 요소에 액세스하는 데 일정한 시간[O(1)]이 걸리고 요소를 추가하는 데 O(n) 시간[최악의 경우]이 걸립니다. LinkedList에서 요소를 추가하는 데 O(n) 시간이 걸리고 액세스에도 O(n) 시간이 걸리지만 LinkedList는 ArrayList보다 더 많은 메모리를 사용합니다.

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

표준 연결 목록 및 배열 작업과 마찬가지로 다양한 메서드는 서로 다른 알고리즘 런타임을 갖습니다.

LinkedList<E>

• get(int index) 는 O(n) ( 평균 n/4 단계)이지만 index = 0 또는 index = list.size() - 1 때 O(1) (이 경우 getFirst() 및 getLast() ). LinkedList<E> 의 주요 이점 중 하나
• add(int index, E element) 는 O(n) ( 평균 n/4 단계)이지만 index = 0 또는 index = list.size() - 1 때 O(1) (이 경우 다음을 수행할 수도 있습니다. addFirst() 및 addLast() / add() 하십시오. LinkedList<E> 의 주요 이점 중 하나
• remove(int index) 는 O(n) ( 평균 n/4 단계)이지만 index = 0 또는 index = list.size() - 1 때 O(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> 는 iterators를 사용하여 일정한 시간 삽입 또는 제거를 허용하지만 요소의 순차 액세스만 허용합니다. 즉, 목록을 앞뒤로 이동할 수 있지만 목록에서 위치를 찾는 데는 목록 크기에 비례하는 시간이 걸립니다. Javadoc에 따르면 "목록에 대한 색인을 생성하는 작업은 시작 또는 끝에서 더 가까운 쪽부터 목록을 순회" 하므로 해당 메소드는 평균적으로 O(n) ( n/4 단계)이지만 index = 0 대해 O(1) index = 0 .

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

따라서 수행하려는 작업에 따라 그에 따라 구현을 선택해야 합니다. 두 종류의 목록을 반복하는 것은 실질적으로 똑같이 저렴합니다. ArrayList 반복하는 것이 기술적으로 더 빠르지만 성능에 매우 민감한 작업을 수행하지 않는 한 이에 대해 걱정할 필요가 없습니다. 둘 다 상수입니다.)

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

LinkedList 사용의 또 다른 이점은 목록의 헤드에서 추가하거나 제거할 때 발생합니다. 이러한 작업은 O(1) ArrayList 경우 O(n) 이기 때문입니다. ArrayDeque 는 헤드에서 추가 및 제거를 위한 LinkedList 의 좋은 대안이 될 수 List 는 아닙니다.

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

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

데이터 구조 관점이 두 구조를 이해하는 데 사용되는 경우 LinkedList는 기본적으로 헤드 노드를 포함하는 순차적 데이터 구조입니다. Node는 T 유형의 값[제네릭을 통해 허용됨]과 이에 연결된 Node에 대한 또 다른 참조의 두 가지 구성 요소에 대한 래퍼입니다. 그래서 우리는 그것이 재귀적 데이터 구조라고 단언할 수 있습니다. 위에서 언급한 것처럼 LinkedList에서 요소 추가는 선형 시간이 걸립니다.

ArrayList는 성장 가능한 배열입니다. 일반 배열과 같습니다. 내부적으로 요소가 인덱스 i에 추가되면 이전 크기보다 1 큰 크기의 다른 배열이 생성됩니다(따라서 일반적으로 n개의 요소가 ArrayList에 추가될 때 이전 크기의 새 배열 플러스 n이 생성됨). 그런 다음 요소가 이전 배열에서 새 배열로 복사되고 추가될 요소도 지정된 인덱스에 배치됩니다.

Community Wiki

LinkedList ArrayList 보다 "훨씬 더 많다"는 일반적인 합의 외에 이러한 각 목록의 메모리 공간을 해결한 사람은 아무도 없는 것 같습니다. .

참조는 상대 시스템에서 32비트 또는 64비트(null인 경우에도)이므로 32비트 및 64비트 LinkedLists 및 ArrayLists 대한 4개의 데이터 세트를 포함했습니다.

참고: ArrayList 행에 표시된 크기 는 잘린 목록 ArrayList 의 지원 배열 용량은 일반적으로 현재 요소 수보다 큽니다.

참고 2: (BeeOnRope 덕분에) CompressedOops는 이제 JDK6 중반부터 기본값이므로 64비트 머신에 대한 아래 값은 물론 특별히 끄지 않는 한 기본적으로 32비트 머신과 일치합니다.

---

---

LinkedList ArrayList 보다 훨씬 더 많다는 것을 분명히 보여줍니다. 특히 요소 수가 매우 많습니다. 메모리가 요인이라면 LinkedLists .

제가 사용한 공식은 다음과 같습니다. 제가 잘못한 것이 있으면 알려주시면 수정하겠습니다. 'b'는 32 또는 64비트 시스템의 경우 4 또는 8이고 'n'은 요소 수입니다. mods의 이유는 Java의 모든 객체가 모두 사용 여부에 관계없이 8바이트 공간의 배수를 차지하기 때문입니다.

배열 목록:

ArrayList object header + size integer + modCount integer + array reference + (array oject header + b * n) + MOD(array oject, 8) + MOD(ArrayList object, 8) == 8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8) + MOD(8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8), 8)

연결 목록:

LinkedList object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) * n) + MOD(node object, 8) * n + MOD(LinkedList object, 8) == 8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n + MOD(8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n, 8)

Numeron

ArrayList 는 당신이 원하는 것입니다. LinkedList 는 거의 항상 (성능) 버그입니다.

LinkedList 짜증나는 이유:

• 작은 메모리 개체를 많이 사용하므로 프로세스 전체의 성능에 영향을 줍니다.
• 많은 작은 개체는 캐시 지역성에 좋지 않습니다.
• 모든 인덱싱된 작업에는 순회가 필요합니다. 즉, O(n) 성능이 있습니다. ArrayList 가 사용된 경우보다 알고리즘 O(n)이 느려집니다.
• 좋은 성능을 얻는 것은 까다롭습니다.
• big-O 성능이 ArrayList 와 같더라도 어쨌든 상당히 느릴 것입니다.
• 아마도 잘못된 선택일 수 있기 때문에 소스에서 LinkedList 를 보는 것은 거슬립니다.

Tom Hawtin - tackline

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)

알고리즘: Big-Oh 표기법 (보관됨)

ArrayLists는 write-once-read-many 또는 appender에 적합하지만 전면 또는 중간에서 추가/제거에는 좋지 않습니다.

Michael Munsey

약 10년 동안 초대형 SOA 웹 서비스에서 운영 성능 엔지니어링을 수행한 사람으로서 저는 ArrayList보다 LinkedList의 동작을 선호합니다. LinkedList의 정상 상태 처리량이 더 나빠서 더 많은 하드웨어를 구매하게 될 수 있지만 압력을 받는 ArrayList의 동작은 클러스터의 앱이 거의 동기화되어 어레이를 확장하고 어레이 크기가 큰 경우 응답성이 부족할 수 있습니다. 압력을 받고 있는 동안 앱과 중단은 치명적인 동작입니다.

유사하게, 기본 처리량 테넌트 가비지 수집기에서 앱의 처리량을 향상시킬 수 있지만 10GB 힙이 있는 Java 앱을 얻으면 전체 GC 동안 25초 동안 앱을 잠글 수 있으며 이로 인해 SOA 앱에서 시간 초과 및 오류가 발생합니다. 너무 자주 발생하면 SLA를 날려 버립니다. CMS 수집기가 더 많은 리소스를 사용하고 동일한 원시 처리량을 달성하지 못하더라도 예측 가능하고 대기 시간이 더 짧기 때문에 훨씬 더 나은 선택입니다.

ArrayList는 성능이 처리량만 의미하고 대기 시간을 무시할 수 있는 경우에만 성능에 더 나은 선택입니다. 직장에서의 경험상 최악의 대기 시간을 무시할 수 없습니다.

업데이트(2021년 8월 27일 - 10년 후): 이 답변(SO에 대한 역사적으로 가장 많이 찬성한 답변이기도 함)은 틀릴 가능성이 매우 높습니다(아래 설명에 설명된 이유로). ArrayList가 메모리의 순차 읽기를 최적화하고 캐시 라인 및 TLB 누락 등을 최소화한다고 추가하고 싶습니다. 어레이가 경계를 초과할 때 복사 오버헤드는 비교에 의해 중요하지 않을 수 있습니다(효율적인 CPU 작업으로 수행할 수 있음 ). 이 대답은 하드웨어 추세를 감안할 때 시간이 지남에 따라 더 나빠질 수도 있습니다. LinkedList가 의미가 있을 수 있는 유일한 상황은 수천 개의 목록이 있고 그 중 하나가 GB 크기로 커질 수 있지만 목록의 할당 시간 및 설정 시 좋은 추측을 할 수 없는 고도로 고안된 상황입니다. 모두 GB 크기로 설정하면 힙이 폭발합니다. 그리고 그런 문제를 발견했다면 솔루션이 무엇이든 간에 실제로 리엔지니어링이 필요합니다. 원래 디자인이 단순히 활주로를 벗어났고 척척 처리해야 하는 아주 좋은 경우입니다. 그래도 읽을 수 있도록 수십 년 된 나의 가난한 의견을 남겨 두겠습니다. 간단하고 논리적이며 꽤 틀립니다.

lamont

네, 알아요. 이것은 오래된 질문이지만 제 2센트를 드리겠습니다.

LinkedList는 성능 면에서 거의 항상 잘못된 선택입니다. LinkedList가 호출되는 매우 구체적인 알고리즘이 몇 가지 있지만 매우 드물며 알고리즘은 일반적으로 목록 중간에 있는 요소를 비교적 빠르게 삽입 및 삭제하는 LinkedList의 기능에 따라 달라집니다. ListIterator로.

LinkedList가 ArrayList를 능가하는 한 가지 일반적인 사용 사례가 있습니다. 바로 대기열의 경우입니다. 그러나 목표가 성능이라면 LinkedList 대신 ArrayBlockingQueue(대기열 크기의 상한선을 미리 결정할 수 있고 모든 메모리를 미리 할당할 수 있는 경우) 또는 이 CircularArrayList 구현을 사용하는 것도 고려해야 합니다. . (예, 2001년부터 생성되었으므로 생성해야 하지만 최근 JVM에서 기사에 인용된 것과 비슷한 성능 비율을 얻었습니다.)

Daniel Martin

효율성 질문입니다. LinkedList 는 요소를 추가하고 삭제하는 데 빠르지만 특정 요소에 액세스하는 것은 느립니다. ArrayList 는 특정 요소에 액세스하는 데 빠르지 만 양쪽 끝에 추가하는 것이 느릴 수 있으며 특히 중간에 삭제하는 것이 느릴 수 있습니다.

Array vs ArrayList vs LinkedList vs Vector 는 Linked List 와 마찬가지로 더 자세히 설명합니다.

dgtized

LinkedList의 저자인 Joshua Bloch:

실제로 LinkedList를 사용하는 사람이 있습니까? 제가 썼는데 절대 사용하지 않습니다.

링크: https://twitter.com/joshbloch/status/583813919019573248

답변이 다른 답변들에 비해 그다지 유익하지 못해서 죄송합니다만, 가장 흥미롭고 자명할 것이라고 생각했습니다.

Ruslan

맞음 또는 틀림: 로컬에서 테스트를 실행하고 스스로 결정하십시오!

ArrayList 보다 LinkedList 에서 편집/제거가 더 빠릅니다.

Array 지원하는 ArrayList 는 대용량 응용 프로그램에서 더 나쁩니다.

다음은 각 작업에 대한 단위 테스트 결과입니다. 타이밍은 나노초로 표시됩니다.

---

 Operation ArrayList LinkedList AddAll (Insert) 101,16719 2623,29291 Add (Insert-Sequentially) 152,46840 966,62216 Add (insert-randomly) 36527 29193 remove (Delete) 20,56,9095 20,45,4904 contains (Search) 186,15,704 189,64,981

---

코드는 다음과 같습니다.

 import org.junit.Assert; import org.junit.Test; import java.util.*; public class ArrayListVsLinkedList { private static final int MAX = 500000; String[] strings = maxArray(); ////////////// ADD ALL //////////////////////////////////////// @Test public void arrayListAddAll() { Watch watch = new Watch(); List<String> stringList = Arrays.asList(strings); List<String> arrayList = new ArrayList<String>(MAX); watch.start(); arrayList.addAll(stringList); watch.totalTime("Array List addAll() = ");//101,16719 Nanoseconds } @Test public void linkedListAddAll() throws Exception { Watch watch = new Watch(); List<String> stringList = Arrays.asList(strings); watch.start(); List<String> linkedList = new LinkedList<String>(); linkedList.addAll(stringList); watch.totalTime("Linked List addAll() = "); //2623,29291 Nanoseconds } //Note: ArrayList is 26 time faster here than LinkedList for addAll() ///////////////// INSERT ///////////////////////////////////////////// @Test public void arrayListAdd() { Watch watch = new Watch(); List<String> arrayList = new ArrayList<String>(MAX); watch.start(); for (String string : strings) arrayList.add(string); watch.totalTime("Array List add() = ");//152,46840 Nanoseconds } @Test public void linkedListAdd() { Watch watch = new Watch(); List<String> linkedList = new LinkedList<String>(); watch.start(); for (String string : strings) linkedList.add(string); watch.totalTime("Linked List add() = "); //966,62216 Nanoseconds } //Note: ArrayList is 9 times faster than LinkedList for add sequentially /////////////////// INSERT IN BETWEEN /////////////////////////////////////// @Test public void arrayListInsertOne() { Watch watch = new Watch(); List<String> stringList = Arrays.asList(strings); List<String> arrayList = new ArrayList<String>(MAX + MAX / 10); arrayList.addAll(stringList); String insertString0 = getString(true, MAX / 2 + 10); String insertString1 = getString(true, MAX / 2 + 20); String insertString2 = getString(true, MAX / 2 + 30); String insertString3 = getString(true, MAX / 2 + 40); watch.start(); arrayList.add(insertString0); arrayList.add(insertString1); arrayList.add(insertString2); arrayList.add(insertString3); watch.totalTime("Array List add() = ");//36527 } @Test public void linkedListInsertOne() { Watch watch = new Watch(); List<String> stringList = Arrays.asList(strings); List<String> linkedList = new LinkedList<String>(); linkedList.addAll(stringList); String insertString0 = getString(true, MAX / 2 + 10); String insertString1 = getString(true, MAX / 2 + 20); String insertString2 = getString(true, MAX / 2 + 30); String insertString3 = getString(true, MAX / 2 + 40); watch.start(); linkedList.add(insertString0); linkedList.add(insertString1); linkedList.add(insertString2); linkedList.add(insertString3); watch.totalTime("Linked List add = ");//29193 } //Note: LinkedList is 3000 nanosecond faster than ArrayList for insert randomly. ////////////////// DELETE ////////////////////////////////////////////////////// @Test public void arrayListRemove() throws Exception { Watch watch = new Watch(); List<String> stringList = Arrays.asList(strings); List<String> arrayList = new ArrayList<String>(MAX); arrayList.addAll(stringList); String searchString0 = getString(true, MAX / 2 + 10); String searchString1 = getString(true, MAX / 2 + 20); watch.start(); arrayList.remove(searchString0); arrayList.remove(searchString1); watch.totalTime("Array List remove() = ");//20,56,9095 Nanoseconds } @Test public void linkedListRemove() throws Exception { Watch watch = new Watch(); List<String> linkedList = new LinkedList<String>(); linkedList.addAll(Arrays.asList(strings)); String searchString0 = getString(true, MAX / 2 + 10); String searchString1 = getString(true, MAX / 2 + 20); watch.start(); linkedList.remove(searchString0); linkedList.remove(searchString1); watch.totalTime("Linked List remove = ");//20,45,4904 Nanoseconds } //Note: LinkedList is 10 millisecond faster than ArrayList while removing item. ///////////////////// SEARCH /////////////////////////////////////////// @Test public void arrayListSearch() throws Exception { Watch watch = new Watch(); List<String> stringList = Arrays.asList(strings); List<String> arrayList = new ArrayList<String>(MAX); arrayList.addAll(stringList); String searchString0 = getString(true, MAX / 2 + 10); String searchString1 = getString(true, MAX / 2 + 20); watch.start(); arrayList.contains(searchString0); arrayList.contains(searchString1); watch.totalTime("Array List addAll() time = ");//186,15,704 } @Test public void linkedListSearch() throws Exception { Watch watch = new Watch(); List<String> linkedList = new LinkedList<String>(); linkedList.addAll(Arrays.asList(strings)); String searchString0 = getString(true, MAX / 2 + 10); String searchString1 = getString(true, MAX / 2 + 20); watch.start(); linkedList.contains(searchString0); linkedList.contains(searchString1); watch.totalTime("Linked List addAll() time = ");//189,64,981 } //Note: Linked List is 500 Milliseconds faster than ArrayList class Watch { private long startTime; private long endTime; public void start() { startTime = System.nanoTime(); } private void stop() { endTime = System.nanoTime(); } public void totalTime(String s) { stop(); System.out.println(s + (endTime - startTime)); } } private String[] maxArray() { String[] strings = new String[MAX]; Boolean result = Boolean.TRUE; for (int i = 0; i < MAX; i++) { strings[i] = getString(result, i); result = !result; } return strings; } private String getString(Boolean result, int i) { return String.valueOf(result) + i + String.valueOf(!result); } }

Ash

ArrayList 는 본질적으로 배열입니다. LinkedList 는 이중 연결 목록으로 구현됩니다.

get 것은 꽤 명확합니다. ArrayList 경우 O(1) ArrayList 는 인덱스를 사용하여 임의 액세스를 허용하기 때문입니다. LinkedList 경우 O(n) 인덱스를 먼저 찾아야 하기 때문입니다. add 및 remove 의 다른 버전이 있습니다.

LinkedList 는 추가 및 제거에서 더 빠르지만 가져오기에서는 더 느립니다. 간단히 말해서 다음과 같은 경우 LinkedList 가 선호되어야 합니다.

1. 많은 수의 요소에 대한 임의 액세스가 없습니다.
2. 많은 수의 추가/제거 작업이 있습니다.

=== 배열 목록 ===

• 추가(E e)
  • ArrayList 끝에 추가
  • 메모리 크기 조정 비용이 필요합니다.
  • O(n) 최악, O(1) 상각
• add(int 인덱스, E 요소)
  • 특정 인덱스 위치에 추가
  • 이동 및 가능한 메모리 크기 조정 비용 필요
  • 에)
• 제거(int 인덱스)
  • 지정된 요소 제거
  • 이동 및 가능한 메모리 크기 조정 비용 필요
  • 에)
• 제거(객체 o)
  • 이 목록에서 지정된 요소의 첫 번째 항목을 제거합니다.
  • 먼저 요소를 검색한 다음 이동 및 가능한 메모리 크기 조정 비용이 필요합니다.
  • 에)

=== 링크드리스트 ===

• 추가(E e)

  • 목록 끝에 추가
  • 오(1)

• add(int 인덱스, E 요소)

  • 지정된 위치에 삽입
  • 먼저 위치를 찾아야 합니다
  • 에)
• 제거하다()
  • 목록의 첫 번째 요소 제거
  • 오(1)
• 제거(int 인덱스)
  • 지정된 인덱스가 있는 요소 제거
  • 요소를 먼저 찾아야 합니다.
  • 에)
• 제거(객체 o)
  • 지정된 요소의 첫 번째 항목 제거
  • 요소를 먼저 찾아야 합니다.
  • 에)

다음은 programcreek.com 의 그림입니다( add 및 remove 가 첫 번째 유형입니다. 즉, 목록 끝에 요소를 추가하고 목록의 지정된 위치에서 요소를 제거합니다.):

Ryan

TL;DR 최신 컴퓨터 아키텍처로 인해 ArrayList 는 거의 모든 가능한 사용 사례에서 훨씬 더 효율적이므로 LinkedList 는 매우 독특하고 극단적인 경우를 제외하고는 피해야 합니다.

---

add(E element) 대해 O(1)이 있습니다.

또한 목록 중간에 요소를 추가하는 것은 매우 효율적이어야 합니다.

LinkedList는 캐시 적대적 데이터 구조이기 때문에 실습은 매우 다릅니다. 성능 POV에서 - LinkedList 가 캐시 친화적인 ArrayList 보다 성능이 더 좋을 수 있는 경우는 거의 없습니다.

다음은 임의의 위치에 요소를 삽입하는 벤치마크 테스트 결과입니다. 보시다시피 배열 목록이 훨씬 더 효율적이지만 이론상 목록 중간에 삽입할 때마다 배열의 n개 이후 요소를 "이동"해야 합니다(값이 낮을수록 좋음).

차세대 하드웨어(더 크고 효율적인 캐시)에서 작업 - 결과는 훨씬 더 결정적입니다.

LinkedList는 동일한 작업을 수행하는 데 훨씬 더 많은 시간이 걸립니다. 소스 소스 코드

여기에는 두 가지 주요 이유가 있습니다.

1. 주로 LinkedList 의 노드가 메모리 전체에 무작위로 흩어져 있습니다. RAM("Random Access Memory")은 실제로 무작위가 아니며 메모리 블록을 캐시로 가져와야 합니다. 이 작업은 시간이 걸리고 이러한 페치가 자주 발생하면 캐시의 메모리 페이지를 항상 교체해야 함 -> 캐시 미스 -> 캐시가 효율적이지 않습니다. ArrayList 요소는 연속 메모리에 저장됩니다. 이것이 바로 최신 CPU 아키텍처가 최적화하는 것입니다.

2. 뒤로/앞으로 포인터를 유지하려면 보조 LinkedList ArrayList 에 비해 저장된 값당 메모리 소비가 3배임을 의미합니다.

DynamicIntArray Int (기본 유형)를 유지하는 사용자 지정 ArrayList 구현이므로 모든 데이터가 실제로 인접하게 저장되므로 훨씬 더 효율적입니다.

기억해야 할 핵심 요소는 메모리 블록을 가져오는 비용이 단일 메모리 셀에 액세스하는 비용보다 더 중요하다는 것입니다. 그렇기 때문에 1MB의 순차 메모리를 읽는 것이 다른 메모리 블록에서 이 양의 데이터를 읽는 것보다 최대 400배 더 빠릅니다.

 Latency Comparison Numbers (~2012) ---------------------------------- L1 cache reference 0.5 ns Branch mispredict 5 ns L2 cache reference 7 ns 14x L1 cache Mutex lock/unlock 25 ns Main memory reference 100 ns 20x L2 cache, 200x L1 cache Compress 1K bytes with Zippy 3,000 ns 3 us Send 1K bytes over 1 Gbps network 10,000 ns 10 us Read 4K randomly from SSD* 150,000 ns 150 us ~1GB/sec SSD Read 1 MB sequentially from memory 250,000 ns 250 us Round trip within same datacenter 500,000 ns 500 us Read 1 MB sequentially from SSD* 1,000,000 ns 1,000 us 1 ms ~1GB/sec SSD, 4X memory Disk seek 10,000,000 ns 10,000 us 10 ms 20x datacenter roundtrip Read 1 MB sequentially from disk 20,000,000 ns 20,000 us 20 ms 80x memory, 20X SSD Send packet CA->Netherlands->CA 150,000,000 ns 150,000 us 150 ms

출처: 모든 프로그래머가 알아야 하는 대기 시간 숫자

요점을 더욱 명확하게 하기 위해 목록의 시작 부분에 요소를 추가하는 벤치마크를 확인하십시오. 이것은 이론적으로 LinkedList 가 실제로 빛을 발 ArrayList 가 좋지 않거나 더 나쁜 경우의 결과를 나타내야 하는 사용 사례입니다.

참고: 이것은 C++ Std lib의 벤치마크이지만 C++ 및 Java 결과가 매우 유사한 이전 경험을 보여주었습니다. 소스 코드

대량의 메모리를 순차적으로 복사하는 것은 최신 CPU에 의해 최적화된 작업입니다. 이론을 변경하고 실제로 ArrayList / Vector 훨씬 더 효율적으로 만듭니다.

---

크레딧: 여기에 게시된 모든 벤치마크는 Kjell Hedström 이 작성했습니다. 그의 블로그 에서 더 많은 데이터를 찾을 수 있습니다.

Lior Bar-On

ArrayList 는 무작위로 액세스할 수 있지만 LinkedList 는 요소를 확장하고 제거하는 데 정말 저렴합니다. 대부분의 경우 ArrayList 가 좋습니다.

큰 목록을 만들고 병목 현상을 측정하지 않는 한 그 차이에 대해 걱정할 필요가 없을 것입니다.

Dustin

코드에 add(0) 및 remove(0) 있는 경우 LinkedList addFirst() 및 removeFirst() 메서드가 더 좋습니다. 그렇지 않으면 ArrayList 사용하십시오.

물론 Guava 의 ImmutableList 는 가장 친한 친구입니다.

Jesse Wilson

나는 일반적으로 특정 목록에서 수행할 작업의 시간 복잡성을 기반으로 다른 하나를 사용합니다.

 |---------------------|---------------------|--------------------|------------| | Operation | ArrayList | LinkedList | Winner | |---------------------|---------------------|--------------------|------------| | get(index) | O(1) | O(n) | ArrayList | | | | n/4 steps in avg | | |---------------------|---------------------|--------------------|------------| | add(E) | O(1) | O(1) | LinkedList | | |---------------------|--------------------| | | | O(n) in worst case | | | |---------------------|---------------------|--------------------|------------| | add(index, E) | O(n) | O(n) | LinkedList | | | n/2 steps | n/4 steps | | | |---------------------|--------------------| | | | | O(1) if index = 0 | | |---------------------|---------------------|--------------------|------------| | remove(index, E) | O(n) | O(n) | LinkedList | | |---------------------|--------------------| | | | n/2 steps | n/4 steps | | |---------------------|---------------------|--------------------|------------| | Iterator.remove() | O(n) | O(1) | LinkedList | | ListIterator.add() | | | | |---------------------|---------------------|--------------------|------------| |--------------------------------------|-----------------------------------| | ArrayList | LinkedList | |--------------------------------------|-----------------------------------| | Allows fast read access | Retrieving element takes O(n) | |--------------------------------------|-----------------------------------| | Adding an element require shifting | o(1) [but traversing takes time] | | all the later elements | | |--------------------------------------|-----------------------------------| | To add more elements than capacity | | new array need to be allocated | |--------------------------------------|

Gayan Weerakutti

LinkedList 가 Deque 구현한다는 것을 아무도 언급하지 않았다는 것을 솔직히 믿을 수 없습니다. Deque (및 Queue )의 메소드를 살펴보십시오. 공정한 비교를 원하면 ArrayDeque 에 대해 LinkedList 를 실행하고 기능별 비교를 수행하십시오.

Ajax

매개변수 아래에서 LinkedList와 ArrayList wrt를 비교해 보겠습니다.

1. 시행

ArrayList 는 목록 인터페이스의 크기 조정 가능한 배열 구현입니다.

LinkedList 는 목록 인터페이스의 이중 연결 목록 구현입니다.

---

2. 성능

• get(int 인덱스) 또는 검색 작업

  ArrayList get(int index) 작업은 일정한 시간에 실행됩니다. 즉, O(1) 동안

  LinkedList get(int index) 작업 런타임은 O(n) 입니다.

  ArrayList 가 LinkedList보다 빠른 이유는 ArrayList가 내부적으로 배열 데이터 구조를 사용하기 때문에 요소에 대해 인덱스 기반 시스템을 사용하기 때문입니다.

  LinkedList 는 지정된 요소 인덱스에서 노드를 검색하기 위해 시작 또는 끝(둘 중 더 가까운 쪽)에서 반복하므로 해당 요소에 대한 인덱스 기반 액세스를 제공하지 않습니다.

• insert() 또는 add(Object) 작업

  LinkedList의 삽입은 일반적으로 ArrayList에 비해 빠릅니다. LinkedList에서 추가 또는 삽입은 O(1) 작업입니다.

  ArrayList 에서 배열이 전체 즉 최악의 경우인 경우 배열 크기를 조정하고 요소를 새 배열로 복사하는 추가 비용이 있으므로 ArrayList에서 추가 작업의 런타임이 O(n)이고 그렇지 않으면 O(1)입니다. .

• 제거(int) 작업

  LinkedList의 제거 작업은 일반적으로 ArrayList 즉 O(n)과 동일합니다.

  LinkedList 에는 두 가지 오버로드된 제거 메서드가 있습니다. 하나는 목록의 헤드를 제거하고 일정한 시간 O(1)에서 실행되는 매개변수가 없는 remove()입니다. LinkedList에서 오버로드된 다른 제거 메소드는 매개변수로 전달된 Object 또는 int를 제거하는 remove(int) 또는 remove(Object)입니다. 이 메서드는 Object를 찾을 때까지 LinkedList를 탐색하고 원래 목록에서 연결을 해제합니다. 따라서 이 메서드 런타임은 O(n)입니다.

  ArrayList에서 remove(int) 메소드는 이전 배열에서 새로운 업데이트된 배열로 요소를 복사하는 것을 포함하므로 런타임은 O(n)입니다.

---

3. 역 반복자

LinkedList 는DescendingIterator()를 사용하여 역방향으로 반복할 수 있습니다.

ArrayList 에는DescendingIterator()가 없으므로 ArrayList를 역방향으로 반복하는 자체 코드를 작성해야 합니다.

---

4. 초기 용량

생성자가 오버로드되지 않은 경우 ArrayList 는 초기 용량 10의 빈 목록을 생성하는 반면

LinkedList 는 초기 용량이 없는 빈 목록만 구성합니다.

---

5. 메모리 오버헤드

LinkedList의 메모리 오버헤드는 LinkedList의 노드가 다음 및 이전 노드의 주소를 유지해야 하므로 ArrayList에 비해 더 많습니다. 하는 동안

ArrayList에서 각 인덱스는 실제 객체(데이터)만 보유합니다.

---

원천

Abhijeet Ashok Muneshwar

ArrayList 와 LinkedList 및 CopyOnWrite-ArrayList 의 Big-O 표기법입니다.

배열 목록

 get O(1) add O(1) contains O(n) next O(1) remove O(n) iterator.remove O(n)

링크드리스트

 get O(n) add O(1) contains O(n) next O(1) remove O(1) iterator.remove O(1)

CopyOnWrite-ArrayList

 get O(1) add O(n) contains O(n) next O(1) remove O(n) iterator.remove O(n)

이를 바탕으로 무엇을 선택할지 결정해야 합니다. :)

Rajith Delantha

위의 다른 좋은 인수 외에도 ArrayList 는 RandomAccess 인터페이스를 구현 LinkedList Queue 구현합니다.

따라서 어떻게 든 효율성과 행동의 차이로 약간 다른 문제를 해결합니다(방법 목록 참조).

PhiLho

목록에서 더 많은 작업을 수행할 작업에 따라 다릅니다.

ArrayList 는 인덱싱된 값에 액세스하는 것이 더 빠릅니다. 개체를 삽입하거나 삭제할 때 훨씬 더 나쁩니다.

더 자세히 알아보려면 배열과 연결 목록의 차이점에 대해 설명하는 기사를 읽어보세요.

Matthew Schinckel

배열 목록은 본질적으로 항목 등을 추가하는 메서드가 있는 배열입니다(대신 일반 목록을 사용해야 함). 인덱서를 통해 액세스할 수 있는 항목 모음입니다(예: [0]). 한 항목에서 다음 항목으로의 진행을 의미합니다.

연결 목록은 한 항목에서 다음 항목으로의 진행을 지정합니다(항목 a -> 항목 b). 배열 목록에서도 동일한 효과를 얻을 수 있지만 연결 목록은 이전 항목 다음에 어떤 항목이 따라야 하는지 절대적으로 알려줍니다.

kemiller2002

Java 자습서 - 구현 목록을 참조하십시오.

chharvey

연결 목록의 중요한 기능(다른 답변에서는 읽지 않음)은 두 목록을 연결하는 것입니다. 배열의 경우 이것은 O(n)(+ 일부 재할당의 오버헤드)이고 연결 목록은 O(1) 또는 O(2) ;-)

중요 : Java의 LinkedList 이것은 사실이 아닙니다! Java의 연결 목록에 대한 빠른 연결 방법이 있습니까?를 참조하십시오.

Karussell

ArrayList와 LinkedList에는 장단점이 있습니다.

ArrayList는 다음 노드에 대한 포인터를 사용하는 LinkedList에 비해 연속 메모리 주소를 사용합니다. 따라서 ArrayList에서 요소를 조회하려는 경우 LinkedList로 n번 반복하는 것보다 빠릅니다.

반면 LinkedList의 삽입 및 삭제는 포인터를 변경하기만 하면 되기 때문에 훨씬 쉽습니다.

앱에서 검색 작업이 자주 있는 경우 ArrayList를 사용하세요. 삽입과 삭제가 잦은 경우 LinkedList를 사용하십시오.

Nesan Mano

1) 기본 데이터 구조

ArrayList와 LinkedList의 첫 번째 차이점은 ArrayList가 Array에 의해 지원되고 LinkedList가 LinkedList에 의해 지원된다는 사실에 있습니다. 이것은 성능의 추가 차이로 이어질 것입니다.

2) LinkedList는 Deque를 구현합니다.

ArrayList와 LinkedList의 또 다른 차이점은 List 인터페이스와 별도로 LinkedList는 add() 및 poll() 및 기타 여러 Deque 함수에 대한 선입 선출 작업을 제공하는 Deque 인터페이스도 구현한다는 것입니다. 3) ArrayList에 요소 추가 ArrayList에 요소를 추가하는 것은 Array의 re-size를 트리거하지 않으면 O(1) 연산이 되며, 이 경우 O(log(n))가 되고, 반면에 요소를 추가하는 것은 LinkedList는 탐색이 필요하지 않으므로 O(1) 작업입니다.

4) 위치에서 요소 제거

remove(index) 를 호출하여 특정 인덱스에서 요소를 제거하기 위해 ArrayList는 O(n)에 가깝게 만드는 복사 작업을 수행하는 반면 LinkedList는 O(n/2)로 만드는 해당 지점까지 트래버스해야 합니다. , 근접성을 기반으로 어느 방향에서든 횡단할 수 있기 때문입니다.

5) ArrayList 또는 LinkedList에 대한 반복

반복은 LinkedList와 ArrayList 모두에 대한 O(n) 작업입니다. 여기서 n은 요소의 번호입니다.

6) 위치에서 요소 검색

get(index) 작업은 ArrayList에서 O(1)이고 LinkedList에서는 O(n/2)입니다. 해당 항목까지 트래버스해야 하기 때문입니다. 하지만 Big O 표기법에서 O(n/2)는 상수를 무시하기 때문에 그냥 O(n)입니다.

7) 메모리

LinkedList는 데이터를 저장하기 위한 정적 중첩 클래스인 래퍼 개체 Entry를 사용하는 반면 ArrayList는 데이터를 Array에 저장합니다.

따라서 Array가 한 Array에서 다른 Array로 내용을 복사할 때 크기 조정 작업을 수행하는 경우를 제외하고 ArrayList의 경우 LinkedList보다 메모리 요구 사항이 적습니다.

Array가 충분히 크면 해당 지점에서 많은 메모리를 사용하고 가비지 수집을 트리거하여 응답 시간이 느려질 수 있습니다.

remove() 또는 get() add() 작업을 자주 수행하는 경우를 제외하고 거의 모든 경우에 ArrayList가 LinkedList보다 더 나은 선택인 것 같습니다.

연결 목록은 내부적으로 해당 위치에 대한 참조를 유지하고 O(1) 시간에 액세스할 수 있기 때문에 특히 시작 또는 끝에서 요소를 추가하거나 제거하는 경우 ArrayList보다 연결 목록을 수정하는 것이 더 쉽습니다.

즉, 원소를 추가하고자 하는 위치에 도달하기 위해 연결 리스트를 순회할 필요가 없으며, 이 경우 덧셈은 O(n) 연산이 됩니다. 예를 들어, 연결 목록 중간에 요소를 삽입하거나 삭제합니다.

제 생각에는 Java에서 대부분의 실용적인 목적을 위해 LinkedList보다 ArrayList를 사용하십시오.

Anjali Suman

응답을 읽었지만 의견을 듣기 위해 공유하고 싶은 ArrayList보다 LinkedList를 항상 사용하는 시나리오가 하나 있습니다.

DB에서 얻은 데이터 목록을 반환하는 메서드가 있을 때마다 저는 항상 LinkedList를 사용합니다.

내 근거는 내가 얼마나 많은 결과를 얻고 있는지 정확히 알 수 없기 때문에 메모리가 낭비되지 않으며(ArrayList에서 용량과 실제 요소 수의 차이가 있음) 시간을 낭비하지 않는다는 것입니다. 용량을 복제합니다.

ArrayList에 대해서는 가능한 한 배열의 중복을 최소화하기 위해 최소한 항상 초기 용량의 생성자를 사용해야 한다는 데 동의합니다.

gaijinco

ArrayList 와 LinkedList 모두 List interface 구현하며 그 방법과 결과는 거의 동일합니다. 그러나 요구 사항에 따라 서로를 능가하는 차이점이 거의 없습니다.

ArrayList 대 LinkedList

1) Search: ArrayList 검색 작업은 LinkedList 검색 작업에 비해 상당히 빠릅니다. ArrayList get(int index) O(1) 의 성능을 제공하는 반면 LinkedList 성능은 O(n) 입니다.

Reason: ArrayList 는 암시적으로 배열 데이터 구조를 사용하므로 해당 요소에 대한 인덱스 기반 시스템을 유지하므로 목록에서 요소를 더 빠르게 검색할 수 있습니다. 반면 LinkedList 는 요소를 검색하기 위해 모든 요소를 순회해야 하는 이중 연결 목록을 구현합니다.

2) Deletion: LinkedList 제거 작업은 O(1) 성능을 ArrayList 는 가변 성능을 제공합니다. O(n) (첫 번째 요소를 제거하는 동안) 및 O(1) (마지막 요소를 제거하는 동안).

결론: LinkedList 요소 삭제는 ArrayList에 비해 빠릅니다.

이유: LinkedList의 각 요소는 목록의 두 인접 요소를 가리키는 두 개의 포인터(주소)를 유지합니다. 따라서 제거는 제거될 노드의 두 인접 노드(요소)에서 포인터 위치만 변경하면 됩니다. ArrayList에서는 제거된 요소에 의해 생성된 공간을 채우기 위해 모든 요소를 이동해야 합니다.

3) Inserts Performance: LinkedList add 메소드는 O(1) 성능을 ArrayList 는 최악의 경우 O(n) 성능을 제공합니다. 이유는 제거 설명과 동일합니다.

4) Memory Overhead: ArrayList 는 인덱스와 요소 데이터를 LinkedList 는 요소 데이터와 인접 노드에 대한 두 개의 포인터를 유지 관리합니다.

따라서 LinkedList에서 메모리 소비가 비교적 높습니다.

이러한 클래스 사이에는 다음과 같은 몇 가지 유사점이 있습니다.

• ArrayList와 LinkedList는 모두 List 인터페이스의 구현입니다.
• 둘 다 요소 삽입 순서를 유지합니다. 즉, ArrayList 및 LinkedList 요소를 표시하는 동안 결과 집합은 요소가 목록에 삽입된 순서와 동일한 순서를 갖게 됩니다.
• 이 두 클래스는 모두 동기화되지 않으며 Collections.synchronizedList 메서드를 사용하여 명시적으로 동기화할 수 있습니다.
• 이 클래스에 의해 반환된 iterator 와 listIterator fail-fast (반복자가 생성된 후 언제든지 목록이 구조적으로 수정되면 iterator's 자체 제거 또는 추가 메서드를 ConcurrentModificationException throw 합니다).

LinkedList를 사용할 때와 ArrayList를 사용할 때?

• 위에서 설명한 것처럼 삽입 및 제거 작업은 ArrayList(O(n)) 비해 LinkedList (O(1)) 을 제공합니다.

  따라서 응용 프로그램에서 빈번한 추가 및 삭제 요구 사항이 있는 경우 LinkedList가 최선의 선택입니다.

• 검색( get method ) 작업은 Arraylist (O(1)) LinkedList (O(n)) 에서는 빠르지 않습니다.

  따라서 추가 및 제거 작업이 적고 검색 작업 요구 사항이 더 많은 경우 ArrayList가 가장 좋습니다.

Real73

ArrayList의 get(i) 작업은 다음과 같은 이유로 LinkedList보다 빠릅니다.
ArrayList: List 인터페이스의 크기 조정 가능한 배열 구현
LinkedList: List 및 Deque 인터페이스의 이중 연결 목록 구현

목록에 대한 색인을 생성하는 작업은 지정된 색인에 더 가까운 시작 또는 끝에서 목록을 순회합니다.

Amitābha

여기에서 본 테스트 중 하나는 테스트를 한 번만 수행합니다. 그러나 내가 알아차린 것은 이러한 테스트를 여러 번 실행해야 하며 결국 시간이 수렴된다는 것입니다. 기본적으로 JVM은 워밍업이 필요합니다. 내 특정 사용 사례의 경우 약 500개 항목으로 늘어나는 목록에 항목을 추가/제거해야 했습니다. 내 테스트에서 LinkedList 는 약 50,000 NS에서 들어오는 LinkedList 와 약 90,000 NS에서 들어오는 ArrayList 와 함께 더 빨리 나왔습니다. 아래 코드를 참조하십시오.

 public static void main(String[] args) { List<Long> times = new ArrayList<>(); for (int i = 0; i < 100; i++) { times.add(doIt()); } System.out.println("avg = " + (times.stream().mapToLong(x -> x).average())); } static long doIt() { long start = System.nanoTime(); List<Object> list = new LinkedList<>(); //uncomment line below to test with ArrayList //list = new ArrayList<>(); for (int i = 0; i < 500; i++) { list.add(i); } Iterator it = list.iterator(); while (it.hasNext()) { it.next(); it.remove(); } long end = System.nanoTime(); long diff = end - start; //uncomment to see the JVM warmup and get faster for the first few iterations //System.out.println(diff) return diff; }

Jose Martinez

remove() 와 insert() 는 모두 ArrayList와 LinkedList에 대해 O(n)의 런타임 효율성을 가지고 있습니다. 그러나 선형 처리 시간 뒤에 있는 이유는 매우 다른 두 가지 이유에서 비롯됩니다.

ArrayList에서는 O(1)의 요소에 도달하지만 실제로 다음 요소를 모두 변경해야 하기 때문에 무언가를 제거하거나 삽입하면 O(n)이 됩니다.

LinkedList에서는 원하는 인덱스에 도달할 때까지 맨 처음부터 시작해야 하기 때문에 실제로 원하는 요소에 도달하는 데 O(n)이 걸립니다. 실제로 제거하거나 삽입하는 것은 일정합니다. remove() insert() 대한 참조 2개만 변경하면 되기 때문입니다.

둘 중 삽입 및 제거가 더 빠른 것은 발생 위치에 따라 다릅니다. 시작에 가까우면 LinkedList가 더 빠를 것입니다. 상대적으로 적은 요소를 거쳐야 하기 때문입니다. 우리가 끝에 가까우면 ArrayList가 더 빠를 것입니다. 왜냐하면 우리는 일정한 시간 안에 거기에 도달하고 그 뒤에 오는 몇 가지 나머지 요소만 변경하면 되기 때문입니다. 중간에 정확하게 수행되면 n개의 요소를 통과하는 것이 n개의 값을 이동하는 것보다 빠르기 때문에 LinkedList가 더 빠를 것입니다.

보너스: ArrayList에 대해 이 두 가지 방법을 O(1)로 만드는 방법은 없지만 실제로 LinkedList에서 이를 수행하는 방법이 있습니다. 도중에 요소를 제거하고 삽입하는 전체 목록을 살펴보고 싶다고 가정해 보겠습니다. 일반적으로 LinkedList를 사용하여 각 요소의 맨 처음부터 시작하고 Iterator로 작업 중인 현재 요소를 "저장"할 수도 있습니다. Iterator의 도움으로 LinkedList에서 작업할 때 remove() 및 insert() 대해 O(1) 효율성을 얻습니다. LinkedList가 ArrayList보다 항상 더 나은 위치를 알고 있는 유일한 성능 이점으로 만듭니다.

pietz

ArrayList는 AbstractList를 확장하고 List 인터페이스를 구현합니다. ArrayList는 동적 배열입니다.
기본적으로 배열의 단점을 극복하기 위해 만들어졌다고 할 수 있습니다.

LinkedList 클래스는 AbstractSequentialList를 확장하고 List, Deque 및 Queue 인터페이스를 구현합니다.
성능
arraylist.get() 은 O(1)이고 linkedlist.get() 은 O(n)입니다.
arraylist.add() 는 O(1)이고 linkedlist.add() 는 0(1)입니다.
arraylist.contains() 는 O(n)이고 linkedlist.contains() 는 O(n)입니다.
arraylist.next() 는 O(1)이고 linkedlist.next() 는 O(1)입니다.
arraylist.remove() 는 O(n)이고 linkedlist.remove() 는 O(1)입니다.
배열 목록에서
iterator.remove() 는 O(n)입니다.
반면 링크드리스트에서는
iterator.remove() 는 O(1)입니다.

Randhawa

출처 : http:www.stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist-in-java