연결리스트
연결리스트는 데이터를 담은 노드를 포인터들로 연결하는 선형 자료구조이다.
각 노드는 데이터와 다음 노드에 대한 포인터를 가지고 있다.
연결리스트에서는 탐색과,추가,삭제 모두 최악의 경우 O(n)시간이 걸린다.
물론 맨 앞에 추가하거나, 삭제 할 때의 시간은 O(1)이 걸린다.
하지만, 실제로는 추가하거나,삭제할 때 이전의 노드를 탐색하는데, 시간이 걸리므로,탐색하는 시간까지 해서 O(n)의 시간이 걸린다.
일반적으로 처음에는 head를 가리키고 있으므로, 맨 앞에서의 연산이 삽입 삭제가 일어날 때는 유리하다고 본다.
그렇기 때문에 자바에서 Queue의 구현체로 LinkedList를 사용하는게 아닐까 싶다.
ArrayList vs LinkedList
삽입시 속도 차이
100개의 데이터일 때
2025-03-20T09:45:08.000+09:00 INFO 4816 --- [demo] [nio-8080-exec-1] com.example.demo.aop.TimeTraceAspect :
Service.addArrayList(..) - Total time = 4.77E-5s
2025-03-20T09:45:08.000+09:00 INFO 4816 --- [demo] [nio-8080-exec-1] com.example.demo.aop.TimeTraceAspect :
Service.addLinkedList(..) - Total time = 2.18E-5s100개일 때는 ArrayList가 훨씬 느리다.
이 이유는 ArrayListd에서 가변적으로 배열을 사용하기 위해서 add시에 배열을 1.5배 copy해서 배열을 늘리는 경우가 존재하기 때문이다.
LinkedList의 경우 삽입시 노드를 할당하고 포인터로 연결하는 과정이 추가되기 때문에 시간이 훨씬 오래 걸린다.
1000개의 데이터일 때
2025-03-20T09:47:52.508+09:00 INFO 10108 --- [demo] [nio-8080-exec-1] com.example.demo.aop.TimeTraceAspect : Service.addArrayList(..) - Total time = 6.78E-5s
2025-03-20T09:47:52.509+09:00 INFO 10108 --- [demo] [nio-8080-exec-1] com.example.demo.aop.TimeTraceAspect : Service.addLinkedList(..) - Total time = 9.5E-5s
2025-03-20T09:48:06.921+09:00 INFO 10108 --- [demo] [nio-8080-exec-2] com.example.demo.aop.TimeTraceAspect : Service.addArrayList(..) - Total time = 6.89E-5s
2025-03-20T09:48:06.921+09:00 INFO 10108 --- [demo] [nio-8080-exec-2] com.example.demo.aop.TimeTraceAspect : Service.addLinkedList(..) - Total time = 7.81E-5s신기한게 1000개일 때는 LinkedList가 더 느리다.
이 이유는 LinkedList에서 발생하는, 노드의 할당, 포인터 연결을 하는 작업이 오래 걸렸기 때문이다.
10000개의 데이터일 때
025-03-20T09:50:17.575+09:00 INFO 10104 --- [demo] [nio-8080-exec-1] com.example.demo.aop.TimeTraceAspect : Service.addArrayList(..) - Total time = 4.955E-4s
2025-03-20T09:50:17.577+09:00 INFO 10104 --- [demo] [nio-8080-exec-1] com.example.demo.aop.TimeTraceAspect : Service.addLinkedList(..) - Total time = 5.236E-4s
2025-03-20T09:50:19.836+09:00 INFO 10104 --- [demo] [nio-8080-exec-2] com.example.demo.aop.TimeTraceAspect : Service.addArrayList(..) - Total time = 6.055E-4s
2025-03-20T09:50:19.837+09:00 INFO 10104 --- [demo] [nio-8080-exec-2] com.example.demo.aop.TimeTraceAspect : Service.addLinkedList(..) - Total time = 6.714E-4s
2025-03-20T09:50:22.595+09:00 INFO 10104 --- [demo] [nio-8080-exec-3] com.example.demo.aop.TimeTraceAspect : Service.addArrayList(..) - Total time = 6.163E-4s
2025-03-20T09:50:22.596+09:00 INFO 10104 --- [demo] [nio-8080-exec-3] com.example.demo.aop.TimeTraceAspect : Service.addLinkedList(..) - Total time = 6.216E-4s이 때도 마찬가지로 LinkedList가 느리다.
즉 매우 적은 데이터일 때는 LinkedList가 큰 데이터일 때는 ArrayList를 사용하는 것이 이득이다.
삭제
한개 삭제시
2025-03-20T10:01:05.214+09:00 INFO 11484 --- [demo] [nio-8080-exec-2] com.example.demo.aop.TimeTraceAspect : Service.removeArray() - Total time = 2.0E-5s
2025-03-20T10:01:05.215+09:00 INFO 11484 --- [demo] [nio-8080-exec-2] com.example.demo.aop.TimeTraceAspect : Service.removeLinked() - Total time = 7.7E-6s한개 삭제 시에는 LinkedList가 더 느리다.
10개 삭제시
2025-03-20T10:07:48.252+09:00 INFO 13732 --- [demo] [nio-8080-exec-6] com.example.demo.aop.TimeTraceAspect : Service.removeArray(..) - Total time = 5.59E-5s
2025-03-20T10:07:48.252+09:00 INFO 13732 --- [demo] [nio-8080-exec-6] com.example.demo.aop.TimeTraceAspect : Service.removeLinked(..) - Total time = 1.13E-5s이때는 LinkedList가 더 빠르다.
100개 삭제시
2025-03-20T10:11:11.070+09:00 INFO 12400 --- [demo] [nio-8080-exec-5] com.example.demo.aop.TimeTraceAspect : Service.removeArray(..) - Total time = 5.631E-4s
2025-03-20T10:11:11.071+09:00 INFO 12400 --- [demo] [nio-8080-exec-5] com.example.demo.aop.TimeTraceAspect : Service.removeLinked(..) - Total time = 2.53E-5s즉 하나일 때만 ArrayList가 빠르고 나머지 경우에는 LinkedList가 더 빠름을 알 수 있다.
이 이유는 LinkedList의 내부 동작방식과 관련이 있다.
내부에서 삭제는 아래의 코드로 동작한다.
public E remove(int index) {
checkElementIndex(index); // 유효성 검사
return unlink(node(index)); // ★ 핵심 호출 부분!
}
Node<E> node(int index) {
// 리스트의 앞 절반이면 첫 노드부터 탐색
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { // 리스트의 뒤 절반이면 마지막 노드부터 역으로 탐색
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}이 때 node의 메서드를 호출하는데 index가 0인경우에는 사실 node메서드의 호출이 필요없이 첫번째 노드를 unlink하면된다.
JVM은 이 작업이 반복 되면 최적화하기 때문에 LinkedList가 더 빠른 것이다.
동일한 코드가 여러 번 호출되면 JVM은 내부적으로 프로파일링(profiling)을 통해 이 코드가 자주 실행된다는 것을 인지한다.
for(int i=0; i<10000; i++){
linkedList.remove(0);
}이렇게 반복적으로 같은 코드가 호출될 때 JVM은 이 코드가 "자주 호출되는 HotSpot 코드"라고 인지함.
JVM은 "HotSpot 코드"를 확인하면, 이 부분을 즉시 컴파일해 더 빠른 기계어 코드로 변환한다.
즉, 아래와 같은 과정이 수행
- 불필요한 메서드 호출이 있다면 인라인화(inlining):
- 호출을 메서드 내부로 끌어와 메서드 호출 자체를 없애버림
- 반복 호출되는 코드가 동일한 결과를 내면 미리 결과를 계산 (루프 간소화 등)
최적화 전 (느림):
remove(0) 호출 → node(0) 호출 → 매번 메서드 호출 오버헤드 → 첫번째 노드 삭제최적화 후 (빠름):
remove(0) 호출 → (node(0) 호출이 사라지고 첫 번째 노드 삭제 코드가 바로 삽입됨)즉 Hospot이라고 인식한 반복문의 remove 코드를 위와같이 최적화한다.
결론
실제로 유의미하게 큰 속도 차이는 없고, 내부의JVM동작방식의 차이 때문이라고 생각된다.
굳이 최적화하자면, 적은 데이터를 마지막에 넣을 때는 LinkedList를 많은 데이터라면, ArrayList를 사용하고,
맨앞의 데이터를 삭제를 많이 할 때는 LinkedList를 사용하는 것이 이득이다.
