Algorithm & Data Structure/DataStructure
Java: ArrayList vs LinkedList
슝슝이입니다
2024. 7. 31. 13:31
반응형
ArrayList vs LinkedList: 차이점 및 성능 비교
자바 컬렉션 프레임워크는 다양한 데이터 구조를 제공하며, 그 중 ArrayList와 LinkedList는 List 인터페이스를 구현한 대표적인 클래스들입니다. 이 글에서는 ArrayList와 LinkedList의 차이점, 장단점, 그리고 성능 비교를 다루겠습니다.
List 인터페이스의 구현체
List 인터페이스를 구현한 대표적인 클래스는 다음과 같습니다:
- ArrayList
- LinkedList
- Vector
- Stack
이 중에서 ArrayList와 LinkedList의 차이점을 중점적으로 살펴보겠습니다.
ArrayList란?
ArrayList는 배열을 기반으로 한 리스트로, 중복을 허용하고 순서를 유지하며 인덱스로 원소들을 관리합니다. 배열과 유사하지만, 배열의 크기가 고정된 것과 달리 ArrayList는 동적으로 크기를 조정할 수 있습니다.
// Java ArrayList 예시
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
for (int value : arrayList) {
System.out.println(value); // 출력: 1 2 3
}
}
}
ArrayList의 특징 및 내부 동작
- 동적 크기 조정: 요소를 추가할 때 배열의 용량이 부족하면 더 큰 배열을 생성하고 기존 배열의 요소를 복사합니다.
- Random Access: 인덱스를 통한 빠른 접근이 가능하여 탐색에 유리합니다.
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 용량 확인 및 조정
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
elementData = Arrays.copyOf(elementData, newCapacity);
}
장점
- Random Access에 강함: 인덱스를 통해 O(1) 시간에 요소를 접근할 수 있습니다.
- Cache 효율성: 연속된 메모리 블럭이므로 캐시 히트율이 높습니다.
단점
- 중간 삽입/삭제가 비효율적: 요소들을 이동시켜야 하므로 O(N) 시간이 소요됩니다.
- 메모리 사용: 크기 조정 시 새로운 배열을 생성하고 기존 배열을 복사하는 작업이 필요합니다.
LinkedList란?
LinkedList는 노드들이 포인터로 연결된 자료 구조입니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터를 포함합니다.
// Java LinkedList 예시
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
for (int value : linkedList) {
System.out.println(value); // 출력: 1 2 3
}
}
}
LinkedList의 특징 및 내부 동작
- 노드 기반 구조: 각 노드는 데이터와 다음 노드를 가리키는 포인터를 가집니다.
- 양방향 연결: 양방향으로 연결되어 있어 앞뒤로 탐색이 가능합니다.
장점
- 삽입/삭제가 효율적: 포인터만 변경하면 되므로 O(1) 시간이 소요됩니다.
- 유연한 크기: 필요에 따라 동적으로 크기를 조정할 수 있습니다.
단점
- Random Access가 비효율적: 요소에 접근하려면 처음부터 차례대로 탐색해야 하므로 O(N) 시간이 소요됩니다.
- Cache 효율성 낮음: 불연속 메모리 블럭이므로 캐시 히트율이 낮습니다.
ArrayList vs LinkedList 성능 비교
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class ListPerformanceTest {
public static void main(String[] args) {
List<Integer> arrayList = new ArrayList<>(2000000);
List<Integer> linkedList = new LinkedList<>();
System.out.println("= 순차적으로 추가하기 =");
System.out.println("ArrayList : " + addSequentially(arrayList));
System.out.println("LinkedList : " + addSequentially(linkedList));
System.out.println("= 중간에 추가하기 =");
System.out.println("ArrayList : " + addInMiddle(arrayList));
System.out.println("LinkedList : " + addInMiddle(linkedList));
System.out.println("= 중간에서 삭제하기 =");
System.out.println("ArrayList : " + removeInMiddle(arrayList));
System.out.println("LinkedList : " + removeInMiddle(linkedList));
System.out.println("= 순차적으로 삭제하기 =");
System.out.println("ArrayList : " + removeSequentially(arrayList));
System.out.println("LinkedList : " + removeSequentially(linkedList));
}
public static long addSequentially(List<Integer> list) {
long start = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) {
list.add(i);
}
return System.currentTimeMillis() - start;
}
public static long addInMiddle(List<Integer> list) {
long start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
list.add(list.size() / 2, i);
}
return System.currentTimeMillis() - start;
}
public static long removeSequentially(List<Integer> list) {
long start = System.currentTimeMillis();
for (int i = list.size() - 1; i >= 0; i--) {
list.remove(i);
}
return System.currentTimeMillis() - start;
}
public static long removeInMiddle(List<Integer> list) {
long start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
list.remove(list.size() / 2);
}
return System.currentTimeMillis() - start;
}
}
성능 결과
= 순차적으로 추가하기 =
ArrayList : 126ms
LinkedList : 171ms
= 중간에 추가하기 =
ArrayList : 1695ms
LinkedList : 10ms
= 중간에서 삭제하기 =
ArrayList : 1303ms
LinkedList : 122ms
= 순차적으로 삭제하기 =
ArrayList : 8ms
LinkedList : 23ms
성능 차이 분석
- 순차적으로 추가하기: ArrayList가 LinkedList보다 빠릅니다. ArrayList는 배열 끝에 요소를 추가하는 데 최적화되어 있습니다.
- 중간에 추가하기: LinkedList가 훨씬 빠릅니다. ArrayList는 중간에 요소를 추가할 때 모든 요소를 이동시켜야 합니다.
- 중간에서 삭제하기: LinkedList가 더 빠릅니다. ArrayList는 중간 요소를 삭제할 때 모든 요소를 이동시켜야 합니다.
- 순차적으로 삭제하기: ArrayList가 더 빠릅니다. LinkedList는 각 요소를 찾아가며 삭제해야 하기 때문입니다.
결론
- ArrayList: 탐색이 빠르고, 순차적인 추가/삭제가 효율적입니다. 그러나 중간 삽입/삭제가 빈번하면 성능이 떨어집니다.
- LinkedList: 중간 삽입/삭제가 빠르고, 메모리 효율성이 좋습니다. 그러나 탐색 속도가 느리고, 순차적 접근에서 성능이 떨어집니다.
적용 시나리오:
- ArrayList: 데이터의 크기가 변하지 않거나, 순차적 추가/삭제가 많은 경우.
- LinkedList: 중간 삽입/삭제가 빈번하거나, 요소의 크기가 자주 변하는 경우.
이 글을 통해 ArrayList와 LinkedList의 특성을 이해하고, 상황에 맞는 자료 구조를 선택하는 데 도움이 되길 바랍니다.
반응형