자료구조

자료구조(Data structure)는 컴퓨터가 데이터를 저장하고 조직하며, 필요한 연산을 수행할 수 있도록 데이터 사이의 관계와 접근 방식을 구성한 표현 체계이다. 넓은 의미에서는 하나의 정수와 그 연산도 자료구조로 볼 수 있지만, 일반적으로는 여러 데이터 항목을 일정한 규칙에 따라 배치하고 관리하는 구조를 가리킨다.^[1]

자료구조는 데이터가 메모리에 놓이는 형태만을 뜻하지 않는다. 어떤 값을 저장할 수 있는지, 값 사이에 어떤 관계가 존재하는지, 삽입·삭제·탐색·순회와 같은 연산을 어떤 규칙으로 제공하는지도 자료구조의 일부이다. 같은 데이터 집합이라도 배열, 연결 리스트, 균형 탐색 트리, 해시 테이블과 같이 서로 다른 구조로 표현할 수 있으며, 선택한 구조에 따라 연산의 시간 복잡도와 공간 사용량, 데이터 배치 방식이 달라진다.

자료구조와 추상 자료형은 서로 밀접하지만 구분되는 개념이다. 추상 자료형은 외부에서 사용할 수 있는 값과 연산의 의미를 정의하는 논리적 모델이고, 자료구조는 그 모델을 프로그램과 메모리 위에 실현하는 구체적인 표현 방식이다. 예를 들어 스택은 마지막에 삽입한 값을 먼저 꺼내는 연산 규칙을 가진 추상 자료형이며, 배열이나 연결 리스트를 사용하여 구현할 수 있다. 이러한 구분을 통해 프로그램은 인터페이스에 의존하면서 내부 구현을 목적에 맞게 교체할 수 있다.^[2]

자료구조의 선택은 데이터의 크기와 형태뿐 아니라 자주 수행되는 연산, 요구되는 순서, 중복 허용 여부, 메모리 제약, 동시 접근, 저장장치의 특성에 따라 달라진다. 빠른 임의 접근이 중요하면 배열이 적합할 수 있고, 우선순위가 가장 높은 값을 반복해서 선택해야 한다면 힙을 이용한 우선순위 큐를 사용할 수 있다. 키를 통한 빠른 조회에는 해시 테이블이 널리 사용되며, 정렬된 순서와 범위 탐색이 필요하면 균형 탐색 트리가 유리할 수 있다. 따라서 모든 상황에 가장 적합한 하나의 자료구조가 존재하는 것이 아니라, 필요한 연산과 비용 사이의 균형에 따라 구조를 선택한다.^[3]

자료구조는 알고리즘과 분리해서 다루기 어렵다. 알고리즘은 자료구조가 제공하는 연산을 이용해 문제를 해결하며, 자료구조는 특정 알고리즘이 효율적으로 동작할 수 있는 데이터 표현을 제공한다. 정렬, 탐색, 그래프 순회, 최단 경로 계산, 문자열 검색과 같은 알고리즘의 실제 성능은 입력 데이터의 표현과 자료구조의 선택에 크게 영향을 받는다. 자료구조와 알고리즘의 비용은 일반적으로 입력 크기에 따른 시간 복잡도와 공간 복잡도를 이용해 분석한다.^[4]

현대의 자료구조는 주기억장치 안에서 동작하는 배열과 연결 구조에 한정되지 않는다. 데이터베이스와 파일 시스템은 블록 단위 입출력에 맞춘 B-트리 계열 구조를 사용하며, 분산 시스템은 여러 장치에 데이터를 배치하기 위한 분산 해시 구조와 로그 기반 구조를 사용한다. 병렬 프로그램에서는 여러 실행 흐름이 동시에 접근할 수 있는 동시성 자료구조가 필요하고, 대규모 데이터 처리에서는 캐시 지역성, 메모리 계층, 압축 표현과 외부 메모리 접근 비용도 구조 설계의 핵심 요소가 된다.