ArrayList와 가변 배열

 

 특정 언어에선 배열(이 경우엔 종종 리스트라 불리지만)의 크기를 자동으로 조절할 수 있습니다.

즉, 데이터를 덧붙일 때마다 배열 혹은 리스트의 크기가 증가한다.

하지만 자바 같은 언어에서는 배열의 길이가 고정되어 있다.

이런 경우에는 배열을 만들 때 배열의 크기를 함께 지정해야 한다.

 

동적 가변 크기 기능이 내재되어

특정 언어에선 배열(이 경우엔 종종 리스트라 불리지만)의 크기를 자동으로 조절할 수 있습니다.

 

즉, 데이터를 덧붙일 때마다 배열 혹은 리스트의 크기가 증가한다.

하지만 자바 같은 언어에서는 배열의 길이가 고정되어 있다.

이런 경우에는 배열을 만들 때 배열의 크기를 함께 지정해야 한다. 

 

 동적 가변 크기 기능이 내재되어 있는 배열과 비슷한 자료구조를 원할 때는 보통 ArrayList를 사용한다.

ArrayList는 필요에 따라 크기를 변화시킬 수 있으면서도 O(1)의 접근 시간을 유지한다.

통상적으로 배열이 가득 차는 순간, 배열의 크기를 두 배로 늘린다.

크기를 두 배 늘리는 시간은 O(n)이지만,

자주 발생하는 일이 아니라서 상환 입력 시간으로 계산했을 때 여전히 O(1)이 된다.

 

ArrayList merge(String[] wirds, String[] more) {
	ArrayList sentence = new ArrayList();
    for (String w : words) sentence.add(w);
    for (String w : more) sentence.add(w);
    return sentence;
}

 

이 자료구조를 잘 하는 것은 면접에서 필수적이다.

사용하는 언어에 관계없이 동적 가변 크기 배열 / 리스트 에 대해서 익숙해져 있어야 한다.

하지만 자료구조 이름이나 배열 크기 조절 인자 (자바에선 2)는 달라질 수 있음을 명심하자.

 

상환 입력 시간은 왜 O(1)이 되는가

 

크기가 N인 배열을 생각해 보자.

이 배열의 크기를 늘릴 때마다 얼마나 많은 원소를 복사해야 하는지 역으로 계산해 볼 수 있다.

배열의 크기를 K로 늘리면 그 전 배열의 크기는 K의 절반이었을 것이므로 K/2만큼의 원소를 복사해야 한다.

 

따라서 N개의 원소를 삽입하기 위해서 복사해야 하는 원소의 총 개수는

N/2 + N/4 + N/8 + ... + 2 + 1, 즉 N보다 작다.

 

 위 수열의 합이 뻔해 보이지 않는다면 다음과 같은 상황을 상상해 보자.

1Km 떨어져 있는 상점에 걸어가려고 한다.

0.5km를 걷고 난 뒤, 0.25km를 걷고, 다음에는 0.125km를 걷는다.

이렇게 길이를 반씩 줄이는 행위를 무한정으로 하더라도

1km에 아주 가까워질 수는 있지만 1km이상 걸을 수 없다.

 

 따라서 N개의 원소를 삽입할 때 소요되는 작업은 O(N)이 된다.

배열의 상황에 따라 최악의 경우 O(N)이 소요되는 삽입 연산도 존재하긴 하지만

평균적으로 각 삽입은 O(1)이 소요된다.