1-1. 연속된 자료 구조와 연결된 자료구조

왜 자료구조와 알고리즘을 공부해야 할까?

응용 프로그램을 설계할 때 가장 중요하게 고려해야 할 항목 중에 하나는 데이터 관리이다. 

프로그래머는 데이터를 메모리에 저장하기 위해 여러 자료 구조를 사용할 수 있다. 

응용 프로그램에서 필요한 기능을 구현하고, 동작 성능과 안정성을 확보하려면 적절한 '자료구조'를 선택하는 것이 매우 중요하다. 

적절한 자료구조를 선택하는 것뿐만 아니라, 데이터 조작에 적합한 알고리즘을 선택하는 것 또한 최적의 응용 프로그램 동작을 위해 필수적이다. 

 

연속된 자료 구조와 연결된 자료구조

서론

응용 프로그램에서 데이터를 처리하기에 앞서, 데이터를 어떻게 저장할 것인가를 결정해야 한다 .

이 질문에 대한 답은 데이터를 이용하여 수행할 작업의 종류와 작업 빈도에 따라 달라진다. 

응용 프로그램이 제대로 동작해야 한다는 점은 기본이고, 동시에 지연 시간, 사용 메모리 또는 기타 매개변수 측면에서 최선의 성능을 제공하도록 구현방법을 선택해야 한다. 

 

어떠한 자료구조를 선택할 것인가를 결정함에 있어 적합한 지표로, 알고리즘 복잡도 또는 시간 복잡도(time complexity)가 있다. 

시간 복잡도는 특정 작업을 수행하는 데 걸리는 시간을 데이터 크기에 대한 수식으로 표현하는 방식이다. 

따라서 시간 복잡도는 데이터 크기가 변경되면 연산 시간이 어떻게 변하는지 보여준다 

 

연속된 자료구조

연속된 자료구조(contiguous data structures)는 모든 원소를 단일 메모리 청크(chunk)에 저장한다.  - 메모리 청크는 하나의 연속된 메모리 덩어리를 의미한다. 

모든 원소는 같은 크기의 메모리를 사용하고, 이는 sizeof(type)으로 표시된다. 

첫 번째 원소의 메모리 주소를 시작 주소(BA, Base Address)라고 한다. 

모든 원소가 같은 타입이기 때문에 두 번째 원소의 위치는 BA+sizeof(type)이고, 이를 통해 i번째 원소에 접근하려면 BA+i*sizeof(type)수식을 사용한다. 

 

이러한 자료 구조에서는 배열의 전체 크기와 상관없이 앞서 설명한 수식을 이용하여 모든 원소에 곧바로 접근할 수 있다. 

따라서 데이터 접근 시간은 항상 일정하다. 

이러한 경우를 빅오(Big-O) 표기법으로 나타내면 O(1)로 표시한다. 

 

배열의 유형은 크게 정적 배열(static array)과 동적 배열(dynamic array) 두 가지로 나눌 수 있다. 

정적 배열은 선언된 블록이 끝나면 소멸되는 반면, 동적 배열은 프로그래머가 생성할 시점과 해제할 시점을 자유롭게 결정할 수 있다. 

두 가지 유형 모두 다양한 연산에서 동일한 성능을 나타낸다. 

이러한 배열은 C 언어에서 도입되었기 때문에 C 스타일 배열이라고도 한다. 

실제로 배열을 선언하는 방법은 다음과 같다. 

 

정적 배열은 int arr[size]; 형태로 선언한다
C에서 동적 배열은 int* arr = (int*)malloc(size * sizeof(int)); 형태로 선언한다
C++에서 동적 배열은 int * arr = new int[size]; 형태로 선언한다

정적 배열은 스택(stack) 메모리 영역에 할당되기 때문에 함수를 벗어날 때 자동으로 해제된다. 

반면에 동적 배열은 힙(heap) 영역에 할당되며 사용자가 직접 해제하기 전 까지 유지된다. 

 

배열 같은 연속된 자료 구조에서 각 원소는 서로 인접해 있기 때문에 하나의 원소에 접근할 때 그 옆에 있는 원소 몇 개도 함께 캐시(cache)로 가져온다. 

그러므로 다시 주변 원소에 접근할 때에는 해당 원소를 캐시에서 가져오게 되며, 이 작업은 매우 빠르게 동작한다. 

이러한 속성을 캐시 지역성(cache locality)라고 한다. 

어떤 연산의 점근적 시간 복잡도(asymptotic time complexity) 계산에는 영향을 주지 않지만 실제 동작에서 배열처럼 연속된 원소에 매우 빠르게 접근할 수 있다는 점은 큰 장점이 된다. 

 

 

연결된 자료 구조

연결된 자료 구조(linked data structures)는 노드(node)라고 하는 여러 개의 메모리 청크에 데이터를 저장하며, 이 경우 서로 다른 메모리 위치에 데이터가 저장된다. 

 

