자료구조를 C로 하나하나 만들다 보면, 자연스럽게 동적 크기의 리스트도 만들게 된다.
내가 리스트를 구현 할 때는, Linked List를 사용하였고, 특정 인덱스의 값을 얻기 위해서는 다음같은 코드가 필요했다.
int i=0;
for(myList = head;, i<N; i++, myList = myList->next);
printf("%d\n", myList->value);단순 코드지만, 위와 같은 방법으로 만든 get 함수는 시간복잡도가 O(N)이 되게 된다.
같은 동적 리스트 역할을 하는 Java의 ArrayList나 Python의 List의 시간 복잡도를 확인해보자.
Java 기준인데, 명확히 Linked List와 ArrayList는 구분돼있다. 그렇다면 ArrayList는, 우리가 아는 LinkedList로 구현되지 않았다는 뜻이다. 그렇다면 ArrayList는 어떻게 구현되어 있을까?
보통 배열의 인덱스 접근이 O(1)에 이루어진다. 이것이 가능한 이유는 배열에 들어가는 자료형이 동일하고, 선언시에 크기를 지정하여 스택에 연속적인 공간을 할당하기에 가능하다.
ArrayList는 동적으로 원소를 추가하기 때문에,LinkedList를 생각한다면 연속적인 메모리 할당을 보장하기 힘들다고 생각했다.
그 배경에는 "배열"이 있었다. ArrayList는 명백히 배열 기반 자료구조다.
ArrayList 내부에는 Object[] 배열이 존재하고, 이 안에 원소를 저장한다.
배열에 차곡차곡 원소를 넣다가, 배열의 크기가 꽉 차게 된다면 다음 과정을 수행한다.
1. 배열의 크기가 기존의 2배인 배열을 만든다.
2. 새로 만든 배열에 기존 데이터를 복사해 옮긴다
따라서 배열 확장시, K개의 원소가 존재한다면 K개의 데이터를 모두 복사해야 하기 떄문에 지연이 발생한다.
삭제의 경우엔, 중간에 있는 원소를 삭제한다면 그 뒷 원소들을 모두 한칸씩 앞으로 당겨줘야 하므로 지연이 발생한다.
따라서 연속적인 공간을 가지는 배열을 사용하기에 O(1) 시간으로 데이터를 조회할수 있었다.
