자료구조란?

자료구조란 여러 데이터를 논리적인 규칙을 통해 나열하고 이를 효율적으로 처리하기 위한 사용법을 정의한 것입니다.

예를 들어 도서관에는 여러 책이 있습니다. 각각의 책을 이름 순서로 나열할 수도 있지만, 이렇게 된다면 원하는 책을 쉽게 찾는 것이 어렵게 됩니다. 이때 각각의 책들을 주제에 따라 유형을 나누어 분류한다면 조금 더 원하는 책을 쉽게 찾을 수 있습니다. 우리 나라에서는 한국 십진분류법에 따라 10가지 유형으로 나누어 책을 분류하는데, 이것이 자료구조에 해당합니다.

정수형을 나타내는 int 역시 자료구조 입니다. int는 4바이트의 메모리를 할당받으며, 첫 비트는 부호를 표현하고 나머지 공간은 2진수의 정수를 표현합니다. 또한 덧셈, 뺄셈, 나눗셈, 곱셈 등 여러 연산을 정의하고 있습니다.

자료구조는 알고리즘과 밀접한 관련이 있습니다. 알고리즘은 문제 해결을 위한 일련의 절차를 정의한 것입니다. 예를 들어 도서관에서 책을 분류하는 것이 자료구조라면, 원하는 책을 찾는 방법이 알고리즘에 해당합니다.

보통 알고리즘은 자료구조에 의존적이기 때문에 자료구조가 정의된다면 적용할 알고리즘은 명확해집니다. 책의 일련번호가 한국 십진분류법에 따른 자료구조를 가진다면 자연과학에 관련된 책을 찾기 위해서는 400번대의 일련번호를 가진 책을 찾는 알고리즘을 적용하면 됩니다. 이렇듯 효율적인 문제해결을 위해서는 자료구조가 우선 정의되는 것이 중요합니다.

자료구조의 종류

자료구조는 단순 자료구조(Primitive Data Structure)와 복합 자료구조(Non-Primitive Data Structure)로 나눌 수 있습니다.

단순 자료구조는 int, float, character 등 프로그래밍 언어에서 통상적으로 제공되는 기본 데이터 형식입니다.

복합 자료구조는 다시 선형 자료구조(Linear Data Structure)와 비선형 자료구조(Non-Linear Data Structure)로 나눌 수 있습니다.

선형 자료구조에는 배열(Array)과 리스트(List), 스택(Stack), 큐(Queue) 등이 있으며, 비선형 자료구조에는 그래프(Graph), 트리(Tree) 등이 있습니다.

배열(Array)

배열은 동일한 타입의 데이터들을 저장하고 고정된 크기를 가지며, 메모리의 물리적인 순서를 통해 인덱스가 부여됩니다. 배열에 저장된 데이터는 인덱스를 통해 접근할 수 있습니다.

배열은 다른 데이터 구조를 구축하기 위한 블록으로 사용되며, 정렬에 용이하지만 구조를 재구성하는데 어려움이 있습니다.

연결 리스트(Linked List)

연결 리스트는 인덱스가 아닌 참조를 통해 순차적으로 연결되는 구조입니다. 데이터는 노드(Node)라는 단위요소에 저장되며, 각 노드는 데이터를 참조하는 key와 다음 노드를 참조하는 next로 구성되어 있습니다. 또한 첫 번째 요소를 참조하는 head, 마지막 요소를 참조하는 tail이 포함됩니다.

리스트는 데이터의 추가 및 삭제시 구조를 재구성할 필요가 없이 참조만 변경하면 되기 때문에 동적인 메모리 할당에 효율적입니다. 하지만 배열보다 메모리를 더 많이 사용하며, 데이터를 찾기위해 head부터 tail까지 순회하기 때문에 검색에는 비효율적입니다.

스택(Stack)

스택은 배열이나 리스트로 구성되어 순서가 보존되는 선형 데이터 구조이며, 마지막에 입력된 데이터부터 처리하는 후입선출(Last In First Out, LIFO) 메커니즘을 가집니다.

스택은 수학적 표현식을 분석하거나 재귀함수의 호출을 구현하는데 효율적인 구조입니다.

큐(Queue)

큐는 스택과 비슷하지만 먼저 입력된 데이터부터 처리하는 선입선출(First In First Out, FIFO) 메커니즘을 가집니다. 또한 첫 번째 요소를 참조하는 back과, 마지막 요소를 참조하는 front가 포함됩니다.

큐는 앞서 설명했던 CPU 스케줄링이나 캐시(Cache)를 구현하기에 효율적인 구조입니다.

그래프(Graph)

그래프는 노드(node)와 간선(edge)으로 이루어진 집합(collection) 입니다. 각각의 노드는 간선으로 연결되며, 간선은 방향을 가지거나 방향을 가지지 않을 수 있습니다.

그래프는 네트워크나 검색엔진 알고리즘 등 다양한 알고리즘에 응용이 가능한 구조입니다.

트리(Tree)

트리는 일종의 그래프이며, 노드가 계층적인 구조를 가집니다. 최상위 노드는 루트 노드(root node)이며, 상위 노드인 부모 노드(parent node)와 하위 노드인 자식 노드(child node)로 구성됩니다. 같은 부모 노드를 가지는 자식 노드의 집합은 형제 노드(siblings node)가 되며, 자식이 없는 노드는 단말 노드(leaf node)가 됩니다.

트리는 탐색 알고리즘이나 머신러닝 알고리즘에 많이 사용되는 구조입니다.