[Java] ArrayList와 LinkedList의 요소 순회 시 성능 차이

출시

ChatGPT

---

1. ArrayList

데이터 구조

ArrayList는 내부적으로 동적 배열을 사용하여 요소를 저장한다. 이 배열은 연속적인 메모리 블록에 요소를 저장한다.

요소 순회

• 성능: 요소를 순회할 때 ArrayList는 내부 배열의 인덱스를 통해 직접 접근할 수 있다. 이로 인해 인덱스를 사용한 순회는 매우 빠르다. 요소를 순회할 때의 시간 복잡도는 O(n)이며, 각 요소에 대한 접근은 O(1)이다.
• 장점: 연속적인 메모리 블록 덕분에 캐시 지역성을 활용할 수 있어, 메모리 접근이 빠르다. 이로 인해 CPU 캐시 효율이 높아지며, 순회 성능이 우수하다.

• 관련 글 -> [프로그래밍 개념] 캐시 지역성 + ArrayList와 관계

단점

배열의 크기를 조정할 때 (예: 요소 추가 시) 새로운 배열을 생성하고 기존 배열의 내용을 복사하는 작업이 필요하다. 그러나 순회할 때는 이러한 비용이 없다.

 

2. LinkedList

데이터 구조

LinkedList는 노드 기반의 데이터 구조를 사용한다. 각 노드는 데이터와 다음 노드(그리고 때로는 이전 노드에 대한 참조)를 포함한다.

요소 순회

성능

LinkedList에서 요소를 순회할 때, 첫 번째 노드부터 시작하여 각 노드를 따라가며 순회한다. 이 작업은 O(n) 시간 복잡도를 가지며, 각 노드 접근은 O(1)이다. 그러나 각 노드 접근 시 포인터를 따라가야 하기 때문에, 메모리 접근의 지역성이 떨어져 캐시 효율이 낮을 수 있다.

장점

삽입과 삭제 작업이 O(1) 시간 복잡도를 가지며, 특히 리스트의 중간에서 작업할 때 유리다.

단점

순회 중에 노드의 링크를 따라가야 하므로 메모리 접근이 비연속적이다. 이로 인해 CPU 캐시의 지역성이 낮아지고, 순회 성능이 떨어질 수 있다.

 

성능 비교 요약

순회 속도

ArrayList가 LinkedList보다 순회 속도가 일반적으로 빠르다. 이는 ArrayList가 연속적인 메모리 블록을 사용하고, 인덱스를 통한 직접 접근이 가능하기 때문이다.

메모리 접근

ArrayList는 캐시 지역성을 활용할 수 있어 CPU 캐시 효율이 높다. 반면 LinkedList는 비연속적인 메모리 접근 때문에 캐시 효율이 낮다.

 

결론

 

• ArrayList는 요소를 순회할 때 성능이 더 우수하며, 읽기 작업이 빠르다. 따라서, 요소를 자주 읽고, 순회가 많은 경우에 적합하다.
• LinkedList는 삽입과 삭제가 빈번하게 일어나는 경우에 더 적합하다. 하지만 요소를 순회할 때는 성능이 떨어질 수 있다.

따라서, 애플리케이션의 요구 사항에 따라 적절한 리스트 구현체를 선택하는 것이 중요하다.