을 사용하는 경우 LinkedList 통해 ArrayList Java?
https://stackoverflow.com/questions/322715
-
11-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
나는 항상 하나는 단순히 사용:
List<String> names = new ArrayList<>();
내가 사용하여 인터페이스의 유형으로 이름 휴대, 도록 요청할 때 이런 질문을 내가할 수 있는 재생산 나의 코드입니다.
해야 할 때 LinkedList 사용상 ArrayList 역도 마찬가지로 편리하는가?
해결책
요약 ArrayList 가 ArrayDeque 는 것이 바람직에서 많 더 많은 사례상 LinkedList.당신이 확실하지 않은 경우—그냥 시작 ArrayList.
LinkedList 고 ArrayList 두 개의 다른 구현의 목록을 인터페이스입니다. LinkedList 를 구현하는것으로 이중 연결 목록입니다. ArrayList 를 구현하에 그것을 동적으로 다시 크기 배열입니다.
과 같은 표준에 연결 목록을 배열 작업을 다양한 방법이 다른 알고리즘 런타임입니다.
get(int index)가 O(n) (과 n/4 단계에서 평균)add(E element)가 O(1)add(int index, E element)가 O(n) (과 n/4 단계 평균) 지 O(1) 면index = 0<---의 주요 장점LinkedList<E>remove(int index)가 O(n) (과 n/4 단계에서 평균)Iterator.remove()가 O(1).<---의 주요 장점LinkedList<E>ListIterator.add(E element)가 O(1) 이것은 하나의 주요 장점LinkedList<E>
참고:많은 작업의 필요 n/4 단계에서 평균, 일정 수 단계에서 최고의 경우(예:index=0),고 n/2 단계에서 최악의 경우에는(중앙의 목록)
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>, 에,다른 한편으로는,빠르게 임의의 읽 액세스할 수 있도록 잡아에 있는 모든 요소를 일정한 시간입니다.추가하거나 삭제 어디에서나 필요로 이동 모든 후기 요소를 통해 하나를 만드는 개방 또는니다.또한,더 추가하는 경우 추가 요소의 용량보다 근본적인 배열,new array(1.5 시간의 크기)를 할당하고,오래 된 배열로 복사하고 새로운 중 하나,그래서하여 ArrayList 가 O(n) 최악의 경우에는 그러나 일정한 평균.
그래서에 따라 작업을 수행하려는 선택해야 하 구현합니다.반복을 통해 두 종류의 목록은 실질적으로 동등하게 저렴합니다.(반복하는 ArrayList 기술적으로 더 빨리,하지만 당신은 뭔가 정말 중요한 성능,에 대해 걱정할 필요는 없이-그들은 모두 상수입니다.)
의 주요 혜택 사용 LinkedList 이 발생할 때 당신은 다시 사용하는 기존 반복기를 삽입하고 제거하는 요소입니다.이러한 작업을 수 있습니다 다음 수행에 O(1) 을 변경하여 목록에 로컬로만 있습니다.배열에 있는 목록의 나머지 부분에 배열해야 이동 (i.e복사된).다른 측면에서 찾에 LinkedList 다음과 같은 의미에서 링크 O(n) (n/2 단계)에 대한 최악의 경우,반면에 ArrayList 원하는 위치를 계산할 수 있는 수학과에서 액세스 O(1).
의 또 다른 혜택 사용 LinkedList 이 발생할 경우를 추가하거나 제거에서 머리의 목록은,이런 작업 O(1), 하는 동안,그들은 O(n) 대 ArrayList.Note ArrayDeque 할 수 있는 좋은 대안 LinkedList 에 대한 추가 및 제거,머리에서 하지만 그것은 아닙 List.
또한,이 있는 경우 큰 목록 하는 마음에서 메모리 사용량이 다르다.의 각 요소 LinkedList 더 많은 오버헤드 이 포인터는 다음 요소 또한 저장된다. ArrayLists 이 없이 오버헤드가 발생합니다.그러나, ArrayLists 많은 메모리를 할당된 수용량,는지 여부에 관계없이 요소가 실제로 추가되었습니다.
기본값 초기 용량의 ArrayList 은 아주 작은(10 에서 Java1.4-1.8).하지만 이후 기본 구현은 배열,배열의 크기를 조정해야 합를 추가하는 경우 많은 요소로 구성되어 있습니다.을 방지하는 높은 비용의 크기를 조정하는 경우에 당신을 추가하려고 많은 요소의 구성 ArrayList 은 높은 초기 용량입니다.
다른 팁
지금까지 아무도 일반적인 합의 외에이 각 목록의 메모리 발자국을 다루지 않은 것 같습니다. LinkedList "훨씬 더 많다"는 것입니다 ArrayList 그래서 나는 null 참조를 위해 두 목록이 얼마나 많이 차지하는지 정확히 보여주기 위해 약간의 크 런칭을했습니다.
상대 시스템에서 참조는 32 또는 64 비트 (NULL 일 때도)이므로 32 및 64 비트에 4 개의 데이터 세트를 포함 시켰습니다. LinkedLists 그리고 ArrayLists.
메모: 크기가 표시됩니다 ArrayList 라인은 용입니다 트림 된 목록 - 실제로, 백업 배열의 용량은 ArrayList 일반적으로 현재 요소 수보다 큽니다.
노트 2: (감사합니다 BeeonRope) Compressedoops는 JDK6 중반에서 현재 기본값이므로 64 비트 머신의 아래 값은 기본적으로 32 비트 대응 물과 일치합니다.
결과는 분명히 그것을 보여줍니다 LinkedList 보다 훨씬 더 많습니다 ArrayList, 특히 매우 높은 요소 수를 사용합니다. 메모리가 요인이라면 피하십시오 LinkedLists.
내가 사용한 공식은 다음과 같은 일을 한 경우 알려 주시면 문제를 해결하겠습니다. 'B'는 32 또는 64 비트 시스템의 경우 4 또는 8이며, 'n'은 요소의 수입니다. MOD의 이유는 Java의 모든 객체가 모두 사용 여부에 관계없이 8 바이트 공간의 배수를 차지하기 때문입니다.
ArrayList :
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 :
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)
ArrayList 당신이 원하는 것입니다. LinkedList 거의 항상 (성능) 버그입니다.
왜 LinkedList 짜증 :
- 작은 메모리 객체를 많이 사용하므로 프로세스 전반에 걸쳐 성능에 영향을 미칩니다.
- 많은 작은 물체가 캐시-초점에 좋지 않습니다.
- 모든 인덱스 작업에는 트래버스가 필요하며 즉, O (N) 성능이 있습니다. 소스 코드에서는 분명하지 않으며 알고리즘 O (N)가
ArrayList사용되었습니다. - 좋은 성능을 얻는 것은 까다 롭습니다.
- Big-O 성능이 동일하더라도
ArrayList, 어쨌든 그것은 아마도 훨씬 느리게 될 것입니다. - 보는 것은 부끄러운 일입니다
LinkedList아마도 잘못된 선택이기 때문에 소스에서.
약 10 년 동안 매우 대규모 SOA 웹 서비스에서 운영 성과 엔지니어링을해온 사람으로서 ArrayList보다 LinkedList의 동작을 선호합니다. LinkedList의 정상 상태 처리량이 악화되어 더 많은 하드웨어를 구매할 수 있지만 압력을받는 Arraylist의 동작은 클러스터의 앱이 동기식으로 배열을 확장하여 대량의 어레이 크기를 제공 할 수 있습니다. 앱과 정전에서 압력을받는 동안 치명적인 행동입니다.
마찬가지로, 기본 처리량 임기 쓰레기 수집기에서 앱에서 더 나은 처리량을 얻을 수 있지만, 10GB 힙으로 10GB 힙으로 Java 앱을 받으면 전체 GCS에서 25 초 동안 앱을 잠그면 SOA 앱에서 타임 아웃 및 고장을 일으킬 수 있습니다. 너무 자주 발생하면 SLA를 불어냅니다. CMS 수집가가 더 많은 리소스를 취하고 동일한 원시 처리량을 달성하지 않더라도 예측 가능하고 더 작은 대기 시간이 있기 때문에 훨씬 더 나은 선택입니다.
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)
ArrayLists 좋은 대한 기록-읽기 또는 appenders 지만,나쁜 추가/제거에서 전면 또는 중간에 있습니다.
그래, 나는이 문제가 고대 질문이지만, 나는 2 센트를 던질 것이다.
Linkedlist입니다 거의 언제나 잘못된 선택, 성능면. 링크 사전 목록을 요구하는 매우 구체적인 알고리즘이 있지만, 이들은 매우 드물며 알고리즘은 일반적으로 LinkedList의 LinkedList의 기능에 따라 달라집니다. ListIterator와 함께.
LinkedList가 ArrayList를 능가하는 공통 사용 사례가 하나 있습니다. 그러나 목표가 성능 인 경우 링크 사전 목록 대신 ArrayBlockingqueue (미리 큐 크기의 상한을 결정할 수 있고 모든 메모리를 전면에 할당 할 수있는 경우) 또는이를 고려해야합니다. CircularArraylist 구현. (예, 2001 년부터 생성해야하지만 최근 JVM에서 기사에서 인용 한 것과 비슷한 성능 비율을 얻었습니다).
효율성 질문입니다. LinkedList 요소를 추가하고 삭제하는 데 빠르지 만 특정 요소에 액세스하는 데 속도가 느립니다. ArrayList 특정 요소에 액세스하기 위해서는 빠르지 만 양쪽 끝에 추가하는 데 속도가 느리고 특히 중간에 삭제하는 데 속도가 느릴 수 있습니다.
Array vs Arraylist vs LinkedList vs Vector 처럼 더 깊이 진행됩니다링크 된 목록.
정확하거나 잘못 : 로컬로 테스트를 실행하고 직접 결정하십시오!
편집/제거가 더 빠릅니다 LinkedList ~보다 ArrayList.
ArrayList, 후원 Array, 크기의 두 배가되어야하는 것은 대량 적용에서 더 나쁩니다.
아래는 각 작업에 대한 단위 테스트 결과입니다. 타임은 나노초로 나와 있습니다.
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);
}
}
ArrayList 본질적으로 배열입니다. LinkedList 이중 링크 목록으로 구현됩니다.
그만큼 get 꽤 분명합니다. o (1) ArrayList, 왜냐하면 ArrayList 인덱스를 사용하여 임의의 액세스를 허용합니다. o (n) LinkedList, 먼저 색인을 찾아야하기 때문에. 참고 : 다른 버전이 있습니다 add 그리고 remove.
LinkedList 추가 및 제거는 더 빠르지 만 Get은 느려집니다. 간단히, LinkedList 다음과 같은 경우 선호해야합니다.
- 요소의 무작위 액세스가 많지 않습니다.
- 많은 수의 추가/제거 작업이 있습니다.
=== 배열 목록 ===
- 추가 (E E)
- ArrayList의 끝에 추가하십시오
- 메모리 크기 조정 비용이 필요합니다.
- o (n) 최악, o (1) 상각
- 추가 (int index, e 요소)
- 특정 인덱스 위치에 추가하십시오
- 이동 및 메모리 크기 조정 비용이 필요합니다
- 에)
- 제거 (int index)
- 지정된 요소를 제거하십시오
- 이동 및 메모리 크기 조정 비용이 필요합니다
- 에)
- 제거 (Object O)
- 이 목록에서 지정된 요소의 첫 번째 발생을 제거하십시오.
- 요소를 먼저 검색 한 다음 이동 및 가능한 메모리 크기 조정 비용
- 에)
=== Linkedlist ===
추가 (E E)
- 목록의 끝에 추가하십시오
- o (1)
추가 (int index, e 요소)
- 지정된 위치에 삽입하십시오
- 먼저 위치를 찾아야합니다
- 에)
- 제거하다()
- 목록의 첫 번째 요소를 제거하십시오
- o (1)
- 제거 (int index)
- 지정된 인덱스로 요소를 제거합니다
- 먼저 요소를 찾아야합니다
- 에)
- 제거 (Object O)
- 지정된 요소의 첫 번째 발생을 제거하십시오
- 먼저 요소를 찾아야합니다
- 에)
여기에 그림이 있습니다 programcreek.com (add 그리고 remove 첫 번째 유형, 즉 목록 끝에 요소를 추가하고 목록의 지정된 위치에서 요소를 제거합니다.) : :
LinkedList의 저자 인 Joshua Bloch :
누구든지 실제로 LinkedList를 사용합니까? 나는 그것을 썼고 결코 그것을 사용하지 않습니다.
링크: https://twitter.com/joshbloch/status/583813919019573248
다른 답변처럼 유익하지 않다는 답변에 대해 유감스럽게 생각하지만, 그것이 가장 흥미롭고 자기 설명 할 것이라고 생각했습니다.
ArrayList 무작위로 액세스 할 수 있습니다 LinkedList 요소를 확장하고 제거하는 것이 정말 저렴합니다. 대부분의 경우 ArrayList 괜찮습니다.
큰 목록을 만들고 병목 현상을 측정하지 않으면 차이에 대해 걱정할 필요가 없습니다.
나는 이것이 오래된 게시물이라는 것을 알고 있지만, 나는 아무도 그것을 언급하지 않는다고 믿을 수 없다. LinkedList 구현 Deque. 방법을 살펴보십시오 Deque (그리고 Queue); 공정한 비교를 원한다면 달리기를 시도하십시오 LinkedList 에 맞서 ArrayDeque 기능적 비교를 수행합니다.
다음은 두 가지 모두에서 큰 표기법입니다 ArrayList 그리고 LinkedList 그리고 또한 CopyOnWrite-ArrayList:
배열 목록
get O(1)
add O(1)
contains O(n)
next O(1)
remove O(n)
iterator.remove O(n)
Linkedlist
get O(n)
add O(1)
contains O(n)
next O(1)
remove O(1)
iterator.remove O(1)
복사기-배열 목록
get O(1)
add O(n)
contains O(n)
next O(1)
remove O(n)
iterator.remove O(n)
이것을 기반으로 선택해야 할 사항을 결정해야합니다. :)
tl; dr 현대적인 컴퓨터 아키텍처로 인해 ArrayList 거의 모든 가능한 사용 사례에 대해 훨씬 더 효율적이므로 LinkedList 매우 독특하고 극단적 인 경우를 제외하고는 피해야합니다.
이론적으로 LinkedList에는 O (1)에 add(E element)
또한 목록 중간에 요소를 추가하는 것은 매우 효율적이어야합니다.
Linkedlist는 a 캐시 적대 데이터 구조. Performance POV에서 - 사례는 거의 없습니다. LinkedList 보다 더 잘 수행 할 수 있습니다 캐시 친화적입니다 ArrayList.
다음은 임의의 위치에 요소를 삽입하는 벤치 마크 테스트 결과입니다. 보시다시피 - 배열 목록은 훨씬 더 효율적이지만 이론적으로 목록의 중간에 각각 삽입물은 "이동"이 필요합니다. N 배열의 이후 요소 (낮은 값이 더 좋습니다) :
후기 세대 하드웨어 (더 크고 효율적인 캐시)에서 작업 - 결과는 훨씬 더 결정적입니다.
LinkedList는 동일한 작업을 수행하는 데 훨씬 더 많은 시간이 걸립니다. 원천 소스 코드
여기에는 두 가지 주된 이유가 있습니다.
주로 - 그 노드
LinkedList메모리에 무작위로 흩어져 있습니다. RAM ( "Random Access Memory")은 실제로 무작위가 아니며 메모리 블록을 캐시로 가져와야합니다. 이 작업에는 시간이 걸리고 이러한 페치가 자주 발생하면 캐시의 메모리 페이지를 항상 교체해야합니다 -> 캐시 미스 -> 캐시는 효율적이지 않습니다.ArrayList요소는 연속 메모리에 저장됩니다. 이것은 최신 CPU 아키텍처가 최적화하는 것입니다.중고등 학년
LinkedList보류/전달 포인터를 유지해야합니다. 이는 다음과 비교하여 저장된 값 당 메모리 소비의 3 배를 의미합니다.ArrayList.
DynamicIntArray, BTW는 사용자 정의 ArrayList 구현 보유입니다 Int (원시 유형) 객체가 아닌 (원시 유형), 따라서 모든 데이터는 실제로 인접하게 저장되어있어 훨씬 더 효율적입니다.
기억해야 할 핵심 요소는 메모리 블록을 가져 오는 비용이 단일 메모리 셀에 액세스하는 비용보다 더 중요하다는 것입니다. 그렇기 때문에 독자 1MB의 순차 메모리가 다른 메모리 블록 에서이 양의 데이터를 읽는 것보다 최대 x400 배 더 빠릅니다.
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. 더 많은 데이터를 찾을 수 있습니다 그의 블로그
링크드리스트 및 ArrayList WRT를 아래에 비교해 보겠습니다.
1. 구현
배열 목록 목록 인터페이스의 Resized 가능한 배열 구현, 반면
Linkedlist 목록 인터페이스의 이중 연결 목록 구현입니다.
2. 성능
get (int index) 또는 검색 작업
배열 목록 get (int index) 작동은 일정한 시간에 실행됩니다. 즉, O (1)
Linkedlist get (int index) 작동 실행 시간은 O (n)입니다.
뒤에있는 이유 배열 목록 LinkedList보다 빠르는 것은 ArrayList가 내부적으로 배열 데이터 구조를 사용하므로 요소에 인덱스 기반 시스템을 사용한다는 것입니다.
Linkedlist 지정된 요소 인덱스에서 노드를 검색하기 위해 시작 또는 끝에서 (더 가까운 지) 반복하므로 요소에 대한 인덱스 기반 액세스를 제공하지 않습니다.
삽입 () 또는 추가 (개체) 작업
삽입 Linkedlist ArrayList와 비교하여 일반적으로 빠릅니다. LinkedList에서 추가 또는 삽입은 O (1) 작동입니다.
들어있는 동안 배열 목록, 배열이 최악의 경우 최악의 경우 배열 크기 조정 및 복사 요소를 새 배열로 복사하는 데 추가 비용이 발생하여 ArrayList O (N)에서 추가 작업을 수행하는 경우 O (1)입니다.
(int) 작업을 제거하십시오
LinkedList에서 작업을 제거하는 것은 일반적으로 ArrayList, 즉 O (N)과 동일합니다.
~ 안에 Linkedlist, 두 개의 과부하 제거 방법이 있습니다. 하나는 목록의 헤드를 제거하고 일정한 시간에 실행되는 매개 변수가없는 제거 ()입니다. O (1). LinkedList에서 다른 과부하 제거 된 제거 메소드는 객체를 제거하거나 매개 변수로 전달되는 int를 제거하는 (int) 또는 제거 (개체)입니다. 이 메소드는 객체를 찾을 때까지 링크 사전 목록을 가로 지르고 원래 목록에서 indink습니다. 따라서이 방법 런타임은 O (n)입니다.
들어있는 동안 배열 목록 제거 (int) 메소드에는 이전 배열에서 새 업데이트 배열로 요소를 복사하는 것이 포함되므로 런타임은 O (n)입니다.
3. 역 반복자
Linkedlist 내림차순으로 반복 할 수 있습니다.
내림차순이 없습니다 배열 목록 , 우리는 배열리스트를 반대 방향으로 반복하기 위해 자체 코드를 작성해야합니다.
4. 초기 용량
생성자가 과부하되지 않은 경우 배열 목록 초기 용량 10의 빈 목록을 만듭니다.
Linkedlist 초기 용량없이 빈 목록 만 구성합니다.
5. 메모리 오버 헤드
메모리 오버 헤드 Linkedlist LinkedList의 노드로서 ArrayList와 비교하여 다음 노드 및 이전 노드의 주소를 유지해야합니다. 하는 동안
~ 안에 배열 목록 각 색인은 실제 객체 (데이터) 만 보유합니다.
위의 다른 좋은 주장 외에도 주목해야합니다. ArrayList 구현 RandomAccess 인터페이스 LinkedList 구현 Queue.
따라서 어떻게 든 효율성과 행동의 차이로 약간 다른 문제를 해결합니다 (방법 목록 참조).
보다 Java 자습서 - 구현 목록.
배열 목록은 기본적으로 항목 등을 추가하는 메소드가있는 배열입니다 (대신 일반 목록을 사용해야합니다). 인덱서를 통해 액세스 할 수있는 항목 모음입니다 (예 : [0]). 그것은 하나의 항목에서 다음 항목으로 진행을 의미합니다.
링크 된 목록은 한 항목에서 다음 항목으로 진행을 지정합니다 (항목 A-> 항목 B). 배열 목록으로 동일한 효과를 얻을 수 있지만 링크 된 목록은 이전 항목을 따라야 할 항목을 절대적으로 말합니다.
목록에서 더 많은 작업을 수행 할 작업에 따라 다릅니다.
ArrayList 색인 값에 액세스하는 것이 더 빠릅니다. 객체를 삽입하거나 삭제할 때 훨씬 더 나쁩니다.
자세한 내용은 배열과 링크 된 목록의 차이점에 대해 설명하는 기사를 읽으십시오.
나는 보통 특정 목록에서 수행 할 작업의 시간 복잡성을 기반으로 다른 하나를 사용합니다.
|---------------------|---------------------|--------------------|------------|
| 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 |
|--------------------------------------|
링크 된 목록의 중요한 기능 (다른 답변에서 읽지 않은)은 두 목록을 연결하는 것입니다. 배열의 경우 이것은 링크 된 목록이있는 O (n) (일부 재 할당의 오버 헤드)입니다. 이것은 O (1) 또는 O (2) ;-)입니다.
중요한: Java를 위해 LinkedList 이것은 사실이 아닙니다! 보다 Java에서 링크 된 목록에 대한 빠른 동의 방법이 있습니까?
응답을 읽었지만 의견을 듣기 위해 공유하고 싶은 Arraylist를 통해 항상 LinkedList를 사용하는 시나리오가 있습니다.
DB에서 얻은 데이터 목록을 반환하는 메소드가있을 때마다 항상 LinkedList를 사용합니다.
내 근거는 내가 얼마나 많은 결과를 얻었는지 정확히 알 수 없기 때문에 메모리 낭비가 없을 것이며 (용량과 실제 요소 수의 차이를 가진 Arraylist에서와 같이), 시간 낭비를 시도하지 않을 것입니다. 용량을 복제하십시오.
Arraylist는 최소한 최소한 초기 용량으로 생성자를 사용하여 배열의 복제를 최대한 최소화해야한다는 데 동의합니다.
ArrayList 및 LinkedList에는 자체 장단점이 있습니다.
ArrayList는 다음 노드를 향한 포인터를 사용하는 LinkedList에 비해 연속 메모리 주소를 사용합니다. 따라서 Arraylist에서 요소를 찾으려면 LinkedList로 N 반복을 수행하는 것보다 빠릅니다.
반면에, 링크 사전 목록의 삽입 및 삭제는 포인터를 변경 해야하는 반면 Arraylist는 삽입 또는 삭제에 대한 시프트 작업을 사용하는 것을 의미하기 때문에 훨씬 쉽습니다.
앱에서 검색 작업이 빈번한 경우 Arraylist를 사용하십시오. 자주 삽입 및 삭제가있는 경우 링크 사전 목록을 사용하십시오.
ArrayList 고 LinkedList 모두 구현하는 List interface 과 그들의 방법과 결과가 거의 동일합니다.그러나 거기에 몇 가지 그들 사이의 차이점을 하나 더 이상 다른 요구 사항에 따라.
ArrayList 대 LinkedList
1) Search: ArrayList 검색 작업은 매우 빠르게 비교 LinkedList 검색 작업입니다. get(int index) 에 ArrayList 의 성능을 제공합 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 추가 방법을 제공합 O(1) 이면서 성능 ArrayList 공 O(n) 최악의 경우입니다.이와 같은 설명을 위해 제거합니다.
4) Memory Overhead: ArrayList 지 인덱스와 요소는 동안 데이터 LinkedList 유지 요소 데이터 및 두 개의 포인터를 위한 이웃 노드
따라서 메모리 소비가 높은 LinkedList 비교.
거기에 몇 가지 사이에 유사성이 이러한 클래스는 다음과 같습니다:
- 모두 ArrayList 및 LinkedList 가의 이행 목록을 인터페이스입니다.
- 그들은 모두 유지하는 요소를 삽입해 의미하는 표시되는 동안 ArrayList 및 LinkedList 요소를 결정할 것이라고 같은 순서 요소를 가지고 삽입니다.
- 모두 이 클래스들은 동기화되지 않고 만들 수 있는 동기화를 이용하여 명시적으로 컬렉션이 있습니다.synchronizedList 방법입니다.
- 이
iterator고listIterator반환에 의해 이러한 클래스fail-fast(면 목록은 구조적으로 언제든지 수정 후에는 반복기를 만들어서,어떤 방법을 제외하고해iterator’s자체를 제거하거나 추가 방법,반복자throwaConcurrentModificationException).
을 사용하는 경우 LinkedList 고 사용하는 경우 ArrayList?
- 위에서 설명한 바와 같이 삽입 및 제거 작업을 좋은 성능
(O(1))에LinkedList비ArrayList(O(n)).따라서가 있다면 요구 사항의 빈번한 추가 및 삭제 응용 프로그램에서 다음 LinkedList 는 최고의 선택입니다.
- 검색(
get method)작업에서 빠른Arraylist (O(1))지LinkedList (O(n))그래서 있는 경우에는 더 적은 추가 및 제거 작업과 더 많은 검색 작업이 필요조건,ArrayList 것 당신의 최선의 방법입니다.
ArrayList의 작동 (i)은 링크드리스트보다 빠릅니다.
ArrayList : 목록 인터페이스의 Resizable-Array 구현
LinkedList : 목록 및 deque 인터페이스의 이중 연결 목록 구현
목록에 색인이있는 작업은 처음 또는 끝에서 목록을 가로 지르며 지정된 인덱스에 더 가까운 것.
1) 기본 데이터 구조
ArrayList와 LinkedList의 첫 번째 차이점은 ArrayList가 Array에 의해 뒷받침되고 LinkedList는 LinkedList에 의해 뒷받침된다는 사실과 함께 제공됩니다. 이로 인해 성능이 더 큰 차이가 생길 것입니다.
2) Linkedlist는 Deque를 구현합니다
ArrayList와 LinkedList의 또 다른 차이점은 List Interface를 제외하고 LinkedList는 Deque Interface를 구현한다는 것입니다.이 인터페이스는 Add () 및 Polle () 및 기타 여러 Deque 함수에 대한 첫 번째 Out 작업에서 첫 번째 작업을 제공한다는 것입니다. 3) ArrayList에 요소 추가 ArrayList에 요소 추가 요소가 O (1) ATURANT IS ARRAY의 크기를 트리거하지 않으면 작동합니다. 반면에 O (log (n))가됩니다. 링크드 목록은 내비게이션이 필요하지 않으므로 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)입니다. O (n/2)는 LinkedList에서 해당 항목까지 가로 질러 이동해야합니다. 그러나 큰 o 표기법에서 o (n/2)는 상수를 무시하기 때문에 O (n)입니다.
7) 메모리
LinkedList는 데이터를 저장하기위한 정적 중첩 클래스 인 래퍼 객체 인 Entry를 사용하고 다음과 이전에 두 개의 노드를 저장하는 동안 ArrayList는 데이터를 배열에 저장합니다.
따라서 ArrayList의 경우 링크드리스트보다 메모리 요구 사항이 덜 보이는 경우 어레이가 한 배열에서 다른 배열로 컨텐츠를 복사 할 때 재조정 작업을 수행하는 경우를 제외하고는 메모리 요구 사항이 덜 보입니다.
배열이 충분히 크면 해당 시점에서 많은 메모리가 필요하고 쓰레기 수집을 트리거하여 응답 시간이 느려질 수 있습니다.
ArrayList와 LinkedList의 위의 모든 차이점에서 raylist는 remove () 또는 get ()보다 자주 add () 작업을 수행 할 때를 제외하고는 거의 모든 경우 링크드리스트보다 더 나은 선택입니다.
특히 링크 된 목록이 해당 위치에 대한 내부 참조를 유지하고 O (1) 시간에 액세스 할 수 있기 때문에 ArrayList보다 링크 된 목록을 수정하는 것이 더 쉽습니다.
다시 말해, 요소를 추가하려는 위치에 도달하기 위해 링크 된 목록을 통과 할 필요가 없습니다.이 경우 추가는 O (n) 작동이됩니다. 예를 들어, 링크 된 목록의 중간에 요소를 삽입하거나 삭제합니다.
제 생각에는 Java의 실질적인 목적의 대부분을 위해 LinkedList를 통해 ArrayList를 사용하십시오.
remove () 및 insert () 모두 ArrayList 및 LinkedList 모두에 대해 O (N)의 런타임 효율이 있습니다. 그러나 선형 처리 시간의 이유는 두 가지 매우 다른 이유에서 비롯됩니다.
Arraylist에서는 O (1)의 요소에 도달하지만 실제로 무언가를 제거하거나 삽입하면 다음 요소가 모두 변경되어야하기 때문에 O (N)가됩니다.
LinkedList에서는 원하는 인덱스에 도달 할 때까지 처음부터 시작해야하기 때문에 실제로 원하는 요소에 도달하는 데 O (N)가 필요합니다. 실제로 제거하거나 삽입하는 것은 일정합니다. remove ()에 대해 1 참조와 insert ()에 대해 2 참조 만 변경하면됩니다.
이 둘 중 어느 것이 삽입 및 제거에 더 빠른가? 우리가 처음에 가까워지면 링크 사전 목록이 더 빨라질 것입니다. 왜냐하면 우리는 상대적으로 적은 요소를 거쳐야하기 때문입니다. 우리가 끝까지 가까이 있으면 어레이 목록이 더 빠르면 더 빠르게 진행될 것입니다. 왜냐하면 우리는 일정한 시간에 도착하고 그 뒤를 따르는 나머지 요소 만 변경해야하기 때문입니다. 중간에 정확하게 수행되면 N 요소를 통과하는 것이 N 값을 이동하는 것보다 빠르기 때문에 링크 사전 목록이 더 빠릅니다.
보너스 : 배열 목록의 경우이 두 가지 방법을 O (1)로 만드는 방법은 없지만 실제로 링크 사전 목록에서이를 수행 할 수있는 방법이 있습니다. 길에 요소를 제거하고 삽입하는 전체 목록을 살펴보고 싶다고 가정 해 봅시다. 일반적으로 LinkedList를 사용하여 각 요소의 시작부터 시작하여 반복자와 함께 작업하는 현재 요소를 "저장"할 수도 있습니다. 반복자의 도움으로 LinkedList에서 작업 할 때 remove () 및 insert ()에 대한 O (1) 효율성을 얻습니다. 링크 사전 목록이 항상 배열 목록보다 더 나은 곳을 알고있는 유일한 성능 이점으로 만듭니다.
ArrayList는 AbstractList를 확장하고 목록 인터페이스를 구현합니다. ArrayList는 동적 배열입니다.
기본적으로 배열의 단점을 극복하기 위해 만들어 졌다고 말할 수 있습니다.
LinkedList 클래스는 Abstract evectientlist 및 implements 목록, deque 및 큐 인터페이스를 확장합니다.
성능
arraylist.get() O (1)입니다 linkedlist.get() is o (n)
arraylist.add() O (1) 및 linkedlist.add() IS 0 (1)
arraylist.contains() O (n) 및linkedlist.contains() is o (n)
arraylist.next() O (1) 및 linkedlist.next() is o (1)
arraylist.remove() O (n)이지만 linkedlist.remove() is o (1)
ArrayList에서iterator.remove() is o (n)
링크드 목록에 있습니다 iterator.remove()is o (1)
내가 여기서 본 테스트 중 하나는 테스트를 한 번만 수행합니다. 그러나 내가 알아 차린 것은이 테스트를 여러 번 실행해야한다는 것입니다. 결국 그들의 시간은 수렴 될 것입니다. 기본적으로 JVM은 워밍업해야합니다. 내 특정 유스 케이스의 경우 약 500 개 항목으로 자라는 마지막으로 품목을 추가/제거해야했습니다. 내 테스트에서 LinkedList 링크 된 상태에서 더 빨리 나왔습니다 LinkedList 약 50,000 ns에옵니다 ArrayList 약 90,000 ns에 들어 오세요 ... 주거나 가져 가라. 아래 코드를 참조하십시오.
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;
}
