응용 프로그램에서 필요한 기능을 구현하고, 동작 성능과 안정성을 확보하려면
적절한 자료 구조를 선택하는 것이 중요하다.
자료구조는 크게 연속된 자료 구조와 연결된 자료 구조로 구분할 수 있다.
연속된 자료구조
연속된 자료 구조(contiguous data structure)는 모든 원소를 단일 메모리 청크(chucnk)에 저장한다.
메모리 청크: 하나의 연속된 메모리 덩어리
BA = 시작주소
sizeof(type) = 원소 하나에 필요한 메모리 크기
바깥쪽 큰 사각형은 모든 원소가 저장되어 있는 단일 메모리 청크를 나타내고, 안쪽 작은 사각형들은 각각의 원소가 저장된 메모리 공간을 의미한다. 이 그림에서 모두 같은 타입(type)을 사용하고 있으니 즉, 모두 같은 크기의 메모리를 사용한다. 이는 sizeof(type)으로 표시된다.
첫 번째 원소의 메모리 주소를 시작주소(Base Address)라고 한다. 모든 원소가 같은 타입이기 때문에 i번째 원소의 위치는 BA+i*sizeof(type)라는 수식이 성립된다.
위의 수식을 이용하면 배열의 크기와 상관없이 모든 원소에 곧바로 접근할 수 있다. 따라서 데이터 접근 시간은 항상 일정하다. 이러한 경우를 빅오 표기법으로 나타내면 O(1)로 표시한다.
배열의 유형은 정적 배열(static array)과 동적 배열(dynamic array) 두 가지로 나눌 수 있다.
정적 배열: 스택(stack) 메모리 영역에 할당되기 되어 함수를 벗어날 때 자동으로 해제된다.
int arr[size]; //정적 배열의 선언동적 배열: 힙(heap) 영역에 할당되어 프로그래머가 생성할 시점과 해제할 시점을 자유롭게 결정할 수 있다.
int* arr = (int*)malloc(size*sizeof(int)); //C style 선언
int* arr = new int[size]; //C++ style 선언두 유형의 배열은 연산에서 동일한 성능을 나타낸다.
이러한 배열은 C 언어에 도입되었기 때문에 C 스타일 배열이라고 한다.
배열과 같은 연속된 자료 구조에서는 각 원소는 서로 인접해 있기 때문에 하나의 원소에 접근할 때 그 옆에 있는 원소 몇 개도 함께 캐시(cache)로 가져온다. 그러므로 다시 주변 원소에 접근할 때는 해당 원소를 캐시에서 가져오게 되며, 이 작업은 굉장히 효율적으로 동작한다. 이러한 속성은 캐시 지역성(cache locality)이라고 한다. 연산의 점근적 시간 복잡도(asymptotic time complexity)계산에는 영향을 주지 않지만 실제 동작에서는 연속된 원소에 빠르게 접근한다는 장점이 있다.
연결된 자료 구조
연결된 자료 구조는 노드(node)라고 하는 여러 개의 메모리 청크에 데이터를 저장하며, 서로 다른 메모리 위치에 데이터가 저장된다.
이와 같은 형태로 구성된 자료 구조는 연결 리스트(linked list)라고 한다.
기본 구조에서 각각의 노드는 저장할 데이터(data)와 다음 노드를 가리키는 포인터(next)를 가지고 있다. 맨 마지막 노드에서는 포인터 대신 자료 구조의 끝을 나타내는 NULL을 가진다.
연결 리스트에서 특정 원소에 접근하려면 리스트의 시작 부분인 헤드(head) 부분부터 시작하여 원하는 원소에 도달할 때까지 포인터를 따라 이동해야한다. 그러므로 i번째 원소에 접근하려면 i번 이동하는 작업이 필요하다. 즉, 원소 접근 시간은 노드 개수에 비례하며, 시간 복잡도는 O(n)이다.
연결 리스트는 포인터를 이용하여 원소의 삽입과 삭제를 빠르게 수행할 수 있다.
새로운 원소를 삽입하려면 새 노드를 생성하고 각 노드의 포인터를 수정하면 된다. 새로 추가한 노드(i=2)의 포인터는 다음 노드(i=3)을 가리키고 이전 노드(i=1)의 포인터가 원래 가리키던 것(i=3)을 제거하고 새로운 노드(i=2)를 가리키도록 설정한다.
마찬가지로 기조의 원소를 제거하려면 삭제할 원소가 연결 리스트에 연결되어 있지 않도록 포인터를 수정하면 된다. 이후 해당 노드의 메모리 할당을 해제하거나 또다른 적절한 처리를 할 수 있다.
연결 리스트는 원소들이 연속적으로 저장되어있지 않기 때문에 캐시 지역성을 기대할 수 없다. 그러므로 연결 리스트는 다음 노드 직접 방문하지 않고 다음 원소를 캐시로 가져올 방법은 없다. 따라서 배열과 연결리스트에서 모든 원소를 차례대로 방문하는 작업은 이론적으로 같은 시간 복잡도를 가지지만 실제로는 연결 리스트는 성능이 조금 떨어진다.
다양한 연산에 대한 배열과 연결 리스트의 시간 복잡도
| 파라미터 | 배열 | 연결 리스트 |
| 임의 접근 | O(1) | O(n) |
| 맨 뒤의 원소 삽입 | O(1) | O(1) |
| 중간에 원소 삽입 | O(n) | O(1) |
| 캐시 지역성 | 있음 | 없음 |
'코딩테스트를 위한 자료 구조와 알고리즘 with C++' 카테고리의 다른 글
| 1장 리스트, 스택, 큐 - std::vector (0) | 2021.08.23 |
|---|---|
| 1장 리스트, 스택, 큐 - std::array (0) | 2021.07.23 |