| ArrayList | LinkedList | |
|---|---|---|
| 구현 | 배열 | 노드끼리 연결 |
| 데이터 접근 시간 | 모든 데이터 상수 시간 접근 | 위치 따라 다른 접근 시간 |
| 삽입/삭제 시간 | 삽입/삭제 자체는 상수 시간. 다만, 데이터 시프트가 필요한 경우 추가 시간 필요 | 삽입/삭제 자체는 상수 시간. 다만, 위치에 따라 그 위치 까지 이동하는 시간 발생 |
| 리스트 크기 확장 | 배열 확장 필요할 경우 새로운 배열 만들고 복사하는 시간 발생 | |
| 검색 | 최악의 경우 리스트에 있는 아이템 수 만큼 확인 | 최악의 경우 리스트에 있는 아이템 수 만큼 확인 |
| CPU Cache | CPU Cache 이점 활용 가능 |
| 배열 | 연결리스트 | |
|---|---|---|
| 메모리 공간 | 연속 | 불연속 |
| 삽입, 삭제(맨 끝, 맨 앞 제외) | O(n) | O(1) |
| n번째 요소 참조 | O(1) | O(n) |
| 탐색 | O(n) | O(n) |
- 데이터 추가, 삭제 많이하는건 연결리스트
- 참조를 많이 하는 것은 배열