Array
미리 할당된 크기 내에서 연관된 data를 메모리와 index가 연속적이고 순차적으로 저장하는 자료구조이다.
ArrayList
연관된 data를 메모리와 index가 연속적이고 순차적으로 저장한다는 점에서는 Array와 비슷하지만 미리 할당된 크기보다 더 큰 data가 들어왔을 경우 capacity를 늘린다.
Performance
기본적인 구조가 비슷하기 때문에 두 자료구조가 비슷한 시간 복잡도를 가진다.
| Search | O(n) |
| Append | O(1) |
| Insertion (append가 아닌) | O(n) - 해당 index를 기준으로 뒤에 있는 index의 data를 한칸씩 뒤로 밀어야한다 |
| Delete(맨 끝) | O(1) |
| Delete | O(n) - Insertion 과 같은 이유이다. |
| Access | O(1) |
Append 나 index를 통한 access가 빠르기 때문에 Data 조회가 많이 일어나는 경우 자주 사용된다.
Resize
- 크기가 고정된 Array와는 다르게 ArrayList는 capacity보다 더 큰 data를 저장하려고 할 때 capacity를 늘리게 된다.
- Java를 기준으로 resize가 발생하면 기존 ArrayList의 capacity의 1.5배에 해당하는 새로운 ArrayList 할당 후 기존 데이터를 복사하여 옮긴다.
ArrayList에서 Append를 하다보면 Resize가 일어난다. Resize는 기존 데이터 전체를 복사하여야 하기 때문에 O(n)의 시간복잡도를 가진다. 하지만 Resize는 자주 일어나는 작업은 아니기 때문에 Append의 시간복잡도를 O(n)이라도 하지 않는다. 조금 더 정확하게는 Amortized O(1)이라고 한다.
Reference
추가적으로 java를 기준으로 두 자료구조는 넣을 수 있는 자료형이나 사용방법 면에서 여러 차이를 가진다. 그 차이점에 대해 잘 정리해둔 게시글이 있어서 이에 대한 링크를 남긴다.
https://beginnersbook.com/2018/10/data-structure-array/
https://velog.io/@humblechoi/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Array-vs-ArrayList
https://junghyungil.tistory.com/96
https://stackoverflow.com/questions/71203084/time-complexity-for-arraylist-resizing-java
'자료구조' 카테고리의 다른 글
| [자료 구조] 해시 테이블(Hash Table) (0) | 2023.02.11 |
|---|---|
| [자료구조] 큐(Queue) (0) | 2023.01.26 |
| [자료구조] LinkedList vs ArrayList (0) | 2023.01.21 |
