자바 - 컬렉션 프레임워크 - List
자바 리스트 성능 비교
직접 만든 배열 리스트와 연결 리스트 성능 비교 표
앞에 추가 및 삭제
O(n) - 2371ms
O(1) - 3ms
평균 추가 및 삭제
O(n) - 1129ms
O(n) - 1358ms
뒤에 추가 및 삭제
O(1) - 2ms
O(n) - 2797ms
인덱스 조회
O(1) - 1ms
O(n) - 평균 389ms
검색
O(n) - 평균 338ms
O(n) - 평균 606ms
자바가 제공하는 배열 리스트와 연결 리스트 성능 비교 표
앞에 추가 및 삭제
O(n) - 110ms
O(1) - 4ms
평균 추가 및 삭제
O(n) - 50ms
O(n) - 1414ms
뒤에 추가 및 삭제
O(1) - 2ms
O(n) - 2ms
인덱스 조회
O(1) - 1ms
O(n) - 평균 436ms
검색
O(n) - 평균 214ms
O(n) - 평균 585ms
추가, 삭제
배열 리스트 : 인덱스를 통해 추가나 삭제할 위치를
O(1)로 빠르게 찾지만, 추가나 삭제 이후에 데이터를 한칸씩 밀어야 하므로 이 부분이O(n)으로 오래 걸린다.연결 리스트 : 인덱스를 통해 추가나 삭제할 위치를
O(n)으로 느리게 찾지만, 실제 데이터의 추가는 간단한 참조 변경으로 빠르게O(1)로 수행된다.
앞에 추가 및 삭제
배열 리스트 : 추가나 삭제할 위치를 찾는데
O(1), 데이터를 한칸씩 이동O(n)=>O(n)연결 리스트 : 추가나 삭제할 위치를 찾는데
O(1), 노드를 변경하는데O(1)=>O(1)
평균 추가 및 삭제
배열 리스트 : 추가나 삭제할 위치를 찾는데
O(1), 인덱스 이후의 데이터를 한칸씩 이동O(n/2)=>O(n)연결 리스트 : 추가나 삭제할 위치를 찾는데
O(n/2), 노드를 변경하는데O(1)=>O(n)
뒤에 추가 및 삭제
배열 리스트 : 추가나 삭제할 위치를 찾는데
O(1), 이동할 데이터 없음 =>O(1)연결 리스트 : 추가나 삭제할 위치를 찾는데
O(1), 노드를 변경하는데O(1)=>O(1)자바가 제공하는 연결 리스트는 마지막 위치를 가지고 있다.
인덱스 조회
배열 리스트 : 배열에 인덱스를 사용해서 값을
O(1)로 찾을 수 있음연결 리스트 : 노드를 인덱스 수 만큼 이동해야 함
O(n)
검색
배열 리스트 : 데이터를 찾을 때 까지 배열을 순회
O(n)연결 리스트 : 데이터를 찾을 때 까지 노드를 순회
O(n)
데이터를 추가할 때 ArrayList가 MyArrayList보다 빠른 이유
자바의 배열 리스트는 메모리 고속 복사를 사용하기 때문에 성능이 최적화된다.
메모리 고속 복사는 시스템에 따라 성능이 다르기 때문에 정확한 계산은 어렵지만 대략
O(n/10)정도이다.(상수를 제거하면O(n))하지만 메모리 고속 복사라도 데이터가 아주 많으면 느려진다.
시간 복잡도와 실제 성능
이론적으로 연결 리스트의 평균 추가(중간 삽입) 연산은 배열 리스트보다 빠를 수 있다. 그러나 실제 성능은 요소의 순차적 접근 속도, 메모리 할당 및 해제 비용, CPU 캐시 활용도 등 다양한 요소에 의해 영향을 받는다.
배열 리스트는 요소들이 메모리 상에서 연속적으로 위치하여 CPU 캐시 효율이 좋고, 메모리 접근 속도가 빠르다.
반면 연결 리스트는 각 요소가 별도의 객체로 존재하고 다음 요소의 참조를 저장하기 때문에 CPU 캐시 효율이 떨어지고, 메모리 접근 속도가 상대적으로 느릴 수 있다.
배열 리스트의 경우
CAPACITY를 넘어서면 배열을 다시 만들고 복사하는 과정이 추가되지만, 한번에 1.5배씩 늘어나기 때문에 이 과정은 가끔 발생하므로 전체 성능에 큰 영향을 주지는 않는다.
즉 이론적으로는 연결 리스트가 평균 추가(중간 삽입)에 있어 더 효율적일 수 있지만, 현대 컴퓨터 시스템의 메모리 접근 패턴, CPU 캐시 최적화, 메모리 고속 복사 등을 고려할 때 배열 리스트가 실제 사용 환경에서 더 나은 성능을 보여주는 경우가 많다.
배열 리스트 vs 연결 리스트
대부분의 경우 배열 리스트가 성능상 유리하다.(이런 이유로 실무에서는 주로 배열 리스트를 기본으로 사용)
데이터를 앞쪽에서 추가하거나 삭제하는 일이 압도적으로 많다면 연결 리스트를 고려해보자.
Last updated