순차적(선형) 자료구조 - 배열 또는 리스트

순차적 자료구조는 활용도가 굉장히 높으므로 완벽히 이해하고 있어야 하는 자료구조입니다. 요소가 순차적으로 배열되어 있어 선형(Linear) 자료구조라고 부르기도 합니다. 배열(array) 또는 리스트(list)는 가장 기본적이고 순차적인(sequential) 자료구조입니다. 메모리에 요소 값이 순서대로 들어가기 때문에 인덱스만 알면 해당 값을 한 번에 탐색이 가능합니다.

 

순차적 자료구조의 종류

- 배열(Array) 또는 리스트(List)

- 스택(Stack)

- 큐(Queue)

- 데크(Dequeue)

- 연결 리스트(Linked List)

 

배열(정적 배열)

파이썬은 정적 배열을 지원하지 않기 때문에 C언어로 정적 배열에 대해 알아보려고 합니다. C 언어에서 배열을 생성하려면 배열의 요소 타입과 배열의 크기를 선언해야 합니다. 이때 타입은 모든 요소가 같은 타입이 여야 하고, 배열의 크기를 한 번 지정하면 변경이 불가능한 정적 배열입니다. 만약, 선언한 배열의 크기보다 많은 데이터를 삽입해야 하는 경우 현재 배열보다 크기가 더 큰 새로운 배열을 생성한 뒤, 요소 값을 옮겨주어야 합니다(시간 복잡도 O(N)).

int A[4] = {2, 4, 0, 5};

위 코드를 실행하면 메모리에는 아래와 같이 요소들이 올라갑니다.

메모리에 올라간 배열

C 언어에서 int는 4바이트로 만약 A[0]의 메모리 주소가 100이라면 A[2]의 메모리 주소는 108이 됩니다. 만약 인덱스 N의 값을 확인하고 싶으면 어떻게 할까요? 

A[N]의 주소 = A[0]의 주소 + N * 4 bytes

이렇게 빠르게 해당 배열의 인덱스 번째 주소를 파악할 수 있는 것이 배열의 가장 큰 장점입니다.

A[2] = A[2] + 1

 

A[2] = A[2] + 1 연산 후, 메모리

배열은 위 코드처럼 쓰기, 대입, 읽기, 산술 연산을 지원합니다. 즉, 모두 기본 연산으로 O(1)이라는 아주 짧은 시간이 걸립니다. 다만, 배열은 고정된 크기를 가지고 이를 변경할 수 없기 때문에 크기가 변하는 삽입, 삭제를 할 때는 시간 비용이 커집니다. 삽입을 할 때, 배열의 크기가 충분하고 배열의 끝에 삽입하는 경우 O(1) 시간을 가지지만, 여유 공간이 없거나 배열의 중간에 삽입하는 경우 O(N) 시간을 가집니다. 삭제할 때는, 삭제할 원소가 끝에 있을 경우 O(1) 시간을 가지지만, 삭제한 원소보다 큰 인덱스를 앞으로 한 칸씩 옮겨야 하기 때문에 O(N) 시간을 가집니다.

 

리스트(동적 배열)

실제 데이터는 전체 크기를 가늠하기 힘들 때가 많습니다. 그래서 정적 배열을 사용하면 실제 필요한 공간보다 적게, 혹은 많게 할당받아 공간이 부족하거나 낭비될 수 있습니다. 이러한 문제 때문에 데이터 양에 따라 자동으로 공간을 조정해주는 배열이 등장합니다. 그것이 동적 배열입니다.

파이썬은 배열을 보통 리스트로 구현합니다. array로도 배열을 구현할 수 있지만, 배열의 요소 값이 변하지 않고, 수학적인 연산이 많이 있을 때와 같은 특별한 경우에만 사용됩니다. (사실, 그 특별한 경우에도 array 대신 numpy가 사용됩니다.) array의 경우 다른 언어의 배열과 같이 동일한 타입의 요소만 가질 수 있지만, list는 요소의 타입이 다르더라도 상관없습니다.

어쨌든, 파이썬의 array와 list 모두 크기를 변경할 수 있는 동적 배열입니다.

A = [2, 4, 0, 5]

리스트의 타입에 제한이 없기 때문에 따로 타입을 선언하지 않고 리스트를 생성할 수 있습니다. 위 코드를 실행하면 아래와 같이 메모리에 리스트가 올라갑니다.

메모리에 올라간 리스트

리스트는 메모리에 값을 저장하는 배열과 다르게 '값의 주소'를 저장합니다. 값은 객체가 되어 메모리의 다른 공간에 생성됩니다. 

A[2] = A[2] + 1

A[2] = A[2] + 1 연산 후, 메모리

위 연산을 수행하면 A[2]의 값이 바뀌는 것이 아니라, 0의 주소를 가리키고 있던 연결을 끊어버리고 '객체 1'의 주소를 저장합니다.

파이썬의 리스트는 아래와 같은 다양한 연산을 제공합니다.

- A.append(value) : 리스트의 끝에 value을 삽입

- A.pop(index) : A[n]을 제거하고 리턴.

- A.insert(index, value) : A[index]에 value를 삽입

- A.remove(value) : A에서 value 제거

- A.index(value) : A의 요소중 값이 value인 index를 리턴

- A.count(value) : A의 요소중 값이 value인 요소 개수 리턴

동적 배열의 동작 방식

파이썬에서 리스트의 경우 처음에는 메모리를 작게 할당하여 생성합니다. 그리고 데이터를 추가하다 공간이 다 채워지면 새로운 공간에 더 큰 크기의 배열을 할당하고 기존 데이터를 복사하는 작업을 수행합니다. 더 큰 크기의 배열을 생성할 때 얼마나 '더 큰 크기'의 배열을 생성할까요?

파이썬은 오픈소스입니다. 이곳을 보시면 파이썬이 배열을 리사이징하는 코드를 볼 수 있습니다. 저처럼 C 언어로 작성된 코드를 이해하기 어려운 분들은 주석을 살펴보면 코드에 대한 설명이 잘 정리되어 있습니다. 아래는 주석의 일부분을 가져와봤습니다. (소스코드를 보기 힘드신 분들은 여기를 보시면 보다 자세히 정리되어 있습니다.)

* The growth pattern is: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...
* Note: new_allocated won't overflow because the largest possible value is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.

처음에는 기존 배열의 크기에서 두 배 가량 커지다가 이후에는 9/8 = 1.125배로 커집니다. 몇 배로 배열의 크기가 리사이징 되는지는 언어마다 상이합니다. 자바의 경우 1.5배, C++의 경우 2배씩 커집니다.

어쨌든 배열이 리사이징되면서 기존의 배열의 값들을 복사하는 O(N)의 비용이 발생합니다. 하지만 이 경우는 최악의 경우로 자주 일어나지 않기 때문에 데이터를 삽입하는 경우 O(1)이 걸린다고 봐도 무방합니다. 정적 배열 또한 공간이 다 채워지면 새로운 배열을 할당하여 기존 데이터를 복사하는 과정을 수행하지만, 차이점은 정적 배열은 개발자가 직접 새로운 배열을 생성해야 하고, 동적 배열의 경우 자동으로 수행해줍니다.