ArrayList

 

 

자바는 배열 생성시 고정된 배열 size를 입력해주어야 하지만

ArrayList 클래스를 사용하면 데이터를 추가할 때 자동으로 사이즈가 늘어난다

 

그러나 ArrayList의 입력 시간은 배열과 마찬가지로 O(1)이다

(검색은 정렬된 경우엔 O(log n), 정렬되지 않은 경우엔 O(n)이 걸린다)

입력할 때는 어차피 배열 사이즈가 고정되어 있기 때문이다

 

ArrayList는 배열이 다 차면 두 배 큰 크기의 새로운 배열을 선언하고

기존 배열의 데이터를 모두 옮겨오는 Doubling 작업을 하는데,

이 과정에서 n이 자꾸 두배로 늘어나기 때문에 입력값이 n을 따라갈 수 없다

(컬렉션 프레임워크가 도입되면서 증가율이 달라졌다고 함... 50%?)

 

더블링 작업에 걸리지 않은 데이터를 입력하는데 n만큼의 시간이 걸렸다 하더라도

2n은 n으로 표기하기 때문에 어쨌든 모든 데이터를 입력하는데 최대 n만큼의 시간이 걸린다

 

따라서 하나의 값을 입력할 땐 O(1)이 된다!

 

그러나 더블링 과정이 상당히 효율이 떨어지므로 처음 인스턴스를 생성할 때,

저장할 데이터의 개수를 고려하여 충분한 용량의 인스턴스를 생성하는 것이 좋다고 한다

 

자세한 메서드명과 설명은 자바의 정석 584 참고하기