배열리스트 vs 연결리스트 성능 비교

ArrayList vs LinkedList

앞에 삽입, 삭제

배열 리스트 O(n) - 뒤로 공간 하나씩 땡겨야함

연결 리스트 O(1) - 앞에 노드 하나 만들면 됨

 

중간 삽입, 삭제

배열 리스트 O(n) - 중간부터 뒤에 공간 땡겨야함

연결 리스트 O(n) - 중간까지 노트 타고 가야함

 

끝에 삽입, 삭제

배열 리스트 O(1) - 바로 추가하면됨

연결 리스트 O(1) - 바로 추가하면됨

 

인덱스로 조회

배열 리스트 O(1) - 메모리 주소 복사해서 바로 감

연결 리스트 O(n) - 노드를 인덱스 수 만큼 이동

 

숫자로 조회

배열 리스트 O(n) - 배열 숫자나올때 까지 순회

연결 리스트 O(n) - 노드 숫자나올때 까지 순회

 

배열 리스트가 앞에 삽입,삭제 빼고 연결 리스트를 압승함.

 

같은 O(n)이라도 연결 리스트는 노드가 메모리 상에 흩어져있어 운영체제 레벨의 메모리 관리, 캐시 히트율 안 좋음, 배열 리스트의 메모리 고속 복사 기능 등의 이유로 연결 리스트가 더 빠름

이론 상으로는 연결 리스트가 배열 리스트보다 중간 삽입,삭제가 빠를 수 있는데 실제 성능은 위와 같은 이유로 대부분의 상황에서 배열 리스트가 더 빠름

숫자로 조회도 같은 O(n)이지만 일반적으로 배열 리스트가 더 빠름

연결 리스트는 인덱스 조회랑 숫자로 조회가 속도 큰 차이가 안 남. 인덱스 조회가 10% 정도 더 빠른 듯 10초랑 11초 차이