[자료구조] 순차적 자료구조, 배열과 리스트의 이해

목표

대표적인 순차적 자료구조인 배열과 리스트에 대해서 자세히 알아보도록 하겠습니다.

 

목차                                                                           클릭하면 해당 목차로 이동합니다.

순차적 자료구조(Sequential Data Structure)

 

C언어: 배열(Array)

 

Pythoon: 리스트(List)

 

정리

 

개요

이전 포스팅에서 시간 복잡도와 BIG-O 표기법에 대해서 알아보았습니다.

이번 포스팅에서는 순차적 자료구조인 배열과 리스트에 대해서 알아보도록 하겠습니다.

배열과 리스트는 C언어나 파이썬을 이용해서 코딩을 할 때 자주 사용하는 자료구조입니다.

저도 학교에서 과제나 프로젝트를 진행할 때 많이 사용한 자료구조인데요. 특히, 리스트의 경우 많은 연산자가 있어서 유용하게 사용했습니다.

어떤 특징이 있는지 자세히 이해하고 쓰면 더 효율적으로 사용할 수 있을 것이라고 기대합니다.

 

순차적 자료구조(Sequential Data Structure)

순차적인 자료구조(Sequential Data Structure)란, 데이터(값)들이 순차적으로 메모리에 저장되어 있는 구조를 뜻합니다.

저장된 곳의 주소(Address, Reference)를 통해 빠르게 접근할 수 있습니다.

 

대표적으로 다음 3가지를 예시로 들 수 있습니다.

1. 배열 & 리스트

- index를 통해 임의의 원소에 접근

[ ] 연산자 제공, 삽입·삭제 연산 제공

2. 스택(Stack), 큐(Queue), 디큐(Dequeue)

-제한된 접근(삽입·삭제)만 허용, 다음과 같은 구조를 가짐.

스택 : LIFO (Last In First Out) → 제일 나중에 들어온 데이터가 먼저 나감.

큐    : FIFO (First In First Out)  → 제일 먼저 들어온 데이터가 먼저 나감.

디큐 : 스택 + 큐 → 제일 먼저 들어온 데이터가 나갈 수도, 제일 나중에 들어온 데이터가 나갈 수도 있음.

3. 연결 리스트(Linked List)

- 데이터들이 메모리에 연속되지 않게 독립적으로 저장되어 있다. 각 데이터들은 다음 데이터의 주소를 갖고 있다.

자기 값과 다음 주소를 알고 있는 형태이다. 인덱스로 접근 할 수 없고 처음부터 계속 찾아가야 한다.

 

이번 포스팅에서는 배열과 리스트를 중심으로 설명하도록 하겠습니다.

 

C언어: 배열(Array)

배열은 C언어를 포함한 C++, Java와 같은 많은 언어에서 지원하는 자료구조입니다.

여기서는 C언어의 배열을 보면서 자세하게 설명하겠습니다.

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

위와 같이 크기가 4인 정수형 배열을 선언하고 값을 넣었습니다.

이 배열 A의 시작 주소는 "100"이라고 가정하겠습니다. A[0]의 주소값은 100이겠지요.

정수형 배열이기 때문에 다음 값은 4Byte씩 증가합니다.

만약, 배열의 2번째에 저장된 값을 알고 싶다면 100 + 2*4 로 계산할 수 있습니다. (배열의 시작주소 + 2번째*한칸이 차지하는 Byte수)

 

이게 가능한 이유는 값들이 메모리에 순차적으로 저장되어 있기 때문입니다.

결국, 배열의 시작 주소·저장된 값의 종류(차지하는 Byte수)·몇 번째인지 나타내는 인덱스 이 3가지 정보만 알고 있으면 저장된 곳의 주소를 알 수 있습니다.

 

빠르게 접근할 수 있다고 말씀드렸는데요. 얼마나 빠를까요? 앞에서 배운 BIG-O표기법으로 시간 복잡도를 확인해보겠습니다.

다음과 같이 A[2]의 값에 1을 더하는 코드가 있다고 가정하겠습니다.

A[2] = A[2] + 1

기본 연산이 몇 개나 있을까요? A[2]의 값을 불러와서(읽기) 1을 더한 값을(산술) A[2]에 가져가서(대입) 저장해야(쓰기) 합니다.

총 4번의 기본 연산이 필요합니다. 시간 복잡도에 대한 포스팅을 적을 때, 편의상 읽기·쓰기는 생략했지만 사실은 단위 시간 "1"이 필요합니다.

단위 시간 "1"에 가능한 이유는 알고리즘을 실행하는 환경(가상 머신)이 RAM(Random Access Memory) 구조이기 때문입니다.

 

A[2]에 접근하는 것도 A[0] + 2*4 (시작주소+인덱스*Byte수) 이기 때문에 산술연산 2번이면 가능합니다.

모든 연산이 상수시간에 가능하기 때문에 BIG-O 표기법으로 나타내면 O(1) 입니다.

 

결국, 배열은 인덱스를 통해 특정 위치에 있는 값을 상수시간 내에 읽고 쓸 수 있는 2개의 기본연산을 제공하는 자료구조라고 할 수 있습니다.

 

