[파이썬(python) 자료구조] 배열 / 연결리스트

1. (정적)배열

: 연속된, 정해진 크기의 메모리 공간을 할당. 같은 타입의 원소만을 담을 수 있음. (정해진 크기의 메모리 공간을 할당하고, 이를 원소 타입, 원소 개수에 맞춰서 분할하기 때문)

또한 한 번 생성한 배열은 크기 변경이 불가능하다.

배열의 장점은 어느 위치에나 O(1)에 조회가 가능하다는 점이다. (배열 시작 주소 + 원소 타입에 따른 바이트 크기 * 원소 인덱스)로 해당 배열 원소 값의 주소 계산 및 메모리 접근이 가능하기 때문. (배열 원소 개수에 독립적)

그러나, 원소의 삭제나 삽입 등의 작업은 최악의 경우 O(n)의 시간복잡도를 갖는다. 예를 들어 원소의 가장 첫번째 원소를 삭제한다고 가정하면 나머지 모든 원소를 하나씩 override해야 하기 때문에 (당겨와야 하기 때문에) n-1개만큼의 작업을 수행해줘야 한다.

 

배열 메모리 구조

 

배열은 큐 구현에 사용되는 자료형이다.

 

2. 동적배열

  실제로 정적 배열을 활용하기엔 비효율이 초래되는 경우가 많다. 따라서 크기를 사전에 지정하지 않고 자동으로 조정할 수 있도록 하는 동적 배열의 필요성이 대두되었다.

ex) C++의 std::vector, Python의 List

파이썬에서는 아예 정적 배열을 지원하지 않고 동적 배열만을 지원한다.

 

- 동적 배열의 구현

 미리 초기값을 작게 잡아 배열을 생성하고, 데이터가 추가되면서 배열이 꽉 채워지게 되면 큰 사이즈의 배열을 새로운 메모리 공간에 할당하고 기존 데이터를 모두 복사한다. (time complexity: O(n))

배열의 사이즈 증가는 대부분 2배씩 이루어진다. (Doubling) 파이썬의 doubling 구조를 보면 아래와 같다.

 

// cpython/Objects/listobject.c
// The growth pattern is: 0,4,8,16,25,35,46,58,72,88...
new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3: 6);

 

주석을 보면 growth pattern은 0,4,8,16,25,35,... 이다. 처음은 2배씩 증가하지만 점점 감소하는 걸 볼 수 있다. 이러한 재할당 비율은 growth factor (성장 인자) 라고 하며, 파이썬의 growth factor는 전체적으로는 1.125로 다른 언어에 비해서는 다소 조금만 늘려가는 형태이다. (C++의 경우는 2배, java의 경우는 1.5배)

 

동적 배열 메모리 구조

 

그림을 보면, 크기와 용량도 같이 저장되어 있는 걸 볼 수 있음. (pythonList 구조체 같이 정의를 해놓았을 듯)

더블링을 해야할 만큼 공간이 차게 되는 경우, 위에서 말했던 것처럼 O(n)의 비용이 발생하게 된다. 그러나 이는 최악의 경우 O(n)이 된다는 것이고, 이는 자주 일어나는 일이 아니므로 "분할 상환 분석"에 따른 입력 시간은 여전히 O(1)이다.

 

3. 연결리스트

  연결리스트는 배열과 달리 물리 메모리를 연속적으로 사용할 필요가 없다. 따라서 동적으로 새로운 노드를 삽입 및 삭제하는 것이 간편하다. 데이터를 구조체로 묶어서 포인터로 연결하는 개념으로 구현된다. (연속된 메모리 공간에 할당되는 것이 아니므로 메모리 내에 scattered되어 있다고 보면 됨)

 

연결리스트 메모리 구조

연결리스트는 원소가 메모리 공간에 연속적으로 존재하지 않으므로 특정 인덱스(원소)에 접근하기 위해서는 전체를 순서대로 읽어야 함. 즉 배열 원소 개수에 dependent이므로 O(1)에 값 조회가 불가능하고, O(n)에 조회가 가능하다. 반면, 연결리스트의 시작 또는 끝 지점에 아이템을 추가하거나 삭제, 추출하는 작업은 O(1)에 가능하다. (그냥 포인터만 바꿔주면 되기 때문) 연결리스트는 스택 구현에 쓰이는 자료형이다.