연결 리스트의 기본 구조에서 각각의 노드는 저장할 데이터(data)와 다음 노드를 가리키는 포인터(next)를 가지고 있다. 

맨 마지막 노드에서는 다음 노드의 포인터 대신 자료 구조의 끝을 나타내는 NULL을 가진다. 

 

연결 리스트에서 특정 원소에 접근하려면 리스트의 시작 부분, 즉 헤드(head) 부분부터 시작하여 원하는 원소에 도달할 때까지 next 포인터를 따라 이동해야 한다. 그러므로 i번째 원소에 접근하려면 연결 리스트 내부를 i번 이동하는 작업이 필요하다. 

그러므로 원소 접근 시간은 노드 개수에 비례하며, 시간 복잡도로 표현하면 O(n)이다. 

 

배열과 달리 연결 리스트는 포인터를 이용하여 원소의 삽입 또는 삭제를 매우 빠르게 수행할 수 있다. 

 

<연결 리스트에 새 원소 추가하기>

1. 새로운 노드를 생성
2. 새로 추가한 노드(i=2)의 next 포인터가 다음 노드(i=3)를 가리키게 만든다
3. 이전 노드(i=1)의 next 포인터가 다음 노드(i=3)를 가리키던 것을 제거하고, 새로운 노드(i=2)를 가리키도록 설정한다.

 기존 원소를 제거하기 위해서는 삭제할 원소가 더 이상 연결 리스트에 연결되어 있지 않도록 next 포인터를 수정하면 된다. 그런 다음 해당 노드의 메모리 할당을 해제하거나 적절한 처리를 수행할 수 있다. 

 

연결 리스트에서는 원소가 메모리에 연속적으로 저장되지 않기 때문에 캐시 지역성을 기대할 수 없다. 

즉, 현재 노드가 가리키는 다음 노드에 직접 방문하지 않고 다음 원소를 캐시로 가져올 수 있는 방법은 없다. 

따라서 배열과 연결 리스트에서 모든 원소를 차례대로 방문하는 작업은 이론적으로 같은 시간 복잡도를 가지지만, 실제로는 연결 리스트의 성능이 조금 떨어진다. 

 

비교

연속된 자료 구조와 연결된 자료 구조의 비교

연속된 자료 구조	연결된 자료 구조
모든 데이터가 메모리에 연속적으로 저장됨	데이터는 노드에 저장되고, 노드는 메모리 곳곳에 흩어져 있을 수 있다
임의 원소에 즉각적으로 접근	임의 원소에 접근하는 것은 선형 시간 복잡도를 가지며 느린편이다
캐시 지역성 효과로 모든 데이터를 순회하는 것이 매우 빠름	캐시 지역성 효과가 없으므로 모든 데이터를 순회하는 것이 느린 편이다
데이터 저장을 위해 정확하게 데이터 크기만큼의 메모리를 사용	각 노드에서 포인터 저장을 위해 여분의 메모리를 사용한다.

 

다양한 연산에 대한 배열과 연결 리스트의 시간 복잡도

파라미터	배열	연결 리스트
임의접근	O(1)	O(n)
맨 뒤에 원소 삽입	O(1)	O(1)
중간에 원소 삽입	O(n)	O(1)
캐시 지역성	있음	없음

 

배열과 리스트는 매우 범용적이며 많은 응용 프로그램에서 데이터를 저장하는 용도로 사용되고 있다. 

그러므로 이들 자료 구조의 구현은 버그가 없어야 하며, 최대한 효율적으로 동작해야 한다. 

사용자가 직접 이들 자료 구조를 구현하지 않아도 되도록 C++는 std::array, std::vector, std::list와 같은 자료구조 클래스를 제공한다. 

 

 

C 스타일 배열의 제약 사항

C스타일 배열은 배열의 역할을 충분히 수행하지만 그다지 많이 사용되지는 않는다. 

C스타일 배열은 몇 가지 제약사항을 가지고 있어, 더 나은 형태의 배열이 필요하기도 하다. 

 

C스타일 배열의 단점

• 메모리 할당과 해제를 수동으로 처리해야 한다. 메모리를 해제하지 못하면 메모리 릭(memory leak)이 발생할 수 있고, 이 경우 해당 메모리 영역을 사용할 수 없다
• [ ] 연산자에서 배열 크기보다 큰 원소를 참조하는 것을 검사하지 못한다. 잘못 사용하면 segmentation fault 혹은 메모리 손상으로 이어질 수 있다
• 배열을 중첩해서 사용할 경우, 문법이 너무 복잡해서 코드를 이해하기 어렵다. 
• 깊은 복사(deep copy)가 기본으로 동작하지 않는다. 이러한 동작은 수동으로 구현해야 한다. 

위와 같은 문제점을 회피할 수 있도록 C++는 C스타일 배열을 대체하는 std::array를 제공한다.