ArrayList

자바의 List 인터페이스를 상속받은 여러 클래스 중 하나
일반 배열과 동일하게 연속된 메모리 공간을 사용하며 인덱스는 0부터 시작합니다.

• 배열과의 차이점은 배열이 크기가 고정인 반면 ArrayList는 크기가 가변적으로 변합니다.
• 내부적으로 저장이 가능한 메모리 용량이 있으며 현재 사용중인 공간의 크기가 있습니다.
• 만약 현재 가용량 이상을 저장하려고 할 때 더 큰 공간의 메모리를 새롭게 할당

get/set

배열의 index를 통해 접근하는 방식이기 때문에, random access 속도가 빠르며 get/set 메소드는 상수 시간을 가지게 된다.

add

ArrayList는 배열이기 때문에 중간에 값을 끼워넣는 연산이 불가능하다.
만약 새로운 값을 추가하려고 할 때, List의 크기가 생성되어 있는 배열의 size(생성시 따로 설정하지 않았다면 size = 10인 배열이 생성된다)보다 커지게 되면, 이전 크기의 2배가 되는 배열을 생성해 배열 전체를 복사하여 새로운 배열에 복사하고 제일 뒤에 값을 추가해야 한다.
따라서 기존에 있던 배열에서 추가하고 싶은 index부터 마지막 index까지 한 칸씩 뒤로 미루는 연산이 필요하다.
따라서, 해당하는 인덱스를 찾아가는 시간(O(1)) + 배열을 복사하는 시간(O(n)) = O(n)의 시간이 소요된다.

remove

add와 유사하게 remove는 삭제된 index + 1부터 마지막 index까지 한 칸씩 앞으로 당기는 연산을 하게 된다.
따라서, add와 동일한 O(n)의 시간 복잡도를 가지게 된다

시간복잡도

이번에 알고리즘을 문제를 풀어보면서 스택 관련한 문제를 ArrayList를 통해 반복으로 코드를 구현했지만 내가 생각했을 때의 시간복잡도를 훨씬 넘겨 효율성이 떨어졌는데, ArrayList의 Remove에 대한 내용에서의 O(n)을 몰랐었다. 따라서 이번 기회에 ArrayList에 대해 더 잘 알 수 있는 기회를 가질 수 있었기에 다행이고 꼭 숙지해야될 것 같다.

자료 출처 : https://psychoria.tistory.com/765, https://girawhale.tistory.com/8