Java에서 LinkedList over ArrayList를 사용하는 시기
나는 항상 간단하게 사용해 왔다.
List<String> names = new ArrayList<>();
나는 휴대성을 위해 인터페이스를 유형 이름으로 사용하므로, 이와 같은 질문을 할 때 코드를 다시 작업할 수 있다.
그 반대는 언제 다시 사용되어야 하는가?
ArrayList와 함께ArrayDeque보다 훨씬 더 많은 사용 사례에서 선호된다.LinkedList. 잘 모르겠으면 — 시작부터ArrayList.
TLDR, ArrayList에서 요소에 액세스하는 데 일정한 시간이 걸리고 [O(1)] 요소를 추가하는 데 O(n) 시간이 걸린다[최악의 경우].LinkedList에서 요소를 추가하는 데 O(n) 시간이 걸리고 액세스에도 O(n) 시간이 걸리지만 LinkedList는 ArrayList보다 더 많은 메모리를 사용한다.
LinkedList그리고ArrayList목록 인터페이스의 두 가지 다른 구현이다. LinkedList그것을 이중 연계 리스트로 구현한다. ArrayList동적으로 재프로그래밍된 어레이로 구현.
표준 링크된 목록과 배열 연산처럼, 다양한 방법들은 다른 알고리즘 런타임을 가질 것이다.
을 위해
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단계가 필요함(목록 중간)
을 위해
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)은 O(n)이다.index = 0.
ArrayList<E>반면에 빠른 임의 읽기 액세스를 허용하여 일정한 시간에 어떤 요소도 잡을 수 있다.그러나 끝이 아닌 곳에서 추가 또는 제거하려면 모든 후자의 요소를 위로 이동시켜야 하며, 이는 개구부를 만들거나 공백을 메우기 위해 필요하다.또한 기본 어레이의 용량보다 요소를 더 추가하면 새 어레이(크기의 1.5배)가 할당되고 이전 어레이가 새 어레이에 복사되므로ArrayList최악의 경우 O(n)이지만 평균적으로 일정하다.
따라서 하고자 하는 작업에 따라 그에 따라 구현을 선택해야 한다.두 종류의 리스트에 대해 반복하는 것은 사실상 똑같이 싸다.ArrayList기술적으로는 더 빠르지만, 만약 여러분이 정말로 성능에 민감한 일을 하고 있지 않다면, 여러분은 이것에 대해 걱정하지 말아야 한다. 둘 다 상수다.)
사용의 주요 이점은LinkedList기존 반복기를 재사용하여 요소를 삽입 및 제거할 때 발생.이 작업은 로컬에서만 목록을 변경하여 O(1)에서 수행할 수 있다.배열 목록에서 나머지 배열은 이동해야 한다(예: 복사).반대편에서, 찾으려고.LinkedList최악의 경우 O(n) (n/2단계)의 링크를 따르는 것을 의미하지만ArrayList원하는 위치는 수학적으로 계산할 수 있으며 O(1)에서 액세스할 수 있다.
사용의 또 다른 이점LinkedList해당 작업은 O(1)이고 O(n)는 O(n)이기 때문에 목록 머리글에서 추가하거나 제거할 때 발생한다.ArrayList. 참고하십시오.ArrayDeque의 좋은 대안이 될 수도 있다LinkedList머리에서 추가 및 제거하기 위해, 그러나 그것은List.
또한 목록이 크면 메모리 사용량도 다르다는 점을 명심하십시오.의 각 .LinkedList다음 요소와 이전 요소에 대한 포인터도 저장되므로 오버헤드가 더 크다. ArrayLists머리 위에 이런 거 없어.하지만ArrayLists요소가 실제로 추가되었는지 여부에 관계없이 용량에 할당된 만큼의 메모리를 차지하십시오.
의 기지의 량.량.량.량.ArrayList상당히 작다(Java 1.4 - 1.8에서 10).그러나 기본 구현은 어레이이므로 요소를 많이 추가할 경우 어레이의 크기를 조정해야 한다.많은 요소를 추가할 것으로 알고 있을 때 크기 조정 비용이 많이 들지 않도록 하려면ArrayList초기 용량이 더 큰
데이터 구조 관점이 두 구조를 이해하는 데 사용되는 경우, LinkedList는 기본적으로 헤드 노드를 포함하는 순차적 데이터 구조다.노드는 두 가지 구성요소에 대한 래퍼로, T형식의 값 [생물을 통해 허용됨]과 그것에 연결된 노드에 대한 또 다른 참조가 그것이다.따라서, 우리는 그것이 재귀적 데이터 구조라고 주장할 수 있다(노드는 다른 노드 등을 가진 다른 노드를 포함한다...).위에 언급한 LinkedList에서 요소의 추가는 선형 시간이 걸린다.
ArrayList는 확장 가능한 배열이다.그것은 마치 일반적인 배열과 같다.후드 아래에서 요소가 추가되고 ArrayList가 이미 용량이 가득 차면 이전 크기보다 큰 크기의 다른 어레이를 생성한다.그런 다음 이전 배열에서 새 배열로 요소를 복사하고 추가될 요소도 지정된 인덱스에 배치한다.
지금까지, 이 목록들 각각에 대한 기억의 발자국을 다루지 않은 사람은, a라는 일반적인 합의 외에 아무도 없는 것 같다.LinkedList보다 "더 많은" 것 입니다.ArrayList그래서 나는 NN null reference에 대해 두 리스트가 얼마나 많이 차지하는지를 정확히 보여주기 위해 몇 가지 숫자들을 바삭바삭 했다.
참조가 상대 시스템에 32비트 또는 64비트(null일 때도)이므로, 나는 32비트 및 64비트용 데이터 4세트를 포함시켰다.LinkedLists그리고ArrayLists.
참고: 에 표시된 크기ArrayList선은 잘라낸 리스트를 위한 것이다 - 실제로, 백업 배열의 용량은ArrayList일반적으로 현재 요소 개수보다 크다.
참고 2: (감사함 BeeOnRope) JDK6 이상 버전에서는 CompressedOops가 기본 설정이기 때문에 64비트 시스템의 아래 값은 32비트 버전과 기본적으로 일치하며, 물론 특별히 끄지 않는 한,
그 결과를 보면 분명히 알 수 있다.LinkedList보다 훨씬 더 많다ArrayList특히 요소 수가 매우 높은 경우.메모리가 요인일 경우 에서 멀리 조향하십시오.LinkedLists.
내가 사용한 공식은 내가 잘못한 것이 있으면 알려주고 고쳐주겠다. 32비트나 64비트 시스템에 대해 'b'는 4 또는 8이고, 'n'은 원소의 수이다.모드의 이유에 주목하십시오. 모든 사용 여부와 상관없이 자바에 있는 모든 개체가 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:
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사용되었다. - 좋은 성과를 얻는 것은 어렵다.
- 빅 O 성능이 다음과 같을 때에도
ArrayList어쨌든 상당히 느려질 것이다. - 보기만 해도 거슬린다.
LinkedList왜냐하면 그것은 아마도 잘못된 선택이기 때문이다.
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 표기법(보관)
배열 목록은 한 번 읽을 수 있는 다수 또는 부록에는 좋지만 전면 또는 중간에서 추가/제거하는 데는 좋지 않다.
약 10년 동안 대규모 SOA 웹 서비스에서 운영 성능 엔지니어링을 해온 사람으로서, ArrayList보다 LinkedList의 행동을 선호한다.LinkedList의 정상 상태 처리량이 더 나쁘고 따라서 더 많은 하드웨어를 구입하게 될 수도 있지만, 압박을 받는 ArrayList의 동작은 클러스터 내의 애플리케이션에서 거의 동시에 어레이를 확장하고 어레이 크기가 클 경우 애플리케이션에서 응답성이 부족하고 운영 중단이 발생할 수 있으며, 이는 압박을 받는 동안에만 발생할 수 있다.미각의 행동
마찬가지로, 기본 처리량 종신형 가비지 수집기에서 앱의 처리량을 향상시킬 수 있지만, 일단 10GB의 힙이 있는 자바 앱을 얻으면 SOA 앱의 시간 초과 및 장애를 유발하는 전체 GC 동안 앱을 25초 동안 잠그고 너무 자주 발생하는 경우 SLA를 해제할 수 있다.CMS 수집기는 더 많은 자원을 사용하고 동일한 원시 처리량을 달성하지 못하더라도 예측 가능하고 대기 시간이 짧기 때문에 훨씬 더 나은 선택이다.
ArrayList는 성능의 모든 의미가 처리량이고 지연 시간을 무시할 수 있는 경우에만 더 나은 선택이다.내 직장 경험상 최악의 지연 시간을 무시할 수 없다.
업데이트(2021년 8월 27일 - 10년 후):이 대답(SO에 대해 역사적으로 가장 많이 인용한 대답)은 잘못되었을 가능성이 매우 높다(아래 논평에 요약된 이유들).ArrayList가 순차 메모리 읽기에 최적화되고 캐시라인 및 TLB 누락 등을 최소화할 것이라는 점을 추가하고자 한다.어레이가 한도를 초과하여 증가할 때 복사 오버헤드는 비교에 의해 중요하지 않을 수 있다(그리고 효율적인 CPU 작동에 의해 수행될 수 있다).이 대답은 또한 하드웨어 추세를 고려할 때 시간이 지날수록 점점 더 나빠지고 있을 것이다.LinkedList가 타당할 수 있는 유일한 상황은 수천 개의 목록 중 어떤 것이든 GB 크기로 커질 수 있지만, 목록을 할당하는 시간에 적절한 추측을 할 수 없고 모두 GB 크기로 설정하는 경우 힙을 폭파하는 것이다.그리고 만약 당신이 그런 문제를 발견한다면, 그것은 정말로 당신의 해결책이 무엇이든 재엔지니어링을 필요로 한다. (그리고 나는 나 자신이 낡은 코드 더미를 유지하고 있기 때문에 낡은 코드 재엔지니어링을 가볍게 제안하고 싶지는 않지만, 그것은 원래의 설계가 단순히 활주로를 다 써버려서 버려야 하는 아주 좋은 사례가 될 것이다.)그래도 네가 읽을 수 있도록 내 수십 년 된 형편없는 의견은 그대로 두고 가겠다.간단하고 논리적이고 꽤 틀렸다.
그래, 나도 알아, 이건 오래된 질문이야. 하지만 난 내 의견을 말할게.
LinkedList는 거의 항상 잘못된 선택이다. 성능 측면에서.LinkedList가 호출되는 일부 매우 구체적인 알고리즘이 있지만, 이러한 알고리즘은 매우 매우 드물며, 일반적으로 알고리즘은 ListIterator를 사용하여 해당 알고리즘을 탐색한 후 목록의 중간에 요소를 비교적 빨리 삽입하고 삭제하는 LinkedList의 능력에 따라 결정된다.
LinkedList가 ArrayList를 능가하는 한 가지 일반적인 사용 사례, 즉 큐의 사용 사례가 있다.단, LinkedList 대신 ArrayBlockingQueue(대기열 크기 상한을 미리 결정할 수 있고 모든 메모리를 미리 할당할 수 있는 경우) 또는 이 CircularArrayList 구현을 사용하는 것도 고려해 보십시오.(응, 2001년부터니까 제네레이션해야 할 텐데, 최근 JVM에서 기사에 인용된 것과 비슷한 성능비율을 얻었어)
링크드리스트의 저자 조슈아 블로흐:
실제로 LinkedList를 사용하는 사람?나는 그것을 썼고, 절대로 사용하지 않는다.
링크: https://twitter.com/joshbloch/status/583813919019573248
다른 답보다 유익하지 못한 답변이 아쉽지만, 공개하지 않으면 가장 스스로 해명할 수 있을 것 같았다.
능률적인 질문이다. LinkedList요소를 추가하고 삭제하는 데는 빠르지만 특정 요소에 액세스하는 데는 느리다. ArrayList특정 요소에 빠르게 액세스할 수 있지만 양쪽 끝에 추가하는 속도가 느릴 수 있으며, 특히 중간에 삭제하는 속도가 느릴 수 있다.
Array vs ArrayList vs LinkedList vs Vector는 Linked List와 마찬가지로 보다 심층적으로 진행된다.
정답 또는 정답: 로컬에서 테스트를 실행하고 직접 결정하십시오!
편집/제거가 더 빠름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덧셈과 제거는 더 빠르지만, 얻는 것은 더 느리다.요컨대LinkedList다음과 같은 경우에 선호되어야 한다.
- 요소의 무작위 액세스 수가 많지 않음
- 많은 수의 추가/제거 작업이 있다.
==== 배열 목록 ===
- add(E e)
- ArrayList의 끝에 추가
- 메모리 크기 조정 비용 필요
- O(n) 최악, O(1) 상각
- add(인덱스, E 요소)
- 특정 인덱스 위치에 추가
- 이동 및 메모리 크기 조정 비용 필요
- O(n)
- 제거(인덱스 입력)
- 지정된 요소를 제거하다
- 이동 및 메모리 크기 조정 비용 필요
- O(n)
- 제거(객체 o)
- 이 목록에서 지정된 요소의 첫 번째 항목을 제거하십시오.
- 먼저 요소를 검색한 다음, 이동 및 가능한 메모리 크기 조정 비용 필요
- O(n)
=== LinkedList ====
add(E e)
- 명단의 끝에 추가하다.
- O(1)
add(인덱스, E 요소)
- 지정된 위치에 삽입하다
- 우선 그 자리를 찾을 필요가 있다.
- O(n)
- 제거하다
- 목록의 첫 번째 요소를 제거하다.
- O(1)
- 제거(인덱스 입력)
- 지정된 색인으로 요소 제거
- 먼저 원소를 찾아야 한다.
- O(n)
- 제거(객체 o)
- 지정된 원소의 첫 발생을 제거하다.
- 먼저 원소를 찾아야 한다.
- O(n)
여기 programcreek.com의 수치가 있다(add그리고remove첫 번째 유형: 즉, 목록 끝에 요소를 추가하고 목록의 지정된 위치에서 요소를 제거하십시오.
TL;DR은 현대적인 컴퓨터 구조로 인해,ArrayList거의 더 일 것이며, 거의 가 한국 사의 가 로 로 로 로 로 로 로 로 로 로 로 로.LinkedList매우 독특하고 극단적인 경우를 제외하고 피해야 한다.
이론적으로, LinkedList는 다음에 대한 O(1)를 가지고 있다.add(E element)
또한 목록 중간에 요소를 추가하는 것은 매우 효율적이어야 한다.
LinkedList는 캐시 적대적 데이터 구조인 만큼 실행 방식은 매우 다르다.성능 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++와 자바 결과는 매우 유사했다.소스 코드
순차적으로 대량 메모리를 복사하는 것은 현대 CPU에 의해 최적화된 작업이다 - 이론의 변화 그리고 실제로 다시,ArrayList/Vector훨씬 능률적인
크레딧:여기에 게시된 모든 벤치마크는 Kjell Hedström에 의해 만들어졌다.더 많은 데이터를 그의 블로그에서 찾을 수 있다.
ArrayList임의로 액세스할 수 있는 동안LinkedList요소를 확장하고 제거하는 것은 정말 싸다.대부분의 경우,ArrayList괜찮아
큰 리스트를 만들고 병목현상을 측정하지 않았다면 아마 그 차이점에 대해 걱정할 필요가 없을 것이다.
코드에 다음이 있는 경우add(0)그리고remove(0), 사용 aLinkedList그리고 더 예쁘다.addFirst()그리고removeFirst()방법들그렇지 않은 경우 사용ArrayList.
그리고 물론, 구아바의 불변명단은 너의 가장 친한 친구야.
아래 매개 변수에서 LinkedList와 ArrayList w.r.t.를 비교해 봅시다.
1.실행
ArrayList는 목록 인터페이스의 크기를 조정할 수 있는 어레이 구현 입니다.
LinkedList는 목록 인터페이스의 이중 연계 목록 구현이다.
2. 퍼포먼스
가져오기(인덱스 입력) 또는 검색 작업
ArrayList get(인덱스) 작업은 일정한 시간(예: O(1) 동안 실행됨
LinkedList get(인덱스) 작업 실행 시간은 O(n) 입니다.
ArrayList가 LinkedList보다 빠른 이유는 ArrayList가 내부적으로 어레이 데이터 구조를 사용하기 때문에 해당 요소에 인덱스 기반 시스템을 사용하기 때문이다.
LinkedList는 지정된 요소 인덱스에서 노드를 검색하기 위해 처음부터 끝까지(둘 중 더 가까운 것) 반복하므로 해당 요소에 대한 인덱스 기반 액세스를 제공하지 않는다.
삽입() 또는 추가(개체) 작업
LinkedList의 삽입은 ArrayList에 비해 일반적으로 빠르다.LinkedList에서 추가 또는 삽입은 O(1) 작업 입니다.
ArrayList에서 어레이가 전체인 경우(최악의 경우) 어레이의 크기를 조정하고 요소를 새 어레이에 복사하는 데 추가 비용이 발생하여 어레이 목록 O(n)에서 추가 작업을 실행하거나 그렇지 않으면 O(1)가 된다.
작전을 해제하다.
LinkedList에서 제거 작업은 일반적으로 ArrayList, 즉 O(n)와 동일하다.
LinkedList에는 두 가지 과부하 제거 방법이 있다.하나는 목록 헤드를 제거하고 일정한 시간 O(1)으로 실행되는 매개 변수 없이 remove()이다.LinkedList의 다른 과부하 제거 방법은 매개 변수로 전달된 개체 또는 int를 제거하는 제거(int) 또는 제거(Object)이다.이 메서드는 객체를 찾을 때까지 LinkedList를 가로지르고 원래 목록에서 연결을 해제한다.따라서 이 방법 런타임은 O(n)이다.
ArrayList 제거(int) 방법에는 이전 어레이에서 업데이트된 새 어레이로 요소를 복사하는 작업이 포함되지만, 따라서 실행 시간은 O(n)이다.
3. 리버스 이터레이터
LinkedList는 downloadIterator()를 사용하여 역방향으로 반복할 수 있음
ArrayList 에 downloadIterator()가 없으므로, 우리는 ArrayList를 역방향으로 반복하기 위해 우리만의 코드를 써야 한다.
4. 초기 용량
생성자가 오버로드되지 않은 경우 ArrayList는 초기 용량 10의 빈 목록을 생성하는 동안
LinkedList는 초기 용량 없이 빈 목록만 구성한다.
5. 메모리 오버헤드
LinkedList의 노드는 다음 노드와 이전 노드의 주소를 유지해야 하므로 LinkedList의 메모리 오버헤드는 ArrayList에 비해 더 크다.동안
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 |
|--------------------------------------|
이게 오래된 게시물인 건 알지만 아무도 그런 말을 안 하다니 믿을 수가 없어.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)
CopyOnWrite-ArrayList
get O(1)
add O(n)
contains O(n)
next O(1)
remove O(n)
iterator.remove O(n)
이것들을 바탕으로 너는 무엇을 선택할지 결정해야 한다.:)
위의 다른 좋은 주장들과 더불어, 당신은 주목해야 한다.ArrayList를 사용하다RandomAccess인터페이스(한 동안)LinkedList를 사용하다Queue.
따라서, 그들은 효율성과 행동의 차이와 함께 약간 다른 문제를 다룬다. (그들의 방법 목록 참조)
그것은 당신이 리스트에서 어떤 작전을 더 많이 수행하느냐에 달려있다.
ArrayList인덱싱된 값에 액세스하는 속도가 더 빠름.물체를 삽입하거나 삭제할 때는 훨씬 더 나쁘다.
자세한 내용은 어레이와 링크된 목록의 차이점에 대한 기사를 참조하십시오.
배열 목록은 본질적으로 항목 등을 추가하는 방법이 있는 배열이다(대신 일반 목록을 사용해야 한다).인덱서를 통해 액세스할 수 있는 항목의 모음입니다(예: [0]).그것은 한 항목에서 다음 항목으로의 진행을 의미한다.
링크된 목록은 한 항목에서 다음 항목으로 진행(항목 a -> 항목 b)을 지정한다.배열 목록에서도 같은 효과를 얻을 수 있지만, 링크된 목록에는 이전의 항목과 어떤 항목이 따라야 하는지 확실히 나와 있다.
Java Tutorials - List Implements를 참조하십시오.
링크된 목록의 중요한 특징(다른 답변에서 읽지 않음)은 두 목록의 결합이다.어레이의 경우 이 값은 O(n)이고(일부 재할당의 오버헤드)이며 링크된 목록은 O(1) 또는 O(2) ;-일 뿐이다.
중요:Java의 경우 해당 항목LinkedList이건 사실이 아니야!자세한 내용은 Java에서 링크된 목록에 대한 빠른 연결 방법이 있는가?를 참조하십시오.
ArrayList와 LinkedList는 그들만의 장단점이 있다.
ArrayList는 다음 노드를 향해 포인터를 사용하는 LinkedList와 비교하여 연속 메모리 주소를 사용한다.따라서 ArrayList에서 요소를 조회하려는 경우 LinkedList를 사용하여 n번 반복하는 것보다 더 빠름
반면, ArrayList는 삽입 또는 삭제에 시프트 작업을 사용하는 것을 의미하지만, 포인터만 변경하면 되기 때문에 LinkedList의 삽입 및 삭제는 훨씬 쉽다.
앱에서 자주 검색하는 작업이 있는 경우 ArrayList를 사용하십시오.자주 삽입 및 삭제하는 경우 LinkedList를 사용하십시오.
1) 기반 데이터 구조
ArrayList와 LinkedList의 첫 번째 차이점은 ArrayList가 어레이로 백업되고 LinkedList가 LinkedList로 백업된다는 점이다.이는 실적의 추가적 차이로 이어질 것이다.
2) LinkedList에서 Deque 구현
ArrayList와 LinkedList의 또 다른 차이점은 List 인터페이스와 별도로 LinkedList는 또한 Deque 인터페이스를 구현한다는 것이다. 이 인터페이스는 Decque 인터페이스를 구현하며, Deck 인터페이스를 위한 첫 번째 아웃 오퍼레이션을 제공한다.add()그리고poll()기타 몇 가지 Deque 기능.3) ArrayList의 요소 추가 ArrayList의 요소 추가는 Array의 크기 재조정을 트리거하지 않을 경우 O(1) 연산이며, 이 경우 O(log(n)가 되고, 반대로 LinkedList의 요소 추가는 항법(Navigation)이 필요 없기 때문에 O(1) 연산이다.
4) 위치에서 요소 제거
예를 들어, 호출을 통해 특정 인덱스에서 요소를 제거하려면 다음과 같이 하십시오.remove(index)반면 LinkedList는 근접성에 기반하여 어느 방향에서든 이동할 수 있으므로 O(n/2)로 이동해야 한다 ArrayList는 O(n)에 근접하게작업을 수행하는 복사.
5) ArrayList 또는 LinkedList를 통해 반복
반복은 LinkedList와 ArrayList 모두에 대한 O(n) 작업이며 여기서 n은 요소의 수입니다.
6) 위치에서 요소 검색
그get(index)ArayList에서 O(1)이고 운영은, O(n/2)는 LinkedList에서, 해당 항목까지 이동해야 하기 때문에 해당 O(n/2)는 LinkedList에서 입니다 해당.그러나, Big O 표기법에서 O(n/2)는 상수를 무시하기 때문에 O(n)에 불과하다.
7) 기억
LinkedList는 데이터 저장에 정적 중첩된 클래스인 Entry라는 래퍼 객체를 사용하며, ArrayList는 데이터를 어레이에 저장하기만 한다.
따라서 한 어레이에서 다른 어레이로 컨텐츠를 복사할 때 어레이가 크기 조정 작업을 수행하는 경우를 제외하고, ArrayList의 경우 메모리 요구 사항이 LinkedList보다 적은 것으로 보인다.
어레이가 충분히 크면 해당 시점에 많은 메모리를 소모하고 가비지 수집을 트리거하여 응답 시간을 느리게 할 수 있다.
ArrayList와 LinkedList 간의 위의 모든 차이점 중에서 ArrayList가 자주 하는 경우를 제외하고 거의 모든 경우에 LinkedList보다 더 나은 선택인 것 같다.add()보다 더 많은 운영remove()또는get().
특히 링크된 목록은 내부적으로 해당 위치의 참조를 유지하고 O(1) 시간 내에 액세스할 수 있기 때문에 시작 또는 끝에서 요소를 추가하거나 제거하는 경우에는 ArrayList보다 링크된 목록을 수정하는 것이 더 쉽다.
즉, 요소를 추가하고자 하는 위치에 도달하기 위해 링크된 목록을 거치지 않아도 되며, 그 경우 덧셈은 O(n) 연산이 된다.예를 들어 링크된 목록의 중간에 요소를 삽입하거나 삭제하는 경우.
내 생각에는 Java에서 대부분의 실용적인 목적을 위해 LinkedList를 ArrayList를 사용하는 것 같아.
응답을 읽었지만 어레이 목록을 통해 항상 LinkedList를 사용하여 의견을 듣는 시나리오가 하나 있다.
DB에서 얻은 데이터 목록을 반환하는 방법이 있을 때마다 항상 LinkedList를 사용한다.
나의 근거는 내가 정확히 얼마나 많은 결과를 얻고 있는지 알 수 없기 때문에 (용량과 실제 요소 수의 차이를 가진 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는 모두 List 인터페이스의 구현이다.
- 두 가지 요소 모두 ArrayList 및 LinkedList 요소를 표시하는 동안 결과 집합이 요소가 목록에 삽입된 순서와 동일한 순서를 갖는 요소 삽입 순서를 유지한다.
- 이 두 클래스는 모두 비동기화되며 컬렉션을 사용하여 명시적으로 동기화할 수 있다.동기화된 목록 메서드.
- 그
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의 작업 get(i)이 LinkedList보다 빠름:
배열 목록:목록 인터페이스의 크기 조정 가능한 어레이 구현
LinkedList: List 및 Deque 인터페이스의 이중 연계 목록 구현
목록으로 인덱싱되는 작업은 지정된 인덱스에 더 가까운 처음부터 끝까지 목록을 가로지른다.
여기서 본 시험 중 하나는 시험을 한 번만 보는 것이다.하지만 내가 주목한 것은 당신이 이 테스트를 여러 번 실행해야 한다는 것이고 결국 그들의 시대가 수렴될 것이라는 것이다.기본적으로 JVM은 워밍업이 필요하다.나의 특별한 사용 사례를 위해 나는 약 500개의 항목으로 증가하는 목록에 항목을 추가/제거해야 했다.내 시험에서LinkedList와 함께 더 빨리 나왔다.LinkedList약 50,000 NS의 속도로ArrayList90,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;
}
둘 다remove()그리고insert()ArrayLists와 LinkedLists에 대해 모두 O(n)의 런타임 효율성을 가진다.그러나 선형 처리 시간의 이면에 있는 이유는 다음과 같은 두 가지 매우 다른 이유로부터 온다.
ArrayList에서는 O(1)의 요소에 도달하지만, 실제로 어떤 것을 제거하거나 삽입하면 다음 모든 요소를 변경해야 하기 때문에 O(n)가 된다.
LinkedList에서 원하는 요소에 도달하려면 O(n)가 필요한데, 이는 우리가 원하는 지수에 도달할 때까지 맨 처음부터 시작해야 하기 때문이다.실제로 제거하거나 삽입하는 것은 일정하다. 왜냐하면 우리는 단지 하나의 참조만 변경하면 되기 때문이다.remove()및 다음에 대한 참조 2개insert().
둘 중 어느 것이 삽입과 제거에 더 빠른가 하는 것은 어디에서 발생하느냐에 따라 다르다.만약 우리가 시작에 가까워진다면 링크드리스트는 비교적 적은 요소들을 거쳐야 하기 때문에 더 빨라질 것이다.만약 우리가 끝에 가까워진다면, 어레이리스트는 더 빨라질 것이다. 왜냐하면 우리는 일정한 시간에 그곳에 도착하고 그것을 따르는 몇 안 되는 요소만 바꾸면 되기 때문이다.정확히 중간에서 실행하면 n개의 요소를 통과하는 것이 n개의 값을 이동하는 것보다 빠르기 때문에 LinkedList가 더 빠를 것이다.
보너스: ArrayList에 대해 이 두 가지 방법을 O(1)로 만드는 방법은 없지만, LinkedLists에는 실제로 이 방법을 사용하는 방법이 있다.우리가 가는 길에 요소들을 제거하고 삽입하는 전체 목록을 살펴보기를 원한다고 하자.일반적으로 LinkedList를 사용하여 각 요소에 대해 처음부터 시작하며, Iterator로 작업 중인 현재 요소를 "저장"할 수도 있다.Iterator의 도움으로, 우리는 O(1) 효율을 얻는다.remove()그리고insert()LinkedList에서 작업할 때.LinkedList가 ArrayList보다 항상 더 나은 위치에 있다는 것을 잘 알고 있는 유일한 성능 이점 제공.
ArrayList는 ObstractList를 확장하고 List Interface를 구현한다.ArrayList는 동적 배열이다.
기본적으로 어레이의 단점을 극복하기 위해 만들어졌다고 할 수 있다.
LinkedList 클래스는 ObstractSequentialList를 확장하고 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)
참조URL: https://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist-in-java
'Programing' 카테고리의 다른 글
| 기본적으로 모든 Java 애플리케이션이 사용할 수 있는 Java Keystore로 자체 서명된 인증서를 가져오는 방법 (0) | 2022.05.06 |
|---|---|
| vuex 상태 + persistedState 플러그인에 토큰을 저장하는 것이 안전한가? (0) | 2022.05.06 |
| ZoneOffset의 차이점은 무엇인가?UTC 및 ZoneId.of("UTC")? (0) | 2022.05.06 |
| Vuex 데이터를 사후 대응적으로 만들기 (0) | 2022.05.06 |
| 모키토 던져진 예외를 어떻게 조롱하고 주장할 것인가? (0) | 2022.05.06 |