ArrayList는 기본적인 제네릭타입을 받아서 일자로 붙어있는 리스트를 만드는 형태이다.
이때 처음 초기화를 할 떄 크기를 설정하도록 되어있는데
이 크기 이상으로 값을 추가한다면 어떻게 되는지 갑자기 의문이 생겼다.
결론부터 말하자면 ArrayList는 grow()라는 함수를 구현하고 있다. 자세한건 아래에서 설명하도록 한다.
ArrayList 직접 구현해보기
그래서 ArrayList를 내가 직접 구현해보기로 했다.
ArrayList이든 LinkedList이든 List이기 때문에 기능 자체는 동일하다고 생각했기에 인터페이스로 먼저 List를 만들었다.
public interface List <E>{
public void clear();
public void insert(int pos, E item);
public void append(E item);
public void update(int pos ,E item);
public E getValue(int pos);
public int length();
public void remove(int pos);
}인터페이스를 구현하는 ArrayList의 필드로 size와 직접적인 리스트가 되어줄 무언가 총 두가지가 필요하다고 생각했다.
public class Arraylist <E> implements List <E> {
int listSize;
E[] data;
Arraylist(int capacity){
listSize = 0;
data = (E[])new Object[capacity];
}
어떤 타입이 올 수 있도록 제네릭 타입으로 구현했고
처음 생성을 할때 List사이즈를 초기화하고 배열 형태로 리스트를 구성했다.
List 내 값을 추가하거나 중간에 삽입할때를 고민하기 시작했고
아무래도 처음 사이즈를 준 것에서 새로운 배열을 생성하고 해당 배열안에 원래 배열의 값을 옮기면 크기가 증가할 것으로 예상했다.
@Override
public void add(E e) {
if(size == data.length)
makeDouble();
data[size] = e;
size++;
}
private void makeDouble(){
E [] list2 = (E[]) new Object[data.length*2];
System.arraycopy(data, 0, list2, 0, data.length);
data = list2;
}기존 배열의 두배크기로 배열을 새로 생성한 뒤
새로운 배열 내 기존 배열을 깊은 복사하도록 했다.
그리고 기존 배열이 새로운 배열의 주소값을 가리키도록 하면 증가된 형태가 될 것으로 예상했다.
디버깅 해보니 정상적으로 배열이 두배 증가했다.
ArrayList 내부 코드 살펴보기
원래 자바에서 제공하는 ArrayList를 살펴보니 코드는 다음과 같았다 .
코드를 찬찬히 살펴보면 기존 용량의 비트연산자 1번 줄인만큼의 크기와 기존 용량을 더한양으로 증가시킨다 .
다시말해 1.5배 크기를 증가시키는 것으로 보인다.
시간 복잡도는 ?
처음에 무지성으로 ArrayList에 add의 시간복잡도는 o(1)이라고 암기했었다.
그런데 이렇게 grow 또는 뭔가 증가 시키는 조치가 있는데도...
왜 o(1)일까를 곰곰히 생각해 보게 되었다.
왜냐하면 grow를 할때 배열을 새롭게 복사하는 과정에서 O(n) 만큼 시간이 걸린다고 생각했기 때문이다.
이럴때 천천히 내부에서 어떻게 동작하는지를 생각해보면 된다.
처음에 10개만큼 크기가 주어진다고 가정하자 .
10번의 O(1)
1번의 O(N)
5번의 O(1)
1번의 O(N)
...
이전 크기에 1.5배에 해당하는 만큼 O(1)이 존재한다음 O(N)이 나온다.
즉 O(1) 의 갯수가 O(N) 갯수보다 N*(1.5) 배 만큼 많이 존재하는데 이것을 평균내면 O(1)에 가까운것이다.
이를 어려운 용어로 분할 상환분석 이라고 한다.
복잡할 것 없이 ..!
O(N) 보다 O(1)의 갯수가 월등히 많기 때문에 평균적으로 O(1) 만큼 시간이 걸린다.
결론
ArrayList에서 add의 시간복잡도는 O(1)이다.
