ArrayList는 배열과 똑같이 선형 리스트의 구조로 되어 있어
특정 인덱스 접근에 O(1), 삽입, 삭제에 O(N) 이지만
동적으로 배열크기를 늘려 미리 크기를 지정하지 않아도 되는 특징이 있는 자료구조다.
그렇다면 동적으로 배열크기를 어떻게 관리하나?
처음 Arraylist 객체를 만들면
특정 크기 만큼 메모리를 선형적으로 만들어 놓고 사용하다가
들어가는 데이터의 갯수가 처음 크기보다 커지면
크기가 더 큰 배열을 만들어
기존 배열 데이터들을 복사해 붙이는 방식으로 동적으로 크기를 키운다.
이 때 크기를 키우는 작업에 O(N)의 시간이 들게 되는데
실제론 크기를 변화시키는 상황이 자주 일어나지 않도록 내부적으로 구현이 잘되어 크게 신경쓰지 않아도 된다.