Python List 내부 뜯어보기

array와 linked list를 공부하다 보니 내가 자주 사용하는 python의 list는 어떤 방식으로 구현되어 있을까?라는 궁금증이 생겼다.

 

array는 각 요소의 메모리 크기가 고정되어 있어 1개의 타입만 저장이 가능한데

python list는 아래와 같이 서로 다른 타입의 요소가 저장될 수 있다는 특징이 있는 것도 이해가 가지 않았다.

sample = [1, "샘플", 1.5]

 

그래서 나는 python list는 linked list 방식을 사용하나?라고 생각했지만

아무리 생각해도 조회가 빈번하게 일어나는 배열 특성상 조회 성능을 포기하면서 linked list를 사용하진 않았을 거란 생각이 들었다.

 

그래서 위 궁금증을 해결하기 위해 array와 비교하여 python list의 동작 방식을 살펴보게 되었다.

---

1.  Array 의 동작 방식

python list는 array에 기반하고 있기 때문에 일단 먼저 Array의 기초 개념부터 이해해야 한다.

array는 아래와 같은 특징을 가지고 있다.

 

1. 각 요소는 동일한 메모리 크기를 차지 -> 동일한 타입만 저장 가능

2. 각 요소들은 메모리상 순차적으로 저장됨

3. 배열을 선언할 때 배열의 길이를 고정 ( 고정된 메모리 차지 )

 

위 특징 때문에 array는 특정 인덱스 요소에 접근하려는 O(1)의 시간복잡도로 굉장히 빠르게 접근이 가능하다.

그 방법은 array는 첫 번째 요소의 메모리 주소를 알고 있다가 특정 인덱스 요소에 접근할 경우

순차적으로 해당 배열 요소를 탐색하는 것이 아닌 메모리 주소를 계산하여 접근이 가능하기 때문이다.

예를 들어, 각 요소의 메모리 크기가 8 bytes인 배열 example이 있고 아래와 같이 각 요소들이 저장되어 있다고 가정한다.

 

그럼 example은 첫 번째 요소의 메모리 주소인 0x0을 알고 있으므로

만약 example[3]에 접근하려 하면 첫 번째 메모리 주소 + 인덱스 x 요소당 메모리 크기로 계산할 수 있다.

즉, 0x0 + 3 * 8이 example[3]의 메모리 주소가 된다.

 

1-2. 동적 배열 (Dynamic Array)

그리고 3번째 특징을 보면 배열의 메모리 크기를 고정하기 위해 배열을 처음 선언할 때 배열 길이를 고정하게 되는데

이 때문에 고정된 배열 길이보다 더 많은 요소를 넣어야 하는 상황에서 이슈가 발생한다.

array에서는 배열 길이 고정 이슈를 해결하기 위해  동적 배열이라는 것을 사용한다.

 

동적 배열은 배열이 가득 찼을 경우 resize를 해서 추가 메모리 공간을 확보하는 배열이다.

resize 방법은 다양하지만 가장 쉽고 이해하기 편하게 현재 배열 크기의 2배만큼 확장하는 더블링(Doubling) 방식이 있다.

---

2. Python List의 동작 방식

Python list에서도 array의 개념이 똑같이 적용되지만 조금 다르게 적용된다.

 

먼저 Python list에서 요소를 저장하는 방법부터 살펴보면

array에서 요소의 값을 저장하는 방식 대신 각 요소가 저장된 메모리 주소를 가리키는 포인터 주소를 저장한다.

글로 이해하긴 어려우니 먼저 그림으로 살펴보면 아래와 같다

각 요소는 본인의 데이터 타입의 메모리 크기만큼 차지해 메모리 특정 위치에 저장되고

python list는 해당 메모리 주소를 저장하고 있는 것을 볼 수 있다.

위의 특징 때문에 각 list 내의 서로 다른 타입이 존재할 수 있으며 해당 값을 가리키는 메모리 주소의 크기는 항상 동일하기 때문에

조회를 할 때 메모리 주소를 array와 똑같이 계산하여 O(1)의 시간복잡도를 가지는 장점까지 그대로 가져갈 수 있다.

 

다음으로 list가 가득 찬 경우 python list도 동적 배열과 마찬가지로 resize를 수행한다.

이를 간단히 python 코드로 구현해 보면 아래와 같다.

def append(self, item):
    if self.length == self.capacity:
        self._resize(self.capacity*2)
    self.array[self.length] = item
    self.length += 1

def _resize(self, new_cap):
    new_arr = (new_cap * ctypes.py_object)()
    for idx in range(self.length):
        new_arr[idx] = self.array[idx]
    self.array = new_arr
    self.capacity = new_cap

 

list가 resize 되는 경우 시간복잡도를 살펴보면

list 확장 시 기존 list의 모든 요소들을 확장된 list로 옮기는 과정이 있기 때문에 O(n)이 걸린다.

그럼 실제로 append는 배열의 요소가 가득 차지 않았을 경우에는 O(1)이고 가득 차서 확장이 필요한 경우에는 O(n)의 시간이 소요된다.