연속형 자료구조
연속된 자료구조는 모든 원소를 단일 메모리 청크(chunk)에 저장한다.
모든 원소가 단일 메모리 청크에 저장된다. 또한 모든 원소는 같은 크기의 메모리를 사용하기에 시작주소에 sizeof(type)*n을 더하여 특정 원소의 주소를 구할 수 있다. 이를 통해 모든 원소에 곧바로 접근할 수 있으며 데이터 접근 시간은 항상 일정하다. O(1)
연속된 자료구조인 배열의 유형: 정적 배열 vs 동적 배열
배열 유형은 크게 정적 배열(static array)과 동적 배열(dynamic array) 두 가지로 나눌 수 있다. 정적 배열은 선언된 블록이 끝나면 소멸되는 반면, 동적 배열은 프로그래머가 생성할 시점과 해제할 시점을 자유롭게 결정할 수 있다. 두 가지 유형 모두 다양한 연산에서 동일한 성능을 나타낸다.
-
정적 배열
int arr[size];- 스택(stack) 메모리 영역에 할당되기 때문에 함수나 블록을 벗어날 때 자동으로 해제
-
동적 배열 선언
int *arr = (int*)malloc(size*sizeof(int));int *arr = new int[size];- 힙(heap) 영역에 할당되며 사용자가 직접 해제하기 전까지 유지
배열 같은 연속된 자료구조에서 각 원소는 서로 인접하기에 하나의 원소에 접근할 때 그 옆에 있는 원소 몇 개도 함께 캐시(cache)로 가져온다. 그러므로 다시 주변 원소에 접근할 때에는 해당 원소를 캐시에서 가져오게 되며, 이 작업은 매우 빠르게 동작한다. 이러한 속성을 캐시 지역성(공간적 지역성)이라 한다.
어떤 연산의 점근적 시간 복잡도 계산에는 영향을 주지 않지만 실제 동작에서 배열처럼 연속된 원소에 빠르게 접근할 수 있다는 큰 장점이 됨. 배열에서 모든 원소에 순차적으로 접근하는 경우, 첫 번째 원소를 가져온 후 다음 원소는 캐시에서 바로 참조할 수 있으므로 배열은 '캐시 지역성이 좋다'고 할 수 있다.
연결형 자료구조
연결된 자료구조는 노드(node)라고 하는 여러 개의 메모리 청크에 데이터를 저장하며, 이 경우 서로 다른 메모리 위치에 데이터가 저장된다.
위 그림과 같이 구성된 자료구조를 연결 리스트(linked list)라고 한다. 연결 리스트의 기본 구조에서 각각의 노드는 저장할 데이터와 다음 노드를 가리키는 포인터를 가지고 있다. 맨 마지막 노드에서는 다음 노드의 포인터 대신 자료구조의 끝을 나타내는 NULL(널)을 가진다.
연결 리스트에서 특정 원소에 접근하려면 리스트의 시작 부분, 즉 헤드(head) 부분부터 시작하여 원하는 원소에 도달할 때까지 포인터를 따라 이동해야 한다. 그러므로 i번째 원소에 접근하려면 연결 리스트 내부를 i번 이동하는 작업이 필요하다. 그러므로 원소 접근 시간은 노드 갯수에 비례하며, 시간 복잡도로 표현하면 O(n)이다.
배열과 달리 연결 리스트의 장점은 포인터를 이용하여 원소의 삽입 또는 삭제를 매우 빠르게 수행할 수 있다.
반면 연속된 자료구조와 달리 원소가 메모리에 연속적으로 저장되지 않기에 캐시 지역성을 기대할 수 없다. 따라서 배열과 연결 리스트에서 모든 원소를 차례대로 방문하는 작업은 이론적으로 같은 시간 복잡도를 가지지만, 실제로는 연결 리스트의 성능이 조금 떨어진다. 또한 각 노드에 포인터 저장을 위해 여분의 메모리를 사용한다는 점도 메모리에 대한 요구가 보다 크다는 것을 알 수 있다.
연속형, 연결형 STL 자료구조와 C 스타일 배열의 제약 사항
C++ STL은 std::array, std::vector, std::list와 같은 다양한 연속형, 연결형 자료구조를 제공한다. 이러한 STL 제공 자료구조를 적극적으로 사용하는 것이 권장되는데, 그 이유는 일반적인 C 스타일의 배열에는 몇가지 제약이 있기 때문이다.
1. 메모리 누수(memory leak)
동적 배열을 선언하고, 사용할 때 메모리 할당과 해제를 수동으로 처리해야 한다. 메모리를 해제하지 못하면 메모리 누수(memory leak)이 발생할 수 있고, 이 경우 해당 메모리 영역을 사용할 수 없다.
2. 배열의 범위를 넘어서 접근하는 경우
[] 연산자에서 배열 크기보다 큰 원소를 참조하는 것은 검사하지 못한다. 잘못 사용하면 세크멘테이션 폴트(segmentation fault) 또는 메모리 손상으로 이어질 수 있다. 만약 런타일 에러가 발생하지 않고, 의도치 않은 공간에 접근하여 데이터를 쓰거나 읽는 경우, 더 큰 문제가 발생할 수 있다.
std::array의 at() 멤버함수
std::array의[]연산자는 빠른 동작을 위해 전달된 인덱스 값이 배열의 크기보다 작은지 검사하지 않음.
하지만at(index)형식의 함수를 제공하여 index값이 유효한지 확인한다. index값이 유효하지 않으면 std::out_of_range 예외(exception)를 발생시킨다.
3. 기타
그 밖에 배열을 중첩해서 사용할 경우 가독성이 떨어지는 문제도 있고, 깊은 복사(deep copy)가 기본적으로 동작하지 않아 수동으로 구현해야 한다는 불편성도 있다.
cf) 메모리 누수(Memory Leak)
reference: https://www.kernelpanic.kr/33, https://inspecting.tistory.com/30
메모리 누수는 프로그램이 불필요한 메모리를 계속 점유하는 현상.
힙 영역에 할당된 메모리를 해제하지 않아서 발생함. C언어에서는 힙 영역에 동적 메모리를 할당함. 그런데 힙 영역에 할당된 메모리는 함수호출이 종료되어도 해제되지 않음.
free() 등을 이용해서 사용이 완료된 메모리를 명시적으로 해제해야 한다. 만일 해제되지 않으면 메모리 누수(memory leak)이 발생한다.
동적 메모리 공간을 할당받고, 파일 읽기(by fread 함수)에 실패하면 메모리 할당 해제의 과정없이 바로 NULL을 리턴하면서 함수를 빠져나간다. 이러한 경우에 메모리 누수가 발생한다.
또 다른 예시는 아래와 같다.
bar 포인터 변수에 foo가 가리키는 주소를 대입하면 기존에 bar가 가리키는 공간에 접근할 방법이 사라진다. 이러한 경우에도 메모리 누수가 발생하는 것이다.
cf) 얕은 복사 vs 깊은 복사
- 얕은 복사: 실제 데이터가 아닌 주소를 복사하는 것
- 깊은 복사: 별도의 메모리 공간에 데이터를 복사하는 것
