프로그램이 효율적으로 실행되기 위해서는 최적화된 알고리즘과 이를 구조적으로 지원하는 자료구조가 있어야 합니다. 프로그램이 실행될때 데이터는 메모리에 상주하게 되는데, 이 데이터들을 어떻게 관리할 것 인가에 대한 이론이 자료구조입니다. 우리가 학교 혹은 책에서 배우게 되는 자료구조 (Data Structure)는 여러 종류가 있는데, 그 각각의 다른 특징과 쓰임새가 있습니다. 따라서 각 자료구조의 특성을 잘 이해해야 적절하게 사용할 수가 있어야, 적합한 자료구조가 바탕이 되어 효율적인 알고리즘을 구현할 수 있습니다.

가령 일련의 순서가 있는 동일한 타입의 자료를 관리해야 한다고 할 때와 특정한 번호나 아이디를 가지고 회원의 정보를 검색한다고 할때 사용하는 자료구조는 다를 수 있습니다. 

순서가 있는 자료 구조라 함은 앞과 뒤의 관계가 1:1인 선형(Linear)자료 구조를 이야기 합니다. 선형자료 구조는 리스트라고도 하는데,  배열과 연결리스트를 생각할 수 있습니다. 

정적인 사이즈를 가지고 물리적인 순서와 논리적인 순서가 동일한 배열은 인덱스 연산이 빠른 장점을 가지고 있습니다. 배열의 인덱스 연산은 그 자료의 순서에 따라 위치가 산술적으로 계산가능하기 때문에 수행시간이 상수 O(1)가 됩니다. 즉, 배열에 자료에 수와 상관없이 늘 일정한 계산 속도로 그 위치를 찾을 수 있다는 것이죠. 반면에 중간에 자료가 추가되거나 삭제되면 연속되는 자료의 유지를 위해 나머지 자료들의 이동의 연산이 필요하고 이때는 자료의 개수(n)에 연산의 수가 비례하게 됩니다. O(n)

연결리스트의 경우에는 매번 자료가 추가 될때마다 동적으로 자료 크기 만큼의 메모리를 할당받고 순서를 유지하기위해 앞뒤 자료가 서로 그 주소를 가리키는 링크 정보를 가지게 됩니다. (이를 노드라고 합니다) 배열이 인덱스 연산이 빠른 반면, 연결 리스트의 경우에는 i 번째 자료를 찾기 위해서는 처음 노드부터 i 번째 까지 찾아가야 하기때문에 연산의 속도가 요소의 개수(n)에 비례하게 됩니다. O(n) 대신 중간에 자료를 추가하거나 삭제할때 자료의 이동이 없이 링크의 조정만 처리하면 되므로 연산의 속도가 상수 O(1)가 됩니다.

선형 자료구조 중에 익숙한 스택(stack)과 큐(queue)는 여러 프로그램 개발에 자주 활용되는 자료 구조입니다. 스택과 큐는 배열로 구현할 수도 있고 연결리스트로 구현할 수도 있습니다. 앞에서 살펴본 것처럼 자료의 추가 삭제나 이동이 빈번한 연산이 많은 경우는 연결리스트를 활용하고, 자료의 변경보다는 인덱스 기반의 참조가 많은 경우는 배열을 사용하는것이 효율적입니다. 특히, 배열의 경우는 처음 크기를 고정하여 사용하므로, 중간에 용량(capacity)가 부족한 경우엔 크기가 더 큰 배열을 만들어 요소를 이동해야 합니다. 

스택의 경우는 최근에 입력된 자료를 먼저 꺼내는 자료 구조입니다. 따라서 최근 정보를 참조한다거나, 이전의 상태로 되돌려야 하는 경우 (바둑, 체스) 등에서 활용할 수 있습니다. 큐는 우리 일상생활에서 가장 많이 사용하는 선착순을 생각하시면 됩니다. 가장 먼저 입력된 자료부터 참조하므로 대기열과 같은 구현에 많이 쓰입니다.

검색을 한다고 할때, 해싱(Hashing)을 사용할 수 있습니다. 특정 키(key) 값에 대한 자료를 찾는 기능이 빠른 자료구조입니다. 이때 키는 중복될 수 없습니다. 가장 흔한 예로 사전을 생각해 볼 수 있습니다. 사전에 “사과” 라는 키워드에 대해 검색을 하면 그 뜻(value)은 여러가지 일 수 있지만, “사과” 라는 키 값은 유일하죠.  따라서 해싱을 다른 말로 Dictionary 라는 이름으로 제공하는 언어도 있습니다. 그런데 검색을 위해 저장한 자료에 대해 정렬을 해야 한다면 해싱 보다는 이진검색트리(Binary Search Tree :BST) 를 사용하는 것이 더 유익합니다.

BST도 해싱 처럼 검색을 위한 자료구조입니다. 노드가 가진 키값을 기준으로 왼쪽 서브트리는 더 작은 키 값, 오른쪽 서브트리는 더 큰 키값을 유지하는 자료구조입니다. 균형을 잘 이룬 BST는 검색이나 자료 추가 삭제에 대한 수행시간이 (logN)이 보장되므로 효율적입니다. 또한 BST의 자료를 inorder traverse로 하나씩 참조하면 오름차순으로 정렬이 됩니다. (이 반대도 가능하겠죠)

(해싱과 BST 에 대한 부분은 다음에 또 포스트 하기로 하죠)

이처럼 여러 자료 구조는 그 특성에 따라 쓰임새가 다릅니다. 물론 지금은 여러 라이브러리에서 최적으로 만들어진 자료구조가 제공되므로 직접 구현해서 사용할 일은 없을 수 있지만, 각 자료구조에 대한 이해를 잘 하게 되면 앞으로 만들 프로그램에서 보다 효율적인 처리를 구현할 수 있을 것입니다.