빠른 시간 내에 접근이 가능한 것이 장점이지만 동시에 읽고 쓰는 것만 지원하는 제한된 자료구조라는 것이 단점입니다.

 

Python: 리스트(List)

반면, 파이썬의 리스트는 유연하고 강력한 연산들을 다양하게 지원한다는 장점이 있습니다.

대신 C언어랑 구조가 다른데요.  다음 예시를 보면서 이해해보겠습니다.

A = [2,4,0,5]

위와 같은 리스트 A가 있습니다. A[0], A[1]과 같이 인덱스로 접근하는 것은 동일합니다.

하지만, 해당 주소값에 값(Value)를 저장하는 게 아닙니다.

해당 주소값에는 배열의 값 "2", "4", "0", "5" 각각의 값이 저장되어 있는 객체를 가리키고 있는 주소값을 갖고 있습니다.

만약, A[2]=A[2]+1 을 하면, A[2]의 값에 +1 하는 게 아니라, 기존에 있던 객체는 냅두고 "1"이라는 값을 갖고 있는 객체를 만들어서 가리키게 됩니다.

▲ 배열과 리스트의 차이점

위 사진은 배열과 리스트의 차이점을 그림으로 나타낸 것입니다.

각 주소값에 값(Value)를 저장해놓은 배열과는 달리, 각 값을 저장하고 있는 객체를 가리키고 있는 리스트를 확인할 수 있습니다. 

 

시간 복잡도는 어떻게 다를까요?

항상 객체의 주소만 저장하기 때문에, 리스트의 각각의 크기를 메모리의 주소를 표현할 수 있는 4Byte 혹은 8Byte로 고정하면 됩니다. 리스트의 각각 인덱스의 크기가 동일하기 때문에 O(1) 시간 접근이 가능합니다.

 

다양한 연산 제공

리스트의 장점은 강력하고 유연한 연산을 다양하게 지원해준다고 말씀드렸습니다.

여러가지 종류가 있지만 대표적으로 몇 가지만 소개하겠습니다.

연산자명	내용
append(value)	리스트의 끝에 value를 추가합니다. ex) A.append(6) → 리스트 A의 맨 끝에 6을 추가
pop()	맨 뒤의 값을 지우고 지운 값을 리턴합니다.
pop(index)	배열의 index번째 값을 제거하고 리턴합니다. ex) A.pop(1) → A[1] 값을 제거하고 오른쪽에서 빈자리를 매꿈
insert(index, value)	index번째에 value를 삽입한다. ex) A.insert(1,10) → A[1]에 10을 삽입한다.
remove(value)	리스트에 존재하는 value를 모두 제거 A.remove(1) → 리스트에 존재하는 값 중 1을 모두 제거
index(value)	맨 처음부터 value가 처음 등장하는 index 리턴 ex) A.index(1) → 1이 처음 나오는 곳의 index를 리턴
count(value)	리스트에 value가 몇 번 나오는지 카운트해서 리턴 ex) A.count(1) → 1이 나오는 만큼 숫자를 세서 리턴
[i:j]	i~j-1까지 복사해서 새로운 리스트를 생성하여 리턴 ex)A[1:10]→A[1]~A[9]까지 잘라서 새로운 리스트 생성 후 리턴
value in A	리스트 A에 value가 있으면 True, 그렇지 않으면 False ex) 10 in A → A안에 10이 있으면 True, 없으면 False

A라는 리스트가 있을 경우 A.append(1) 과 같이 "A.함수" 와 같은 형태로 사용하면 됩니다.

리스트는 클래스로 구성되어 있기 때문에 객체의 멤버함수에 접근하듯 사용하면 됩니다.

 

동적 배열(Dynamic Array)

파이썬의 리스트는 동적 배열이라고도 합니다. 그 이유는 리스트의 크기를 자동으로 조절해주기 때문입니다.

마찬가지로 C언어와 비교하면서 확인해보겠습니다.

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

위와 같은 코드를 실행하면 어떻게 될까요? 당연히 오류가 납니다. 배열 A의 크기는 4인데, 5번째 인덱스에 10을 저장하라고 했으니까요.

이 문제를 해결하려면 다음과 같이 malloc을 이용해서 코딩을 해야합니다.

B = (int*)malloc(5*sizeof(int));
A = B;

위와 같이 메모리에 20Byte의 주소를 할당 받아서 공간을 마련한 후, A에 복사해줘야합니다.

 

반면, 파이썬의 리스트는 크기를 자동으로 조절해줘서 위와 같은 작업이 필요가 없습니다.

정말 조절이 되고 있는지 코드를 통해서 확인해보도록 하겠습니다.

▲ 리스트 크기 확인하는 코드

sys 라이브러리의 getsizeof() 함수는 매개변수로 들어온 리스트의 Byte수를 리턴해줍니다.(C의 sizeof와 동일)

위 코드를 통해서 빈 리스트 일 때 크기와 1을 추가한 뒤 크기를 확인해보겠습니다.

▲ 결과

보시면 56Byte에서 88Byte로 더 늘어난 것을 확인할 수 있습니다. (이 크기는 작업환경에 따라 다릅니다.)

