👤 리스트 추상화
List 자료 구조는 순서가 있고, 중복을 허용하는 자료 구조라고 했다. 앞서 직접 구현했던 MyArrayList, MyLinkedList 모두 내부 구현만 약간 다를 뿐, 같은 기능을 제공하는 “List” 다. 상황에 따라 성능은 달라질 수 있지만, 사용자 관점에서는 같은 기능을 제공한다는 것이다. 이 둘의 공통 기능을 인터페이스로 뽑아내서 추상화 한다면 다형성을 활용한 다양한 이익을 얻을 수 있을 것이다.
위 그림처럼 MyArrayList와 MyLinkedList의 공통 부분을 MyList 인터페이스로 뽑아내보자.
// 공통 부분을 인터페이스로 뽑아냈다.
package collection.list;
public interface MyList<E> {
int size();
void add(E element);
void add(int index, E element);
E get(int index);
E set(int index, E element);
E remove(int index);
int indexOf(E element);
}// MyArrayList
package collection.list;
import java.util.Arrays;
public class MyArrayList<E> implements MyList<E> {
private static final int DEFAULT_CAPACITY = 5;
private Object[] elementData;
private int size = 0;
public MyArrayList() {
elementData = new Object[DEFAULT_CAPACITY];
}
public MyArrayList(int initialCapacity) {
elementData = new Object[initialCapacity];
}
@Override
public int size() {
return size;
}
@Override
public void add(E element) {
if (size == elementData.length) {
grow();
}
elementData[size] = element;
size++;
}
@Override
public void add(int index, E element) {
if (size == elementData.length) {
grow();
}
// 데이터 이동
shiftRightFrom(index);
elementData[index] = element;
size++;
}
// 요소의 마지막부터 index까지 오른쪽으로 밀기
private void shiftRightFrom(int index) {
for (int i = size; i > index; i--) {
elementData[i] = elementData[i - 1];
}
}
// 요소의 index부터 마지막까지 왼쪽으로 밀기
private void shiftLeftFrom(int index) {
for (int i = index; i < size - 1; i++) {
elementData[i] = elementData[i + 1];
}
}
@Override
public E remove(int index) {
E oldValue = get(index);
shiftLeftFrom(index);
size--;
elementData[size] = null;
return oldValue;
}
private void grow() {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity * 2;
elementData = Arrays.copyOf(elementData, newCapacity);
}
@SuppressWarnings("unchecked")
@Override
public E get(int index) {
return (E) elementData[index];
}
@Override
public E set(int index, E element) {
E oldValue = get(index);
elementData[index] = element;
return oldValue;
}
@Override
public int indexOf(E index) {
for (int i = 0; i < size; i++) {
if (index.equals(elementData[i])) {
return i; // 찾으면 해당 인덱스 번호 반환
}
}
// 못 찾으면 -1을 반환
return -1;
}
@Override
public String toString() {
return Arrays.toString(Arrays.copyOf(elementData, size)) +
" size=" + size + ", capacity=" + elementData.length;
}
}// MyLinkedList
package collection.list;
public class MyLinkedList<E> implements MyList<E> {
private Node<E> first; // 첫 노드의 위치
private int size = 0; // 자료 구조에 입력된 데이터의 사이즈
// 새로운 노드를 만들어서 마지막 노드에 연결
@Override
public void add(E e) {
Node<E> newNode = new Node(e); // 새로운 노드 만들기
if (first == null) {
first = newNode;
} else {
Node<E> lastNode = getLastNode(); // 마지막 노드의 위치를 찾아서
lastNode.next = newNode; // next에 새로운 노드의 위치를 대입
}
size++;
}
private Node<E> getLastNode() {
Node<E> x = first;
while (x.next != null) {
x = x.next;
}
return x;
}
@Override
public void add(int index, E e) {
Node<E> newNode = new Node<>(e);
if (index == 0) {
newNode.next = first;
first = newNode;
} else {
Node<E> prevNode = getNode(index - 1);
newNode.next = prevNode.next;
prevNode.next = newNode;
}
}
// 특정 위치의 노드를 찾아서 안의 데이터를 변경
@Override
public E set(int index, E element) {
Node<E> x = getNode(index);
E oldValue = x.item;
x.item = element;
return oldValue;
}
// 중간 위치의 데이터를 삭제하는 메서드
@Override
public E remove(int index) {
Node<E> removeNode = getNode(index); // 삭제하고 싶은 노드
E removedItem = removeNode.item;
if (index == 0) {
first = removeNode.next;
} else {
Node<E> prev = getNode(index - 1);
prev.next = removeNode.next;
}
// 삭제할 노드를 초기화
removeNode.item = null;
removeNode.next = null;
size--;
return removedItem;
}
// 특정 위치에 있는 노드의 데이터를 반환
@Override
public E get(int index) {
Node<E> node = getNode(index);
return node.item;
}
private Node<E> getNode(int index) {
Node<E> x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}
// 몇 번째 인덱스에 있는지 찾아서 반환
@Override
public int indexOf(E o) {
int index = 0;
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
return index;
}
index++;
}
// 없으면 -1 반환
return -1;
}
@Override
public int size() {
return size;
}
@Override
public String toString() {
return "MyLinkedListV1{" +
"first=" + first +
", size=" + size +
'}';
}
// Node 클래스를 제네릭 타입으로 선언
private static class Node<E> {
E item; // Integer로 들어올지, String으로 들어올지 모르겠다!
Node<E> next;
public Node(E item) {
this.item = item;
}
// [A -> B -> C] 형식으로 출력하고 싶다.
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node<E> x = this;
sb.append("[");
while (x != null) {
sb.append(x.item);
if (x.next != null) {
sb.append(" -> ");
}
x = x.next;
}
sb.append("]");
return sb.toString();
}
}
}리스트 기능을 추상화한 제네릭 인터페이스 MyList<E>를 정의했다. 인터페이스 내부에는 공통 기능인 add, get, set, remove, size, indexOf 메서드 등이 포함되어 있다. 그 후, 기존 MyArrayList, MyLinkedList를 MyList 인터페이스를 구현하도록 리팩토링함으로써 중복 코드를 제거하고 다형성을 활용하여 구현체 교체가 유연하게 이루어질 수 있도록 구조 개선시켰다.
이때 만약 모 회사에서 위의 MyArrayList를 활용해서 많은 양의 데이터를 처리하는 BatchProcessor 클래스를 연구하고 있다고 해보자. 하지만 프로그램을 개발하고 돌려보니 많은 양의 데이터가 앞에 추가되는 상황이 많았다. 이처럼 데이터가 앞에서 추가 혹은 삭제되는 상황이 많다면 MyArrayList보다는 MyLinkedList를 사용하는 것이 더 효율적일 것이다. 아래 코드를 살펴보자.
public class BatchProcessor {
private final MyArrayList<Integer> list = new MyArrayList<>();
public void logic(int size) {
for (int i = 0; i < size; i++) {
list.add(0, i);
}
}
}이런 식으로 구체적인 MyArrayList에 의존하고 있는 BatchProcessor 코드다. 이제 여기서 MyLinkedList를 사용하고 싶다면, MyLinkedList로 직접 갈아 끼워야 한다.
public class BatchProcessor {
private final MyLinkedList<Integer> list = new MyLinkedList<>(); // 직접 교체
public void logic(int size) {
for (int i = 0; i < size; i++) {
list.add(0, i);
}
}
}지금 이런 상황을 BatchProcessor 클래스가 구체적인 MyArrayList나 MyLinkedList 클래스에 의존하고 있다고 표현한다. 이렇게 처리하면 다른 구체적인 클래스로 교체하고 싶을 때마다 BatchProcessor의 코드도 수정해야 한다는 문제점이 있다. 바로 이때 BatchProcessor 클래스가 추상적인 MyList 인터페이스에 의존하도록 하는 방법이 있다. 의존관계 주입(DI)을 활용함으로써 다형성을 극한으로 끌어올리는 것이다.
“난 배열 리스트 구조를 사용할거야!”, “난 링크 리스트 구조를 사용할거야!” 과 같은 “결정” 을 BatchProcessor 클래스를 작성하는 시점이 아닌, 실제 프로그램이 실행될 때(런타임) 결정하도록 하는 것이다. 이렇게 하면 MyList 인터페이스를 사용하는 클라이언트 코드(BatchProcessor)를 전혀 손대지 않고 확장 가능하다.
package collection.list;
public class BatchProcessor {
// private final MyArrayList<Integer> list = new MyArrayList<>();
// private final MyLinkedList<Integer> list = new MyLinkedList<>();
private final MyList<Integer> list;
// 부모(MyList)는 자식(MyArrayList, MyLinkedList)을 담을 수 있다.
public BatchProcessor(MyList<Integer> list) {
this.list = list;
}
public void logic(int size) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
list.add(0, i); // 데이터를 맨 앞에 추가
}
long endTime = System.currentTimeMillis();
System.out.println("크기: " + size + ", 계산 시간: " + (endTime - startTime) + "ms");
}
}이처럼 MyList 타입의 list의 구현체를 프로그램이 실제 실행될 시점에 생성자를 통해 결정하도록 하는 것이다. 현재 BatchProcessor는 구체적인 구현체가 무엇이 들어올지, 즉 MyArrayList가 들어올지, MyLinkedList가 들어올지 전혀 알 수 없다는 것이다. 이처럼 BatchProcessor의 외부에서 의존 관계가 결정되고 BatchProcessor 인스턴스에 주입되는 것 같다고 해서 “의존 관계 주입(Dependency Injection)” 이라고 한다.
package collection.list;
public class BatchProcessorMain {
public static void main(String[] args) {
// MyArrayList<Integer> list = new MyArrayList<>();
// BatchProcessor processor = new BatchProcessor(list); // 크기: 100000, 계산 시간: 4716ms
MyLinkedList<Integer> list = new MyLinkedList<>();
BatchProcessor processor = new BatchProcessor(list); // 크기: 100000, 계산 시간: 2ms
processor.logic(100_000);
}
}위와 같이 BatchProcessor 의 생성자에 MyArrayList를 사용할지, MyLinkedList를 사용할지 결정해서 넘겨야 한다. 쉽게 말해, 실제 실행했을 때 new BatchProcessor(list) 부분을 보면, 현재 list는 MyLinkedList로 설정하고 실행 되었으므로 “어? 너 MyLinkedList 써? ㅇㅋ… MyLinkedList를 장착한 BatchProcessor 인스턴스 생성하고 넘겨줄게!” 라고 하는 것이다. 이후에 인스턴스의 메서드를 호출하면 생성자로 넘긴 MyLinkedList를 사용해서 실행되는 것이다.
🤼♂️ 컴파일 타임 vs 런타임 의존 관계
의존 관계는 크게 코드 컴파일 시점인 Compile Time과 프로그램의 실행 시점인 Runtime으로 나눌 수 있다.
컴파일 타임 의존 관계는 자바 컴파일러가 바라보는 의존 관계다. 쉽게 말해, 클래스에 바로 보이는 의존 관계로, 실행하지 않은 소스 코드에 정적으로 나타나는 의존 관계다. 현재 BatchProcessor 클래스를 보면 MyList 인터페이스에만 의존하고 있다. BatchProcessor 내부를 보면 그 어디에서도 MyArrayList나 MyLinkedList와 같은 구체적인 구현체에 대한 정보는 찾아볼 수 없다.
런타임 의존 관계의 경우, 실제 프로그램이 실행될 때 보이는 의존 관계를 말한다. 주로 생성된 인스턴스와 그것을 참조하는 의존 관계다. 쉽게 말해, 프로그램이 실행될 때 인스턴스 간에 의존 관계라고 생각하면 된다. 런타임 의존 관계는 프로그램 실행 중에 계속해서 변할 수 있다. 아래 예시 코드를 보자.
MyArrayList<Integer> list = new MyArrayList<>();
BatchProcessor processor = new BatchProcessor(list);
processor.logic(50_000); BatchProcessor 인스턴스의 MyList list는 생성자를 통해 MyArrayList 인스턴스를 참조(x001)한다. BatchProcessor 인스턴스에 해당 참조값(x001)을 넣어줌으로써 의존 관계를 주입하는 것이다. 따라서 그 이후에 logic()을 호출하면 자연스럽게 MyArrayList 인스턴스가 사용된다. MyLinkedList로 교체하는 상황도 마찬가지다.
정리하자면, 이제 MyList 인터페이스의 도입함으로써 같은 List 자료 구조를 그대로 사용하면서 원하는 구현을 변경할 수 있게 되었다. 기존에는 BatchProcessor 클래스에서 직접 구체적인 구현체에 의존하게 해서 변경을 원한다면 직접 갈아 끼워야 했다. 하지만, 이제 추상적인 List 인터페이스에 의존하게 해서 런타임에 MyList의 구현체를 얼마든지 쉽게 선택할 수 있다. BatchProcessor에서 사용하는 리스트의 의존 관계를 클래스에서 “미리 결정 하는 것” 이 아니라, 런타임에 객체를 생성하는 시점으로 “결정을 미루는 것” 이다. 이렇게 해서 런타임에 MyList의 구현체를 변경해도 BatchProcessor의 코드는 전혀 변경하지 않아도 된다.
위와 같은 식으로 생성자를 통해 의존 관계를 주입하는 방법을 “생성자 주입” 이라고 한다. 덕분에 클라이언트 코드의 변경 없이, 구현 알고리즘인 MyList 인터페이스의 구현을 자유롭게 확장함으로써 OCP 원칙을 지킬 수 있다.
“클라이언트 클래스는 컴파일 타임에 추상적인 것에 의존하고, 런타임에 의존 관계 주입을 통해 구현체를 주입받아 사용함으로써, 이런 이점을 얻을 수 있다.”
🛠 직접 구현한 리스트의 성능 비교
package collection.list;
public class MyListPerformanceTest {
public static void main(String[] args) {
int size = 50_000;
System.out.println("=== MyArrayList 추가 ===");
addFirst(new MyArrayList<>(), size);
addMiddle(new MyArrayList<>(), size); // 찾는 과정은 O(1), 데이터를 추가하는데 밀어야 하므로 O(n)
MyArrayList<Integer> arrayList = new MyArrayList<>(); // 조회용 데이터
addLast(arrayList, size); // 찾는 과정은 O(1), 데이터를 추가하는데 O(1)
int loop = 10_000; // 1만번을 돌면서 조회를 해보자.
System.out.println("=== MyArrayList 조회 ===");
getIndex(arrayList, loop, 0); // 앞부분을 조회하는 경우
getIndex(arrayList, loop, size / 2); // 중간 부분을 조회하는 경우
getIndex(arrayList, loop, size - 1); // 마지막 부분을 조회하는 경우
System.out.println("=== MyArrayList 검색 ===");
search(arrayList, loop, 0); // 앞부분에서 바로 찾음
search(arrayList, loop, size / 2); // 중간 부분에서 찾음
search(arrayList, loop, size - 1); // 가장 마지막에서 찾음
System.out.println("=== MyLinkedList 추가 ===");
addFirst(new MyLinkedList<>(), size);
addMiddle(new MyLinkedList<>(), size); // 찾는 과정은 O(n), 데이터를 추가하는데 O(1)
MyLinkedList<Integer> linkedList = new MyLinkedList<>(); // 조회용 데이터
addLast(linkedList, size); // 찾는 과정은 O(n), 데이터를 추가하는데 O(1)
System.out.println("=== MyLinkedList 조회 ===");
getIndex(linkedList, loop, 0); // 앞부분을 조회하는 경우
getIndex(linkedList, loop, size / 2); // 중간 부분을 조회하는 경우
getIndex(linkedList, loop, size - 1); // 마지막 부분을 조회하는 경우
System.out.println("== MyLinkedList 검색 ==");
search(linkedList, loop, 0); // 앞부분을 조회하는 경우
search(linkedList, loop, size / 2); // 중간 부분을 조회하는 경우
search(linkedList, loop, size - 1); // 마지막 부분을 조회하는 경우
}
private static void addFirst(MyList<Integer> list, int size) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
list.add(0, i);
}
long endTime = System.currentTimeMillis();
System.out.println("앞에 추가 - 크기: " + size + ", 계산 시간: " + (endTime - startTime) + "ms");
}
private static void addMiddle(MyList<Integer> list, int size) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
list.add(i / 2, i); // 대략 중간 정도 위치에 데이터를 추가
}
long endTime = System.currentTimeMillis();
System.out.println("평균 추가 - 크기: " + size + ", 계산 시간: " + (endTime - startTime) + "ms");
}
private static void addLast(MyList<Integer> list, int size) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
list.add(i);
}
long endTime = System.currentTimeMillis();
System.out.println("뒤에 추가 - 크기: " + size + ", 계산 시간: " + (endTime - startTime) + "ms");
}
private static void getIndex(MyList<Integer> list, int loop, int index) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < loop; i++) {
list.get(index);
}
long endTime = System.currentTimeMillis();
System.out.println("인덱스: " + index + ", 반복: " + loop + ", 계산 시간: " + (endTime - startTime) + "ms");
}
private static void search(MyList<Integer> list, int loop, int findValue) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < loop; i++) {
list.indexOf(findValue);
}
long endTime = System.currentTimeMillis();
System.out.println("찾는 값: " + findValue + ", 반복: " + loop + ", 계산 시간: " + (endTime - startTime) + "ms");
}
}
/*
=== MyArrayList 추가 ===
앞에 추가 - 크기: 50000, 계산 시간: 1143ms
평균 추가 - 크기: 50000, 계산 시간: 517ms
뒤에 추가 - 크기: 50000, 계산 시간: 1ms
=== MyArrayList 조회 ===
인덱스: 0, 반복: 10000, 계산 시간: 0ms
인덱스: 25000, 반복: 10000, 계산 시간: 0ms
인덱스: 49999, 반복: 10000, 계산 시간: 0ms
=== MyArrayList 검색 ===
찾는 값: 0, 반복: 10000, 계산 시간: 0ms
찾는 값: 25000, 반복: 10000, 계산 시간: 104ms
찾는 값: 49999, 반복: 10000, 계산 시간: 195ms
=== MyLinkedList 추가 ===
앞에 추가 - 크기: 50000, 계산 시간: 3ms
평균 추가 - 크기: 50000, 계산 시간: 948ms
뒤에 추가 - 크기: 50000, 계산 시간: 1878ms
=== MyLinkedList 조회 ===
인덱스: 0, 반복: 10000, 계산 시간: 0ms
인덱스: 25000, 반복: 10000, 계산 시간: 376ms
인덱스: 49999, 반복: 10000, 계산 시간: 748ms
== MyLinkedList 검색 ==
찾는 값: 0, 반복: 10000, 계산 시간: 0ms
찾는 값: 25000, 반복: 10000, 계산 시간: 409ms
찾는 값: 49999, 반복: 10000, 계산 시간: 816ms
*/<Macbook M3 Pro 기준>
| 기능 | MyArrayList | MyLinkedList |
|---|---|---|
| 앞에 추가/삭제 | O(n): 1143ms | O(1): 3ms |
| 평균 추가/삭제 | O(n): 517ms | O(n): 948ms |
| 뒤에 추가/삭제 | O(1): 1ms | O(n): 1878ms |
| 인덱스 조회 | O(1): 0ms | O(n): 평균 376ms |
| 검색 | O(n): 평균 104ms | O(n): 평균 409ms |
🤔 왜 검색에서 MyArrayList와 MyLinkedList 성능 차이가 많이 나지?
어차피 MyArrayList든 MyLinkedList든 검색할 데이터가 들어 있는 곳까지 계속 까봐야 하는데 왜 이렇게 성능 차이가 심할까? 비슷해야 하는거 아닌가? 실제 성능은 요소의 순차적 접근 속도, 메모리 할당 및 해제 비용, CPU 캐시 활용도 등 다양한 요소에 의해 영향을 받는다. MyArrayList는 요소들이 메모리 상에 연속적으로 위치하기 때문에 CPU 캐시 효율이 좋고, 메모리 접근 속도가 빠른 반면, MyLinkedList는 각 요소가 별도의 노드로 존재하고 다음 요소의 참조를 저장하고 있기 때문에 CPU 캐시 효율이 떨어지고, 메모리 접근 속도가 상대적으로 느릴 수 있다. 이런 부분들을 고려할 때, MyArrayList가 실제 사용 환경에서 더 나은 성능을 보여주는 경우가 많다.
📚 자바 Collection Framework - List
자바의 컬렉션 프레임워크가 제공하는 List는 가장 대표적인 자료 구조다. 아래 구조를 살펴보자.
Collection 인터페이스는 java.util 패키지의 컬렉션 프레임워크의 핵심 인터페이스 중 하나로, 자바에서 다양한 컬렉션, 즉 데이터 그룹을 다루기 위한 메서드를 정의한다. 여기서 List 인터페이스는 java.util 패키지에 있는 컬렉션 프레임워크의 일부다. List는 객체들의 순서가 있는 컬렉션을 나타내며, 같은 객체의 중복 저장을 허용한다. 이 리스트는 배열과 비슷하지만, 크기가 동적으로 변화하는 컬렉션 을 다룰 때 유연하게 사용할 수 있다.
<List 인터페이스의 주요 메서드>
| 메서드 형식 | 설명 |
|---|---|
add(E e) | 리스트의 끝에 지정된 요소를 추가한다. |
add(int index, E element) | 리스트의 지정된 위치에 요소를 삽입한다. |
addAll(Collection<? extends E> c) | 지정된 컬렉션의 모든 요소를 리스트의 끝에 추가한다. |
addAll(int index, Collection<? extends E> c | 지정된 컬렉션의 모든 요소를 리스트의 지정된 위치에 추가한다. |
get(int index) | 리스트에서 지정된 위치의 요소를 반환한다. |
set(int index, E element) | 지정한 위치의 요소를 변경하고, 이전 요소를 반환한다. |
remove(int index) | 리스트에서 지정된 위치의 요소를 제거하고 그 요소를 반환한다. |
remove(Object o) | 리스트에서 지정된 첫 번째 요소를 제거한다. |
clear() | 리스트에서 모든 요소를 제거한다. |
indexOf(Object o) | 리스트에서 지정된 요소의 첫 번째 인덱스를 반환한다. |
lastIndexOf(Object o) | 리스트에서 지정된 요소의 마지막 인덱스를 반환한다. |
contains(Object o) | 리스트가 지정된 요소를 포함하고 있는지 여부를 반환한다.. |
sort(Comparator<? super E> c) | 리스트의 요소를 지정된 비교자에 따라 정렬한다. |
subList(int fromIndex, int toIndex) | 리스트의 일부분의 뷰를 반환한다. |
size() | 리스트의 요소 수를 반환한다. |
isEmpty() | 리스트가 비어있는지 여부를 반환한다. |
iterator() | 리스트의 요소에 대한 반복자를 반환한다. |
toArray() | 리스트의 모든 요소를 배열로 반환한다. |
toArray(T[] a) | 리스트의 모든 요소를 지정된 배열로 반환한다. |
🚋 ArrayList
자바가 제공하는 ArrayList는 기존에 직접 구현해봤던 MyArrayList와 거의 비슷하다. 특징을 살펴보자면…
-
배열을 사용해서 데이터를 관리한다.
-
기본
CAPACITY는 10이다.CAPACITY를 넘어가면 배열을 50% 증가시킨다.- 10 → 15 →22 → 33 → 49로 증가시킨다.
-
메모리 고속 복사 연산을 사용한다.
ArrayList의 중간 위치에 데이터를 추가하면, 그 추가된 데이터를 위해 중간 위치 이후의 요소들이 뒤로 하나 이동해야 한다.- 자바가 제공하는
ArrayList는 이 부분을 최적화 하는데, 배열의 요소 이동은 시스템 레벨에서 최적화된 메모리 고속 복사 연산을 사용해서 비교적 빠르게 수행된다. 참고로System.arraycopy()를 사용한다.
🚀 메모리 고속 복사 연산
⛓ LinkedList
자바가 제공하는 LinkedList도 마찬가지로, 직접 구현해봤던 MyLinkedList와 거의 비슷하다. 하지만 자바가 제공하는 LinkedList의 경우에는 이중 연결 리스트 구조를 가지고 있고, 첫 번째 노드와 마지막 노드를 모두 참조할 수 있다.
이중 연결 구조를 통해, 다음 노드 뿐만 아니라 이전 노드로도 이동 가능하다. 그리고 마지막 노드도 참조할 수 있으므로 데이터를 마지막에 추가하는 경우에도 O(1)의 성능을 제공한다. 양방향으로 이동이 가능하기 때문에 인덱스 조회 성능을 최적화 할 수 있다. 예를 들어, 인덱스가 사이즈의 절반 이하라면 처음 노드로부터 타고 타고 올라가고, 인덱스가 사이즈의 절반을 넘는다면, 마지막 노드로부터 타고 타고 내려오면서 성능을 최적화 할 수 있다.
🛠 자바 리스트의 성능 비교
package collection.list;
import java.util.ArrayList;
import java.util.List;
import java.util.LinkedList;
public class JavaListPerformanceTest {
public static void main(String[] args) {
int size = 50_000;
System.out.println("=== ArrayList 추가 ===");
addFirst(new ArrayList<>(), size);
addMiddle(new ArrayList<>(), size); // 찾는 과정은 O(1), 데이터를 추가하는데 밀어야 하므로 O(n)
ArrayList<Integer> arrayList = new ArrayList<>(); // 조회용 데이터
addLast(arrayList, size); // 찾는 과정은 O(1), 데이터를 추가하는데 O(1)
int loop = 10_000; // 1만번을 돌면서 조회를 해보자.
System.out.println("=== ArrayList 조회 ===");
getIndex(arrayList, loop, 0); // 앞부분을 조회하는 경우
getIndex(arrayList, loop, size / 2); // 중간 부분을 조회하는 경우
getIndex(arrayList, loop, size - 1); // 마지막 부분을 조회하는 경우
System.out.println("=== ArrayList 검색 ===");
search(arrayList, loop, 0); // 앞부분에서 바로 찾음
search(arrayList, loop, size / 2); // 중간 부분에서 찾음
search(arrayList, loop, size - 1); // 가장 마지막에서 찾음
System.out.println("=== LinkedList 추가 ===");
addFirst(new LinkedList<>(), size);
addMiddle(new LinkedList<>(), size); // 찾는 과정은 O(n), 데이터를 추가하는데 O(1)
LinkedList<Integer> linkedList = new LinkedList<>(); // 조회용 데이터
addLast(linkedList, size); // 찾는 과정은 O(1), 데이터를 추가하는데 O(1)
System.out.println("=== LinkedList 조회 ===");
getIndex(linkedList, loop, 0); // 앞부분을 조회하는 경우
getIndex(linkedList, loop, size / 2); // 중간 부분을 조회하는 경우
getIndex(linkedList, loop, size - 1); // 마지막 부분을 조회하는 경우
System.out.println("== LinkedList 검색 ==");
search(linkedList, loop, 0); // 앞부분을 조회하는 경우
search(linkedList, loop, size / 2); // 중간 부분을 조회하는 경우
search(linkedList, loop, size - 1); // 마지막 부분을 조회하는 경우
}
private static void addFirst(List<Integer> list, int size) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
list.add(0, i);
}
long endTime = System.currentTimeMillis();
System.out.println("앞에 추가 - 크기: " + size + ", 계산 시간: " + (endTime - startTime) + "ms");
}
private static void addMiddle(List<Integer> list, int size) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
list.add(i / 2, i); // 대략 중간 정도 위치에 데이터를 추가
}
long endTime = System.currentTimeMillis();
System.out.println("평균 추가 - 크기: " + size + ", 계산 시간: " + (endTime - startTime) + "ms");
}
private static void addLast(List<Integer> list, int size) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
list.add(i);
}
long endTime = System.currentTimeMillis();
System.out.println("뒤에 추가 - 크기: " + size + ", 계산 시간: " + (endTime - startTime) + "ms");
}
private static void getIndex(List<Integer> list, int loop, int index) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < loop; i++) {
list.get(index);
}
long endTime = System.currentTimeMillis();
System.out.println("인덱스: " + index + ", 반복: " + loop + ", 계산 시간: " + (endTime - startTime) + "ms");
}
private static void search(List<Integer> list, int loop, int findValue) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < loop; i++) {
list.indexOf(findValue);
}
long endTime = System.currentTimeMillis();
System.out.println("찾는 값: " + findValue + ", 반복: " + loop + ", 계산 시간: " + (endTime - startTime) + "ms");
}
}
/*
=== ArrayList 추가 ===
앞에 추가 - 크기: 50000, 계산 시간: 108ms
평균 추가 - 크기: 50000, 계산 시간: 51ms
뒤에 추가 - 크기: 50000, 계산 시간: 1ms
=== ArrayList 조회 ===
인덱스: 0, 반복: 10000, 계산 시간: 0ms
인덱스: 25000, 반복: 10000, 계산 시간: 0ms
인덱스: 49999, 반복: 10000, 계산 시간: 0ms
=== ArrayList 검색 ===
찾는 값: 0, 반복: 10000, 계산 시간: 1ms
찾는 값: 25000, 반복: 10000, 계산 시간: 102ms
찾는 값: 49999, 반복: 10000, 계산 시간: 199ms
=== LinkedList 추가 ===
앞에 추가 - 크기: 50000, 계산 시간: 2ms
평균 추가 - 크기: 50000, 계산 시간: 944ms
뒤에 추가 - 크기: 50000, 계산 시간: 2ms
=== LinkedList 조회 ===
인덱스: 0, 반복: 10000, 계산 시간: 0ms
인덱스: 25000, 반복: 10000, 계산 시간: 377ms
인덱스: 49999, 반복: 10000, 계산 시간: 0ms
== LinkedList 검색 ==
찾는 값: 0, 반복: 10000, 계산 시간: 1ms
찾는 값: 25000, 반복: 10000, 계산 시간: 407ms
찾는 값: 49999, 반복: 10000, 계산 시간: 813ms
*/| 기능 | ArrayList | LinkedList |
|---|---|---|
| 앞에 추가/삭제 | O(n): 108ms | O(1): 2ms |
| 평균 추가/삭제 | O(n): 51ms | O(n): 944ms |
| 뒤에 추가/삭제 | O(1): 1ms | O(n): 2ms |
| 인덱스 조회 | O(1): 0ms | O(n): 평균 377ms |
| 검색 | O(n): 평균 102ms | O(n): 평균 407ms |
🤔 자바에서 제공되는 ArrayList가 직접 구현한 MyArrayList보다 빠른 이유
자바의 배열 리스트는 이때 메모리 고속 복사를 사용하기 때문에 성능이 최적화된다. 메모리 고속 복사는 시스템에 따라 성능이 다르기 때문에 정확한 계산은 어렵지만 대략 O(n/10) 정도로 추정하면, O(n)이 된다. 하지만 메모리 고속 복사라도 데이터가 아주 많으면 느려진다.
최종적으로 정리하자면, 이론적으로는 중간 위치에 데이터를 추가할 때는 LinkedList가 더 효율적인 것처럼 보이지만, 현대 컴퓨터 시스템의 메모리 접근 패턴, CPU 캐시 최적화, 메모리 고속 복사 등을 고려할 때 ArrayList가 실제 사용 환경에서 더 나은 성능을 보여주는 경우가 많다. 따라서 대부분의 경우 ArrayList가 성능적으로 더 유리하다. 이런 이유로 실무에서는 ArrayList를 기본으로 사용하고, 만약 데이터를 앞쪽에서 추가 및 삭제하는 일이 자주 일어난다면 LinkedList를 고려한다.
