ArrayList - 배열을 이용한 동적인 컬렉션

1. 배열로 보는 리스트 생성

ArrayList(이하 리스트)는 자바에서 배열을 기초로 만들어진 동적 배열이다.

리스트를 처음 선언할 때, 외부적으로는 사이즈가 0으로 보이지만, 실제로는 10개의 요소를 담을 수 있는 배열 공간을 내부적으로 할당받는다.

즉, 내부적으로 [0,0,0,0,0,0,0,0,0,0] 형태의 배열을 가지고 시작한다.

ArrayList<Object>  = new ArrayList<>(); // -> 내부 배열생성 [0,0,0,0,0,0,0,0,0,0]

 

 

사용자는 필요에 따라 아래와 같이 초기 배열의 크기를 조절 할 수 있다.

ArrayList<Object>  = new ArrayList<>(3); // -> 내부 배열생성 [0,0,0]

 

2. 리스트의 크기가 가변적일 수 있는 이유

 

리스트는 내부 배열의 크기를 넘어서는 요소들을 추가할 때,

현재 배열 크기의 1.5에서 2배에 해당하는 새로운 배열을 생성하고 기존의 값들을 이로 복사하여 옮긴다.

 

이 과정을 통해 리스트는 필요에 따라 그 크기가 유동적으로 변할 수 있다.

arrayList.add(6)

[1,2,3,4,5] -> [1,2,3,4,5,6,0,0,0,0]

 

3. 리스트의 삭제 - 리스트의 크기는 자동으로 줄어들지 않는다.

리스트는 배열 기반이지만, 고정 크기 배열과 달리 특정 인덱스의 값을 제거하는 기능을 제공한다.

 

예를 들어, {1,2,3,4,5}의 리스트에서 3을 제거하면, 내부적으로는 [1,2,4,5,0,0,0,0,0,0]로 업데이트되며,

리스트의 값들은 {1,2,4,5}로 변경된다.

 

이러한 삭제 연산은 제거한 값의 뒤에 존재하는 인덱스 값들을 앞으로 옮겨야 한다.

따라서, 배열의 크기 N에 비례하는 시간이 소요되므로 시간 복잡도는 O(N)이다.

 

리스트는 값을 추가 할 때에는 자동으로 그 크기가 늘어나지만, 값을 제거한다고 해서 리스트의 내부적 배열 크기가 줄어들지는 않는다.

배열 크기를 줄이기 위해서는 아래 메서드를 사용하여 리스트의 현재 크기에 맞는 새로운 배열을 생성하고 값을 이동시킬 수 있다.

arayList.trimToSize() // 내부 배열의 크기를 리스트의 사이즈에 맞춘다.

[1,2,3,4,5,0,0,0,0,0] -> [1,2,3,4,5]