이렇게 리스트는 자동으로 크기를 조절하고 있음을 알 수 있습니다.

만약, insert나 append 연산을 했을때 할당된 메모리의 크기가 모자르다면 자동으로 여유공간을 할당하게 됩니다.

반대로, pop연산을 하면서 리스트의 크기가 줄어든다면 할당된 메모리의 크기가 줄어들게 됩니다.

 

이런 특징 때문에 리스트를 동적 배열(Dynamic Array)라고 부르는 것입니다.

 

자동으로 크기를 조절해주기 위해서는 기본적으로 현재 리스트의 크기(capacity)와 리스트에 저장된 실제 값의 개수(n)을 알고 있어야 합니다.

이를 위한 내부 변수가 필요하기 때문에 빈 리스트는 일정 크기의 메모리가 필요합니다. (위 예시에선 56Byte)

이렇게 크기를 자동으로 조절하는 것은 메모리 크기 뿐만 아니라 연산 시간에도 영향을 미칩니다.

특정 append 연산에서 메모리를 늘려야 한다면 이전 리스트의 값을 새로운 리스트로 일일히 옮겨야 합니다. 그 과정을 확인하면서 연산 시간에 미치는 영향에 대해 알아보겠습니다.

예를 들어, A라는 리스트에 값 X를 append 하는 과정을 확인해보겠습니다. 코드로는 A.append(X)가 되겠네요.

A.append(X):
    if A.n < A.capacity:  #리스트에 X를 추가할 공간이 있는 경우
        A[n] = X
        A.n += 1
    else:                 #리스트에 할당된 메모리 공간이 모자란 경우
        B = A.capacity*2
        for i in range(n):
            B[i] = A[i]
        del A
        A = B
        A[n] = X
        A.n += 1

리스트에 할당된 메모리 공간에 여유가 있어서 X를 추가할 수 있는 경우에는 그냥 A[n]에 X를 추가하면 됩니다.

단순한 산술 연산이 진행되기 때문에 상수 시간에 해결할 수 있습니다. 따라서, 시간 복잡도는 O(1)이 됩니다.

 

반대로, 할당된 공간이 모자란 경우에는 새로운 리스트를 생성해서 메모리를 더 크게 할당해서 일일히 옮겨야 합니다. 이 과정에서 시간 복잡도는 O(n)이 되는 것입니다.

BIG-O 표기법은 최악의 경우를 가정하고 계산하는 것이기 때문에 O(n)이 되지만, 이렇게 메모리 공간이 모자라서 새로 만드는 경우는 가끔 발생하는 것이기 때문에 평균적으로 따지면 걸리는 시간은 O(n)보다는 작습니다.

 

크기를 2배씩 증가하거나 감소하는 경우엔 append, pop 연산 시간은 평균적으로 O(1)인 것을 증명할 수 있습니다. 이 부분은 추후에 hash table에 대해서 배울 때 다루도록 하겠습니다. 

결과적으로 append, pop 연산이 평균적으로 O(1)임을 감안하고 위에서 설명한 함수들의 수행시간을 확인하면 다음과 같습니다.

연산자명	연산 시간
A[i] = A[j] + 1	단위시간 안에 해결 가능하므로 O(1)
A.append()	평균적으로 O(1)
A.pop()	평균적으로 O(1)
A.pop(index)	index번째 값을 제거하면 빈 공간을 메꾸기 위해서 값을 이동해야함 → O(len(A))
A.insert(0,10)	최악의 경우 0부터 len(A)의 값을 모두 오른쪽으로 이동하므로 O(len(A))
A.remove(9)	처음에 등장하는 9를 찾아 제거하고 값을 이동해야하기 때문에 최악의 경우 O(n)
A.index(9)	9가 마지막에 등장할 수 있으니 최악의 경우 O(len(A))
A.count(9)	총 횟수를 계산해야 하므로 O(len(A))

 

리스트는 많은 함수를 제공해주기 때문에 편리하다는 장점이 분명 존재하지만, 위에서 보신 것처럼 실제 저장된 데이터보다 많은 메모리를 차지하고 있다는 단점이 존재합니다. 그래서 메모리에 효율적인 리스트를 사용하고자 한다면 numpy 모듈의 compact array를 사용하면 됩니다!

실제로 numpy의 array는 머신러닝이나 데이터 분석을 할 때 사용했던 기억이 나네요. 이에 대한 내용은 다음에 자세히 다뤄보도록 하겠습니다.

 

 

정리

이번 포스팅에서 순차적 자료구조인 리스트와 배열에 대해서 자세히 알아보았습니다.

리스트는 분명 배열보다 많은 기능을 제공하지만 연산 시간이 느리다는 단점이 존재합니다.

이런 장·단점을 고려해서 사용해야할 필요가 있을 것 같습니다.

평소 사용할 때는 큰 생각 없이 사용하고 있었는데 이런 구조를 갖고 있었다는 것이 신기합니다.

다음 포스팅에서는 스택에 대해서 자세히 다루도록 하겠습니다.

 

*한국외대 신찬수 교수님의 Data Structures with Python 강의를 참고하여 포스팅하였습니다.