주의!) 테스트를 하면서 성능 비교를 적은 글이라 정확하지 않을 수 있습니다. 혹시나 잘못된 부분이 있으면 지적 부탁드릴게요🙏
시작하기 전에
ArrayList와 LinkedList는 쓰이는 곳이 제각각 다르다는 것을 인지하고 있다.
LinkedList를 사용할 경우는 앞/뒤 요소를 추가하거나 빼는 경우가 빈번할 때(Queue, Stack과 관련된 자료구조를 사용하는 경우) 많이 사용을 하고 그렇지 않은 경우에는 ArrayList를 사용한다.(HashMap을 사용하는 경우도 많지만 이번에는 제외하고 생각해보겠다!) 그렇다면 성능에 대해서는 제대로 알고 있을까? 제대로 체크해보고 싶은 마음에 이 주제로 선정했다😃
참고사항
- 자바에서 LinkedList는
DoubleLinkedList구현이 되어있다. 그렇기 때문에 앞/뒤에 요소를 추가하고 삭제하는 성능은 동일하기 때문에 마지막 요소를 기준으로 비교해 보려고 한다. - 자바에서 ArrayList는 Array를 기반으로 구현이 되어있다. 가변적인 이유는 일정 공간이 다 차게되면 내부적으로 공간을 확장시킨 배열을 생성하고 기존 Array를 전부 copy하는데 자세한 내용은 ArrayList는 어떻게 가변적일까?를 참고 하면 좋을 것 같다.
- 테스트 시 사용했던 코드는 여기를 참고 하면 좋을 것 같다.
ArrayList와 LinkedList의 시간복잡도
| 상황 | ArrayList | LinkedList | 추천 |
|---|---|---|---|
| 마지막에 요소 추가 | 여유 공간이 있을 경우 O(1) / 없을 경우 O(N) | O(1) | ? |
| 주어진 Index에 요소 추가 | O(N) | O(N) | ? |
| 값으로 검색 | O(N) | O(N) | ArrayList |
| Index로 검색 | O(1) | O(N) | ArrayList |
| Index로 요소 제거 | O(N) | O(N) | ? |
| 값으로 요소 제거 | O(N) | O(N) | ? |
- 우선 시간 복잡도에 대해서 먼저 정리해 보았다. 아래에서 하나씩 코드를 통해 비교해보자!
추가
추가하는 경우는 총 2가지가 존재한다.
- 마지막에 요소를 추가
- 주어진 Index에 요소를 추가
마지막에 요소를 추가하는 경우(Code)
| 상황 | ArrayList | LinkedList | 추천 |
|---|---|---|---|
| 마지막에 요소 추가 | 여유 공간이 있을 경우 O(1) / 없을 경우 O(N) | O(1) | ? |
Test를 먼저 ArrayList가 여유 공간이 있는 경우(O(N))를 우선적으로 비교해 보았다.
import java.util.ArrayList;
import java.util.LinkedList;
public class AddLastTest {
public static void main(String[] args) {
AddLastTest test = new AddLastTest();
test.checkAddLast();
}
private void checkAddLast() {
System.out.println("1000인 경우");
compareAddLast(1_000);
System.out.println("-------");
System.out.println("1만인 경우");
compareAddLast(10_000);
System.out.println("-------");
System.out.println("3만인 경우");
compareAddLast(30_000);
System.out.println("-------");
System.out.println("5만인 경우");
compareAddLast(50_000);
System.out.println("-------");
System.out.println("10만인 경우");
compareAddLast(100_000);
System.out.println("-------");
System.out.println("100만인 경우");
compareAddLast(1_000_000);
System.out.println("-------");
System.out.println("1000만인 경우");
compareAddLast(10_000_000);
System.out.println("-------");
}
private void compareAddLast(int size) {
long arrayListTime = addLastByArrayList(size);
long linkedListTime = addLastByLinkedList(size);
System.out.println("ArrayList: " + arrayListTime + "ns");
System.out.println("LinkedList: " + linkedListTime + "ns");
if (arrayListTime < linkedListTime) {
System.out.println("ArrayList가 더 빠릅니다.");
} else if (arrayListTime > linkedListTime) {
System.out.println("LinkedList가 더 빠릅니다.");
} else {
System.out.println("ArrayList와 LinkedList의 수행 시간이 동일합니다.");
}
}
private long addLastByArrayList(int size) {
// 여유 공간이 있는 ArrayList
ArrayList<Integer> arrayList = new ArrayList<>(size + 1);
// 여유 공간이 없는 ArrayList
// ArrayList<Integer> arrayList = new ArrayList<>(size);
for (int i = 1; i <= size; i++) {
arrayList.add(i);
}
long beforeTotalTime = System.nanoTime();
arrayList.add(1);
long afterTotalTime = System.nanoTime();
return afterTotalTime - beforeTotalTime;
}
private long addLastByLinkedList(int size) {
LinkedList<Integer> linkedList = new LinkedList<>();
for (int i = 1; i <= size; i++) {
linkedList.add(i);
}
long beforeTotalTime = System.nanoTime();
linkedList.addLast(1);
long afterTotalTime = System.nanoTime();
return afterTotalTime - beforeTotalTime;
}
}
마지막에 요소를 추가하는 경우(Output)
- 여유 공간이 있는 경우
1000인 경우
ArrayList: 709ns
LinkedList: 2666ns
ArrayList가 더 빠릅니다.
-------
1만인 경우
ArrayList: 625ns
LinkedList: 917ns
ArrayList가 더 빠릅니다.
-------
3만인 경우
ArrayList: 417ns
LinkedList: 833ns
ArrayList가 더 빠릅니다.
-------
5만인 경우
ArrayList: 333ns
LinkedList: 5250ns
ArrayList가 더 빠릅니다.
-------
10만인 경우
ArrayList: 250ns
LinkedList: 5584ns
ArrayList가 더 빠릅니다.
-------
100만인 경우
ArrayList: 125ns
LinkedList: 11708ns
ArrayList가 더 빠릅니다.
-------
1000만인 경우
ArrayList: 208ns
LinkedList: 583ns
ArrayList가 더 빠릅니다.
-------- 여유 공간이 없는 경우
1000인 경우
ArrayList: 8292ns
LinkedList: 2584ns
LinkedList가 더 빠릅니다.
-------
1만인 경우
ArrayList: 14417ns
LinkedList: 667ns
LinkedList가 더 빠릅니다.
-------
3만인 경우
ArrayList: 51125ns
LinkedList: 1375ns
LinkedList가 더 빠릅니다.
-------
5만인 경우
ArrayList: 69084ns
LinkedList: 5583ns
LinkedList가 더 빠릅니다.
-------
10만인 경우
ArrayList: 126750ns
LinkedList: 10250ns
LinkedList가 더 빠릅니다.
-------
100만인 경우
ArrayList: 1342250ns
LinkedList: 19875ns
LinkedList가 더 빠릅니다.
-------
1000만인 경우
ArrayList: 21562333ns
LinkedList: 625ns
LinkedList가 더 빠릅니다.
-------마지막에 요소를 추가하는 경우(Opinion)
결과는 아래와 같다.
- 여유 공간이 없는 경우에 LinkedList가 더 빠르다.
- 여유 공간이 있는 경우에 ArrayList가 더 빠르다.
여유 공간이 있는 경우와 없는 경우에 차이가 존재하는 이유는 ArrayList의 내부 구현 방식 때문인데 ArrayList는 내부적으로 Array로 구현이 되어져 있고 내부에 저장 공간이 가득차게 되면 새로운 공간을 1.5배 확장한 새로운 배열을 생성하고 기존 배열 요소를 복사를 하기 때문에 O(N)이라는 시간 복잡도가 소요된다.
그런데 여유 공간이 있는 경우에 ArrayList가 빠른 이유가 뭘까?
ChatGPT에게 물어봤다🕵️
자바에서 마지막 요소에 추가를 추가할때 ArrayList와 LinkedList 중에 누가 더 빠르고, 빠른 이유를 자세히 설명해줘.
아래는 ChatGPT의 답변 중 일부분을 가져왔다.
-
자바에서 마지막 요소를 추가하는 경우, ArrayList와 LinkedList 중에서
ArrayList가 더 빠릅니다.이는 ArrayList와 LinkedList의 내부 구현 방식 때문입니다. -
ArrayList는 요소들을 메모리에 연속적으로 저장하므로
캐시 지역성이 좋아져 캐시 미스가 적어지는 장점이 있습니다. -
LinkedList는 요소를 메모리에 연속적으로 저장하지 않기 때문에 캐시 지역성이 좋지 않을 수 있고, 새로운 노드를 생성하고 참조를 업데이트하는 작업으로 인해 오버헤드가 높아집니다.
-
마지막 요소를 추가하는 연산은 LinkedList에서도 O(1)의 시간 복잡도를 갖지만, ArrayList에 비해 느릴 수 있습니다.
아..! 예전에 공부했던 Cache Hit, Cache Miss가 떠올랐다. 결국 메모리 상의 데이터를 cache로 가져올 때, 메모리 한 공간을 가져오는 것이 아니라 한 줄을 가져오기 때문에, 메모리에 연속적으로 저장되어 있는 ArrayList가 캐시 적중률이 높다. 그렇기 때문에 더 빠르다고 이해할 수 있었다.
주어진 Index에 요소를 추가하는 경우(Code)
| 상황 | ArrayList | LinkedList | 추천 |
|---|---|---|---|
| 주어진 Index에 요소 추가 | O(N) | O(N) | ? |
import java.util.ArrayList;
import java.util.LinkedList;
public class AddMiddleTest {
public static void main(String[] args) {
AddMiddleTest test = new AddMiddleTest();
test.checkAddMiddle();
}
private void checkAddMiddle() {
System.out.println("1000인 경우");
compareAddMiddle(1_000);
System.out.println("-------");
System.out.println("1만인 경우");
compareAddMiddle(10_000);
System.out.println("-------");
// 이하 생략..!
}
private void compareAddMiddle(int size) {
long arrayListTime = addMiddleByArrayList(size);
long linkedListTime = addMiddleByLinkedList(size);
System.out.println("ArrayList: " + arrayListTime + "ns");
System.out.println("LinkedList: " + linkedListTime + "ns");
if (arrayListTime < linkedListTime) {
System.out.println("ArrayList가 더 빠릅니다.");
} else if (arrayListTime > linkedListTime) {
System.out.println("LinkedList가 더 빠릅니다.");
} else {
System.out.println("ArrayList와 LinkedList의 수행 시간이 동일합니다.");
}
}
private long addMiddleByArrayList(int size) {
// ArrayList<Integer> arrayList = new ArrayList<>(size + 1);
ArrayList<Integer> arrayList = new ArrayList<>(size);
for (int i = 1; i <= size; i++) {
arrayList.add(i);
}
long beforeTotalTime = System.nanoTime();
arrayList.add(arrayList.size() / 2, 1);
long afterTotalTime = System.nanoTime();
return afterTotalTime - beforeTotalTime;
}
private long addMiddleByLinkedList(int size) {
LinkedList<Integer> linkedList = new LinkedList<>();
for (int i = 1; i <= size; i++) {
linkedList.add(i);
}
long beforeTotalTime = System.nanoTime();
linkedList.add(linkedList.size() / 2, 1);
long afterTotalTime = System.nanoTime();
return afterTotalTime - beforeTotalTime;
}
}
주어진 Index에 요소를 추가하는 경우(Outpur)
- 여유 공간이 있는 경우
1000인 경우
ArrayList: 6833ns
LinkedList: 12667ns
ArrayList가 더 빠릅니다.
-------
1만인 경우
ArrayList: 5833ns
LinkedList: 52125ns
ArrayList가 더 빠릅니다.
-------
3만인 경우
ArrayList: 12000ns
LinkedList: 141458ns
ArrayList가 더 빠릅니다.
-------
5만인 경우
ArrayList: 29042ns
LinkedList: 265833ns
ArrayList가 더 빠릅니다.
-------
10만인 경우
ArrayList: 39875ns
LinkedList: 506125ns
ArrayList가 더 빠릅니다.
-------
100만인 경우
ArrayList: 339208ns
LinkedList: 2099042ns
ArrayList가 더 빠릅니다.
-------
500만인 경우
ArrayList: 2922875ns
LinkedList: 12483875ns
ArrayList가 더 빠릅니다.
-------
1000만인 경우
ArrayList: 8668667ns
LinkedList: 22124083ns
ArrayList가 더 빠릅니다.
-------
1500만인 경우
ArrayList: 12854125ns
LinkedList: 30621208ns
ArrayList가 더 빠릅니다.
-------
2000만인 경우
ArrayList: 123266500ns
LinkedList: 46867250ns
LinkedList가 더 빠릅니다.
-------
3000만인 경우
ArrayList: 158794792ns
LinkedList: 59446334ns
LinkedList가 더 빠릅니다.
-------
4000만인 경우
ArrayList: 22075917ns
LinkedList: 89565417ns
ArrayList가 더 빠릅니다.
-------
5000만인 경우
ArrayList: 241122500ns
LinkedList: 102514000ns
LinkedList가 더 빠릅니다.
-------- 여유 공간이 없는 경우
1000인 경우
ArrayList: 12500ns
LinkedList: 18500ns
ArrayList가 더 빠릅니다.
-------
1만인 경우
ArrayList: 23500ns
LinkedList: 75083ns
ArrayList가 더 빠릅니다.
-------
3만인 경우
ArrayList: 53583ns
LinkedList: 213875ns
ArrayList가 더 빠릅니다.
-------
5만인 경우
ArrayList: 97500ns
LinkedList: 396666ns
ArrayList가 더 빠릅니다.
-------
10만인 경우
ArrayList: 183250ns
LinkedList: 561541ns
ArrayList가 더 빠릅니다.
-------
100만인 경우
ArrayList: 1605000ns
LinkedList: 2849625ns
ArrayList가 더 빠릅니다.
-------
500만인 경우
ArrayList: 13679459ns
LinkedList: 11825792ns
LinkedList가 더 빠릅니다.
-------
1000만인 경우
ArrayList: 28220250ns
LinkedList: 21649333ns
LinkedList가 더 빠릅니다.
-------
1500만인 경우
ArrayList: 46936333ns
LinkedList: 33889625ns
LinkedList가 더 빠릅니다.
-------
2000만인 경우
ArrayList: 104978917ns
LinkedList: 41537417ns
LinkedList가 더 빠릅니다.
-------
3000만인 경우
ArrayList: 103493375ns
LinkedList: 74567084ns
LinkedList가 더 빠릅니다.
-------
4000만인 경우
ArrayList: 324854125ns
LinkedList: 100452792ns
LinkedList가 더 빠릅니다.
-------주어진 Index에 요소를 추가하는 경우(Opinion)
테스트 결과가 일반적이지 않아서 판단이 어려웠다🥺
-
여유 공간이 있는 경우에 데이터가 2000만 이상인 경우 부터는 일반적으로 LinkedList가 빨랐다.
-
여유 공간이 없는 경우에 데이터가 500만 이상인 경우 부터 일반적으로 LinkedList가 빨랐다.
한계점
현재 테스트에서는 정확하게 데이터의 삽입을 중간 지점의 Index로 성능을 판단했지만 중간 지점의 위치가 양 끝단에 가까워질 수록 LinkedList의 성능이 더 빠른 양상을 보였다.
LinkedList의 경우에 index의 위치에 따라서 first 부터 순회할지, last 부터 순회할지를 결정하고, 새로 노드를 생성해서 연결시킨다. 그렇기 때문에 linkedList에서 정 가운데 index는 가장 접근하는 시간이 오래 걸리는 지점이다.
주어진 Index에 요소를 추가하는 경우에는 ArrayList와 LinkedList 둘 다 시간 복잡도가 O(N)이다.
ArrayList는 해당 Index의 위치를 찾을 때 O(1)이 걸리지만, 요소를 추가할 경우 copy가 발생한다 따라서 O(N)의 시간 복잡도를 가진다.
아래는 ArrayList에서 중간 삽입 시에 호출 되는 add method이다.
검색
검색의 경우는 총 2가지가 존재한다.
- 값으로 검색
- Index로 검색
값으로 검색(Code)
| 상황 | ArrayList | LinkedList | 추천 |
|---|---|---|---|
| 값으로 검색 | O(N) | O(N) | ArrayList |
값으로 검색하는 경우는 어떨까?
아래 TestCode를 보자.
import java.util.ArrayList;
import java.util.LinkedList;
public class SearchByValue {
public static void main(String[] args) {
SearchByValue test = new SearchByValue();
test.checkSearchByValue();
}
private void checkSearchByValue() {
System.out.println("100만인 경우");
compareSearchByValue(1_000_000);
System.out.println("-------");
System.out.println("500만인 경우");
compareSearchByValue(5_000_000);
System.out.println("-------");
System.out.println("1000만인 경우");
compareSearchByValue(10_000_000);
System.out.println("-------");
}
private void compareSearchByValue(int size) {
long arrayListTime = searchByValueByArrayList(size, size -1);
long linkedListTime = searchByValueByLinkedList(size, size -1);
System.out.println("ArrayList: " + arrayListTime + "ns");
System.out.println("LinkedList: " + linkedListTime + "ns");
if (arrayListTime < linkedListTime) {
System.out.println("ArrayList가 더 빠릅니다.");
} else if (arrayListTime > linkedListTime) {
System.out.println("LinkedList가 더 빠릅니다.");
} else {
System.out.println("ArrayList와 LinkedList의 수행 시간이 동일합니다.");
}
}
private long searchByValueByArrayList(int size, int value) {
ArrayList<Integer> arrayList = new ArrayList<>(size);
for (int i = 1; i <= size; i++) {
arrayList.add(i);
}
long beforeTotalTime = System.nanoTime();
arrayList.contains(value);
long afterTotalTime = System.nanoTime();
return afterTotalTime - beforeTotalTime;
}
private long searchByValueByLinkedList(int size, int value) {
LinkedList<Integer> linkedList = new LinkedList<>();
for (int i = 1; i <= size; i++) {
linkedList.add(i);
}
long beforeTotalTime = System.nanoTime();
linkedList.contains(value);
long afterTotalTime = System.nanoTime();
return afterTotalTime - beforeTotalTime;
}
}
값으로 검색(Output)
100만인 경우
ArrayList: 5463125ns
LinkedList: 6629500ns
ArrayList가 더 빠릅니다.
-------
500만인 경우
ArrayList: 6406958ns
LinkedList: 32658417ns
ArrayList가 더 빠릅니다.
-------
1000만인 경우
ArrayList: 18912166ns
LinkedList: 87123459ns
ArrayList가 더 빠릅니다.
-------
값으로 검색(Opinion)
- 값으로 검색했을 때, ArrayList가 빨랐다. 동일한 O(N)의 시간 복잡도를 가지지만 위와 동일하게 cache 적중률이 높기 때문에 더 빠르다고 예상했다.🕵️
Index로 검색(Code)
| 상황 | ArrayList | LinkedList | 추천 |
|---|---|---|---|
| Index로 검색 | O(1) | O(N) | ArrayList |
Index로 검색했을 경우에는 어떨까?
import java.util.ArrayList;
import java.util.LinkedList;
public class SearchByIndex {
public static void main(String[] args) {
SearchByIndex test = new SearchByIndex();
test.checkSearchByIndex();
}
private void checkSearchByIndex() {
System.out.println("100만인 경우");
compareSearchByValue(1_000_000);
System.out.println("-------");
System.out.println("500만인 경우");
compareSearchByValue(5_000_000);
System.out.println("-------");
System.out.println("1000만인 경우");
compareSearchByValue(10_000_000);
System.out.println("-------");
}
private void compareSearchByValue(int size) {
long arrayListTime = searchByIndexByArrayList(size, size -1);
long linkedListTime = searchByIndexByLinkedList(size, size -1);
System.out.println("ArrayList: " + arrayListTime + "ns");
System.out.println("LinkedList: " + linkedListTime + "ns");
if (arrayListTime < linkedListTime) {
System.out.println("ArrayList가 더 빠릅니다.");
} else if (arrayListTime > linkedListTime) {
System.out.println("LinkedList가 더 빠릅니다.");
} else {
System.out.println("ArrayList와 LinkedList의 수행 시간이 동일합니다.");
}
}
private long searchByIndexByArrayList(int size, int index) {
ArrayList<Integer> arrayList = new ArrayList<>(size);
for (int i = 1; i <= size; i++) {
arrayList.add(i);
}
long beforeTotalTime = System.nanoTime();
arrayList.get(index);
long afterTotalTime = System.nanoTime();
return afterTotalTime - beforeTotalTime;
}
private long searchByIndexByLinkedList(int size, int index) {
LinkedList<Integer> linkedList = new LinkedList<>();
for (int i = 1; i <= size; i++) {
linkedList.add(i);
}
long beforeTotalTime = System.nanoTime();
linkedList.get(index);
long afterTotalTime = System.nanoTime();
return afterTotalTime - beforeTotalTime;
}
}
Index로 검색(Output)
100만인 경우
ArrayList: 18500ns
LinkedList: 21792ns
ArrayList가 더 빠릅니다.
-------
500만인 경우
ArrayList: 32334ns
LinkedList: 40583ns
ArrayList가 더 빠릅니다.
-------
1000만인 경우
ArrayList: 7000ns
LinkedList: 19959ns
ArrayList가 더 빠릅니다.
-------- Index로 검색 시 ArrayList가
확실하게빠르다.
ArrayList에서는 get method를 통해 value에 바로 접근하여 가져오기 때문이다. O(1) 시간 복잡도를 가진다.
반면에 LinkedList는 해당 index값을 찾기 위해 가리키는 참조값을 통해 이동하며 index를 찾는다. 그렇기 때문에 시간 복잡도는 O(N) 이다.
삭제
Index로 요소를 제거하는 경우(Code)
| 상황 | ArrayList | LinkedList | 추천 |
|---|---|---|---|
| Index로 요소 제거 | O(N) | O(N) | ? |
package linked_list_vs_array_list;
import java.util.ArrayList;
import java.util.LinkedList;
public class RemoveByIndexTest {
public static void main(String[] args) {
RemoveByIndexTest test = new RemoveByIndexTest();
test.checkRemoveByIndex();
}
private void checkRemoveByIndex() {
System.out.println("1000인 경우");
compareRemoveByIndex(1_000);
System.out.println("-------");
System.out.println("1만인 경우");
compareRemoveByIndex(10_000);
System.out.println("-------");
System.out.println("3만인 경우");
compareRemoveByIndex(30_000);
System.out.println("-------");
System.out.println("5만인 경우");
compareRemoveByIndex(50_000);
System.out.println("-------");
System.out.println("10만인 경우");
compareRemoveByIndex(100_000);
System.out.println("-------");
System.out.println("100만인 경우");
compareRemoveByIndex(1_000_000);
System.out.println("-------");
System.out.println("500만인 경우");
compareRemoveByIndex(5_000_000);
System.out.println("-------");
System.out.println("1000만인 경우");
compareRemoveByIndex(10_000_000);
System.out.println("-------");
System.out.println("1500만인 경우");
compareRemoveByIndex(15_000_000);
System.out.println("-------");
System.out.println("2000만인 경우");
compareRemoveByIndex(20_000_000);
System.out.println("-------");
System.out.println("3000만인 경우");
compareRemoveByIndex(30_000_000);
System.out.println("-------");
System.out.println("4000만인 경우");
compareRemoveByIndex(40_000_000);
System.out.println("-------");
System.out.println("5000만인 경우");
compareRemoveByIndex(50_000_000);
System.out.println("-------");
}
private void compareRemoveByIndex(int size) {
long arrayListTime = removeByIndexByArrayList(size);
long linkedListTime = removeByIndexByLinkedList(size);
System.out.println("ArrayList: " + arrayListTime + "ns");
System.out.println("LinkedList: " + linkedListTime + "ns");
if (arrayListTime < linkedListTime) {
System.out.println("ArrayList가 더 빠릅니다.");
} else if (arrayListTime > linkedListTime) {
System.out.println("LinkedList가 더 빠릅니다.");
} else {
System.out.println("ArrayList와 LinkedList의 수행 시간이 동일합니다.");
}
}
private long removeByIndexByArrayList(int size) {
ArrayList<Integer> arrayList = new ArrayList<>(size);
for (int i = 1; i <= size; i++) {
arrayList.add(i);
}
long beforeTotalTime = System.nanoTime();
arrayList.remove(arrayList.size() / 2);
long afterTotalTime = System.nanoTime();
return afterTotalTime - beforeTotalTime;
}
private long removeByIndexByLinkedList(int size) {
LinkedList<Integer> linkedList = new LinkedList<>();
for (int i = 1; i <= size; i++) {
linkedList.add(i);
}
long beforeTotalTime = System.nanoTime();
linkedList.remove(linkedList.size() / 2);
long afterTotalTime = System.nanoTime();
return afterTotalTime - beforeTotalTime;
}
}
Index로 요소를 제거하는 경우(Output)
1000인 경우
ArrayList: 10958ns
LinkedList: 20334ns
ArrayList가 더 빠릅니다.
-------
1만인 경우
ArrayList: 9583ns
LinkedList: 75042ns
ArrayList가 더 빠릅니다.
-------
3만인 경우
ArrayList: 16250ns
LinkedList: 215000ns
ArrayList가 더 빠릅니다.
-------
5만인 경우
ArrayList: 39083ns
LinkedList: 396208ns
ArrayList가 더 빠릅니다.
-------
10만인 경우
ArrayList: 54000ns
LinkedList: 653042ns
ArrayList가 더 빠릅니다.
-------
100만인 경우
ArrayList: 518333ns
LinkedList: 2707125ns
ArrayList가 더 빠릅니다.
-------
500만인 경우
ArrayList: 4326208ns
LinkedList: 9208208ns
ArrayList가 더 빠릅니다.
-------
1000만인 경우
ArrayList: 8071834ns
LinkedList: 21287459ns
ArrayList가 더 빠릅니다.
-------
1500만인 경우
ArrayList: 11606917ns
LinkedList: 30358375ns
ArrayList가 더 빠릅니다.
-------
2000만인 경우
ArrayList: 122463250ns
LinkedList: 69787042ns
LinkedList가 더 빠릅니다.
-------
3000만인 경우
ArrayList: 172992541ns
LinkedList: 66143750ns
LinkedList가 더 빠릅니다.
-------
4000만인 경우
ArrayList: 21924208ns
LinkedList: 104820583ns
ArrayList가 더 빠릅니다.
-------
5000만인 경우
ArrayList: 251651667ns
LinkedList: 124550208ns
LinkedList가 더 빠릅니다.
-------Index로 요소를 제거하는 경우(Opinion)
-
데이터가 2000만개 이상부터 중간 지점을 제거할 때, 일반적으로 LinkedList가 빠르다.
-
데이터가 2000만개 미만에서 중간 지점을 제거할 때, 일반적으로 ArrayList가 더 빠르다.
이러한 차이가 나는 이유는 아래와 같다.
- ArrayList의 Index로 조회 후(O(1)) -> 제거(O(N)) 시간 복잡도 걸린다.
- LinkedList는 Index로 조회 후(O(N)) -> 제거(O(N)) 시간 복잡도가 걸린다.
값으로 요소를 제거하는 경우(Code)
| 상황 | ArrayList | LinkedList | 추천 |
|---|---|---|---|
| 값으로 요소 제거 | O(N) | O(N) | ? |
import java.util.ArrayList;
import java.util.LinkedList;
public class RemoveByValueTest {
public static void main(String[] args) {
RemoveByValueTest test = new RemoveByValueTest();
test.checkRemoveByRemove();
}
private void checkRemoveByRemove() {
System.out.println("1000인 경우");
compareRemoveByRemove(1_000);
System.out.println("-------");
System.out.println("1만인 경우");
compareRemoveByRemove(10_000);
System.out.println("-------");
System.out.println("3만인 경우");
compareRemoveByRemove(30_000);
System.out.println("-------");
System.out.println("5만인 경우");
compareRemoveByRemove(50_000);
System.out.println("-------");
System.out.println("10만인 경우");
compareRemoveByRemove(100_000);
System.out.println("-------");
System.out.println("100만인 경우");
compareRemoveByRemove(1_000_000);
System.out.println("-------");
System.out.println("500만인 경우");
compareRemoveByRemove(5_000_000);
System.out.println("-------");
System.out.println("1000만인 경우");
compareRemoveByRemove(10_000_000);
System.out.println("-------");
System.out.println("1500만인 경우");
compareRemoveByRemove(15_000_000);
System.out.println("-------");
System.out.println("2000만인 경우");
compareRemoveByRemove(20_000_000);
System.out.println("-------");
System.out.println("3000만인 경우");
compareRemoveByRemove(30_000_000);
System.out.println("-------");
System.out.println("4000만인 경우");
compareRemoveByRemove(40_000_000);
System.out.println("-------");
System.out.println("5000만인 경우");
compareRemoveByRemove(50_000_000);
System.out.println("-------");
}
private void compareRemoveByRemove(int size) {
long arrayListTime = removeByValueByArrayList(size);
long linkedListTime = removeByValueByLinkedList(size);
System.out.println("ArrayList: " + arrayListTime + "ns");
System.out.println("LinkedList: " + linkedListTime + "ns");
if (arrayListTime < linkedListTime) {
System.out.println("ArrayList가 더 빠릅니다.");
} else if (arrayListTime > linkedListTime) {
System.out.println("LinkedList가 더 빠릅니다.");
} else {
System.out.println("ArrayList와 LinkedList의 수행 시간이 동일합니다.");
}
}
private long removeByValueByArrayList(int size) {
ArrayList<Integer> arrayList = new ArrayList<>(size);
for (int i = 1; i <= size; i++) {
arrayList.add(i);
}
long beforeTotalTime = System.nanoTime();
arrayList.remove(Integer.valueOf(arrayList.size() / 2));
long afterTotalTime = System.nanoTime();
return afterTotalTime - beforeTotalTime;
}
private long removeByValueByLinkedList(int size) {
LinkedList<Integer> linkedList = new LinkedList<>();
for (int i = 1; i <= size; i++) {
linkedList.add(i);
}
long beforeTotalTime = System.nanoTime();
linkedList.remove(Integer.valueOf(linkedList.size() / 2));
long afterTotalTime = System.nanoTime();
return afterTotalTime - beforeTotalTime;
}
}
값으로 요소를 제거하는 경우(Output)
1000인 경우
ArrayList: 59000ns
LinkedList: 24541ns
LinkedList가 더 빠릅니다.
-------
1만인 경우
ArrayList: 174792ns
LinkedList: 169084ns
LinkedList가 더 빠릅니다.
-------
3만인 경우
ArrayList: 487416ns
LinkedList: 478166ns
LinkedList가 더 빠릅니다.
-------
5만인 경우
ArrayList: 861167ns
LinkedList: 812041ns
LinkedList가 더 빠릅니다.
-------
10만인 경우
ArrayList: 1125792ns
LinkedList: 1104000ns
LinkedList가 더 빠릅니다.
-------
100만인 경우
ArrayList: 3902916ns
LinkedList: 3254834ns
LinkedList가 더 빠릅니다.
-------
500만인 경우
ArrayList: 6164500ns
LinkedList: 9287500ns
ArrayList가 더 빠릅니다.
-------
1000만인 경우
ArrayList: 16347375ns
LinkedList: 28890875ns
ArrayList가 더 빠릅니다.
-------
1500만인 경우
ArrayList: 26872208ns
LinkedList: 47006875ns
ArrayList가 더 빠릅니다.
-------
2000만인 경우
ArrayList: 137120125ns
LinkedList: 59482041ns
LinkedList가 더 빠릅니다.
-------
3000만인 경우
ArrayList: 69985750ns
LinkedList: 107208750ns
ArrayList가 더 빠릅니다.
-------
4000만인 경우
ArrayList: 43346417ns
LinkedList: 91117459ns
ArrayList가 더 빠릅니다.
-------
5000만인 경우
ArrayList: 313124500ns
LinkedList: 111122791ns
LinkedList가 더 빠릅니다.
-------값으로 요소를 제거하는 경우(Opinion)
- 값으로 중간 지점의 요소를 제거할 때 일반적으로 LinkedList가 더 빠른 걸로 보여진다.
이러한 차이가 나는 이유는 아래와 같다.
- ArrayList는 값으로 조회 후(O(N)) -> 제거(O(N)) 시간 복잡도가 걸린다.
- LinekdList는 값으로 조회 후(O(N)) -> 제거(O(1)) 시간 복잡도가 걸린다.
정리
| 상황 | ArrayList | LinkedList | 추천 |
|---|---|---|---|
| 마지막에 요소 추가 | 여유 공간이 있을 경우 O(1) / 없을 경우 O(N) | O(1) | ? |
| 주어진 Index에 요소 추가 | O(N) | O(N) | ? |
| 값으로 검색 | O(N) | O(N) | ArrayList |
| Index로 검색 | O(1) | O(N) | ArrayList |
| Index로 요소 제거 | O(N) | O(N) | ? |
| 값으로 요소 제거 | O(N) | O(N) | ? |
우선.. 블로그 글을 작성하면서 확실한 부분과 확실하지 않은 부분이 갈렸다🤔
(상황에 따라 애매한 부분은 ?로 추천 칼럼에 적어뒀다.)
확실한 부분
1) 조회를 빈번하게 하는 경우에는 ArrayList를 활용하자
-
Index로 검색할 때는 ArrayList는 O(1) 시간 복잡도를 가지며 index로 value를 바로 접근해서 가져왔다.
-
값으로 검색할 때는 처음에 ArrayList와 LinkedList 두 컬렉션의 성능이 비슷할 줄 알았지만 ArrayList가 더 빨랐다.
-
이유는
캐시 지역성때문이다. 결국엔 메모리 공간에서 데이터를 캐시로 가져올 때 한 줄로 가져오며 연속적으로 메모리 주소를 가지고 있는 ArrayList가 캐시 적중률이 현저히 높았고 그만큼 오버 헤드가 적었다. 이에 비해 LinkedList는 주소값을 통해서 Node를 각각 찾기 때문에 캐시 적중률이 현저히 낮았고 그만큼 오버 헤드가 많이 발생한다고 생각했다.
2) 데이터의 처음과 끝 부분에 빈번하게 추가 삭제가 일어날 경우에는 LinkedList를 활용하자.
- 성능 테스트를 하면서 느낀 부분은 LinkedList는 확실히 무언가를 삭제, 추가 하는 경우에 성능은 Node를 생성하고 연결시키면 끝나기 때문에 시간 복잡도가 O(1)이다. 하지만 데이터를 찾는 과정에서 생각 보다 많이! ArrayList에 비해 오버헤드가 발생한다. 그렇기 때문에 끝쪽에 데이터가 빈번히 변경되는 경우인
Stack,Queue자료구조로 적극 활용하면 좋을 것 같다고 판단했다.
확실하지 않은 부분
위 상단에 애매하다고 생각된 부분은 추천 컬럼에 ? 표시를 해두었다.
상황에 따라 많이 달라지기 때문이다.
1) 마지막에 요소를 추가하거나 삭제할 때?
- 여유 공간이 있을 경우 마지막 요소 추가에 대한 부분은 ArrayList, LinkedList 두 컬렉션이 O(1) 시간 복잡도를 보여준다. 이 중에서도 여유 공간이 있는 상황에 ArrayList의 추가/삭제 작업이 더욱 빠르다. 하지만 여유 공간이 없는 상황에서는 ArrayList는 내부적으로 새로 확장된 배열을 생성해서 복사를 하기 때문에 O(N)이 소요가 된다.
사용 공간의 크기를 사전에 알고 있는 경우라면 마지막 요소 추가 및 삭제를 할 때 ArrayList를 활용해도 굉장히 좋을 것 같다. 하지만 크기를 알 수가 없는 경우라면 LinkedList를 사용을 권장한다.
이렇게 유용한 정보를 공유해주셔서 감사합니다.