자료 구조

3. 활용

자료 구조는 추상 자료형 (ADT)의 기반이 된다. ADT는 자료형의 논리적 형식을 정의하며, 자료 구조는 자료형의 물리적 형식을 구현한다.^[5]

다양한 종류의 자료 구조는 서로 다른 종류의 응용 프로그램에 적합하며, 일부는 특정 작업에 매우 특화되어 있다. 예를 들어, 관계형 데이터베이스는 일반적으로 데이터 검색을 위해 B-트리 인덱스를 사용하고,^[6] 컴파일러 구현은 일반적으로 해시 테이블을 사용하여 식별자를 찾는다.^[7]

자료 구조는 대용량 데이터베이스 및 인터넷 인덱싱 서비스와 같은 용도로 대량의 데이터를 효율적으로 관리하는 수단을 제공한다. 일반적으로 효율적인 자료 구조는 효율적인 알고리즘을 설계하는 데 핵심이다. 일부 공식 설계 방법론과 프로그래밍 언어는 소프트웨어 설계의 핵심 구성 요소로서 알고리즘보다는 자료 구조를 강조하기도 한다. 자료 구조는 주 기억 장치와 보조 기억 장치에 저장된 정보의 저장 및 검색을 구성하는 데 사용될 수 있다.^[8]

소프트웨어 개발에서 자료 구조 설계는 프로그램(알고리즘)의 효율성에 큰 영향을 미치므로, 다양한 자료 구조가 개발되었다. 프로그램 설계 시 자료 구조 선택은 중요한 문제인데, 이는 대규모 시스템 구축 경험상 구현의 어려움, 품질, 최종 성능이 최적의 자료 구조 선택에 크게 좌우되기 때문이다.

대부분 자료 구조가 정해지면 사용할 알고리즘도 비교적 명확해지지만, 때로는 특정 작업을 위한 최적의 알고리즘을 사용하기 위해 그에 맞는 자료 구조를 선택하기도 한다. 어떤 경우든 적절한 자료 구조 선택은 매우 중요하다. 이러한 중요성 때문에 많은 정형화된 설계 기법과 프로그래밍 언어에서는 자료 구조를 알고리즘보다 더 핵심적인 요소로 간주하기도 한다.

현대 프로그래밍 언어들은 자료 구조의 구현 세부 사항을 인터페이스 뒤로 숨기는 모듈화 기능을 제공하여, 다른 응용 프로그램에서 자료 구조를 안전하게 재사용할 수 있도록 지원한다. C++나 Java 같은 객체 지향 프로그래밍 언어에서는 클래스가 이런 역할을 한다.

자료 구조는 프로그래밍 전반에 걸쳐 매우 중요하기 때문에, C++의 STL, Java API, .NET Framework 등 여러 프로그래밍 언어의 표준 라이브러리나 환경에서 다양한 자료 구조를 기본적으로 제공한다. 자료 구조가 구현 자체를 의미하는지, 아니면 인터페이스를 의미하는지에 대해서는 논의가 있다. 이는 관점에 따라 다를 수 있는데, 자료 구조를 함수 사이의 인터페이스로 보거나, 자료형에 기반한 저장 공간 접근 방법을 구현한 것으로 볼 수도 있다.

4. 구현

자료 구조는 일반적으로 컴퓨터가 포인터로 지정된 메모리의 어느 위치에서든 데이터를 가져오고 저장할 수 있는 능력에 기반한다. 포인터는 메모리 주소를 나타내는 비트 문자열이며, 프로그램에 의해 메모리에 저장되고 조작될 수 있다. 따라서 배열과 레코드 자료 구조는 산술 연산을 사용하여 데이터 항목의 주소를 계산하는 데 기반하는 반면, 연결 리스트와 같은 구조는 구조 자체 내에 데이터 항목의 주소를 저장하는 데 기반한다. 예를 들어 배열의 연속적인 메모리 할당은 빠른 접근 및 수정 작업을 용이하게 하여 순차적인 데이터 처리 시나리오에서 최적화된 성능을 제공한다.^[10]

자료 구조의 구현에는 일반적으로 해당 구조의 인스턴스를 생성하고 조작하는 일련의 절차를 작성하는 것이 필요하다. 자료 구조의 효율성은 해당 연산과 별도로 분석할 수 없다. 이러한 관찰은 추상 자료형의 이론적 개념으로 이어진다. 추상 자료형(ADT)은 수행될 수 있는 연산과 해당 연산의 수학적 속성(공간 및 시간 비용 포함)에 의해 간접적으로 정의되는 자료 구조이다.^[11] 자료 구조는 ADT의 기반이 되며, ADT가 자료형의 논리적 형식을 정의한다면 자료 구조는 자료형의 물리적 형식을 구현하는 역할을 한다.^[5]

소프트웨어 개발에서 자료 구조를 어떻게 설계하는지는 프로그램(알고리즘)의 효율에 큰 영향을 미친다. 따라서 다양한 자료 구조가 고안되었으며, 많은 프로그램 설계에서 자료 구조의 선택은 주요 문제이다. 이는 대규모 시스템 구축 경험상, 구현의 어려움, 품질, 최종 성능이 최상의 자료 구조 선택에 크게 의존하기 때문이다.

대부분의 경우 자료 구조가 결정되면 사용하는 알고리즘은 비교적 명확하게 결정된다. 그러나 때로는 주어진 작업을 수행하는 최적의 알고리즘을 사용하기 위해 해당 알고리즘이 필요로 하는 특정 자료 구조를 선택하기도 한다. 어느 쪽이든 적절한 자료 구조의 선택은 매우 중요하다. 이러한 중요성은 많은 정형화된 설계 기법과 프로그래밍 언어에서 자료 구조가 알고리즘보다 중요한 구성 요소로 간주되는 점에서도 나타난다.

현대적인 프로그래밍 언어는 다른 응용 프로그램에서 자료 구조를 안전하게 재사용할 수 있도록 구현 세부 사항을 인터페이스 뒤에 숨기는 모듈화 메커니즘을 갖추고 있다. C++나 Java와 같은 객체 지향 프로그래밍 언어는 클래스를 이러한 목적으로 사용한다.

자료 구조는 프로그래밍에 매우 중요하므로, C++의 STL이나 Java API, 그리고 .NET Framework와 같은 프로그래밍 언어의 표준 라이브러리 및 환경에서 많은 자료 구조를 사용할 수 있다. 자료 구조가 구현을 나타내는지 아니면 인터페이스를 나타내는지에 대한 논쟁도 있다. 이는 상대적인 관점의 문제로, 자료 구조는 함수 간의 인터페이스로 볼 수도 있고, 데이터형을 기반으로 구성된 저장소에 접근하는 방법을 구현한 것으로 볼 수도 있다.

5. 예시

자료 구조에는 다양한 유형이 있으며, 일반적으로 더 간단한 원시 자료형을 기반으로 구축된다. 잘 알려진 예시는 다음과 같다.

• 배열: 특정 순서로 배열된 여러 요소를 담는 구조로, 일반적으로 모든 요소는 같은 유형이다(프로그래밍 언어에 따라 다를 수 있다). 각 요소는 정수 인덱스를 사용하여 접근한다. 보통 배열 요소들은 메모리 상에 연속적으로 할당되지만, 항상 그런 것은 아니다. 배열은 길이가 고정되어 있거나, 필요에 따라 크기가 조절될 수 있다. 가장 일반적인 자료 구조 중 하나이다.
• 연결 리스트: 노드(node)라고 불리는 데이터 요소들의 선형적인 모음이다. 각 노드는 데이터 값과 다음 노드를 가리키는 참조(포인터)를 가지고 있다. 연결 리스트의 주요 장점은 배열과 달리, 리스트의 나머지 부분을 재배치하지 않고도 값을 효율적으로 삽입하고 삭제할 수 있다는 점이다. 그러나 특정 요소에 대한 임의 접근과 같은 작업은 배열보다 느리다.
• 레코드: '튜플' 또는 '구조체'라고도 불리며, 여러 데이터를 하나로 묶은 집계 데이터 구조이다. 레코드는 보통 고정된 수와 순서의 값들을 포함하며, 각 값은 일반적으로 이름(필드 또는 멤버)으로 구분되어 접근한다. 객체 지향 프로그래밍에서는 객체와 구별하기 위해 일반 오래된 자료 구조(Plain Old Data Structure, PODS)라고도 한다.
• 해시 테이블: '해시 맵'이라고도 하며, 키(key)를 사용하여 값을 빠르게 찾을 수 있게 해주는 자료 구조이다. 해시 함수를 사용하여 키를 배열의 인덱스로 변환함으로써 평균적으로 매우 빠른 시간 안에 데이터에 접근할 수 있다. 해시 테이블은 사전, 캐시, 데이터베이스 인덱싱 등에 널리 사용된다. 단점으로는 서로 다른 키가 같은 인덱스로 변환되는 '해시 충돌'이 발생할 수 있으며, 이는 성능 저하를 일으킬 수 있다. 충돌 해결 방법으로는 체이닝(chaining)이나 열린 주소 지정(open addressing) 같은 기법이 사용된다.
• 그래프: 노드(정점)와 이들을 연결하는 엣지(간선)로 구성되어 개체 간의 관계를 나타내는 구조이다. 소셜 네트워크, 컴퓨터 네트워크, 교통망 등을 모델링하는 데 사용될 수 있다. 그래프는 엣지의 방향성 유무에 따라 유향 그래프와 무향 그래프로 나뉘며, 순환 구조를 가질 수도 있고 가지지 않을 수도 있다(비순환 그래프). 그래프를 탐색하는 대표적인 알고리즘으로는 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)이 있다.
• 스택과 큐: 배열이나 연결 리스트를 이용해 구현할 수 있는 추상 자료형(ADT)이다.
• 스택은 '후입선출'(LIFO, Last-In, First-Out) 원칙을 따른다. 즉, 가장 마지막에 넣은 요소가 가장 먼저 나온다. 주요 연산은 스택 맨 위에 요소를 추가하는 'push'와 맨 위 요소를 제거하는 'pop'이다. 자료의 나열 순서를 거꾸로 바꾸고 싶을 때 유용하다.
• 큐는 '선입선출'(FIFO, First-In, First-Out) 원칙을 따른다. 즉, 가장 먼저 넣은 요소가 가장 먼저 나온다. 주요 연산은 큐의 뒤쪽에 요소를 추가하는 'enqueue'와 앞쪽에서 요소를 제거하는 'dequeue'이다.
• 트리: 요소들을 계층적인 형태로 구성하는 구조이다. 트리는 엣지로 연결된 노드들로 이루어지며, 하나의 루트(root) 노드와 그 아래로 뻗어 나가는 서브 트리(subtree)들로 구성된다. 부모-자식 관계는 엣지로 표현된다. 트리는 다양한 알고리즘과 데이터 저장 방식에 널리 사용된다. 이진 트리, 힙, AVL 트리, B-트리 등이 대표적인 트리 유형이며, 효율적인 검색, 정렬, 데이터의 계층적 표현을 가능하게 한다.

• 트라이: '접두사 트리'라고도 불리며, 문자열을 효율적으로 검색하기 위해 특화된 트리 구조이다. 트라이에서 각 노드는 문자열의 한 문자를 나타내고, 노드 사이의 엣지는 문자 간의 연결을 의미한다. 이 구조는 자동 완성, 맞춤법 검사, 사전 구현과 같은 작업에 특히 유용하며, 문자열 접두사를 기반으로 한 빠른 검색과 연산을 가능하게 한다.

6. 언어 지원

대부분의 어셈블리 언어와 BCPL 같은 일부 저수준 프로그래밍 언어는 자료 구조에 대한 내장 지원이 부족하다. 반면, C나 Pascal과 같은 많은 고급 프로그래밍 언어 및 MASM 같은 일부 고급 어셈블리 언어는 구조체(C의 경우)나 레코드(Pascal의 경우), 그리고 배열 등 특정 자료 구조를 위한 특별한 문법이나 내장 기능을 제공한다.^[14][15]

대부분의 프로그래밍 언어는 여러 프로그램에서 자료 구조 구현을 재사용할 수 있도록 라이브러리 메커니즘을 갖추고 있다. 현대 언어들은 일반적으로 가장 널리 쓰이는 자료 구조들을 구현한 표준 라이브러리를 함께 제공하는데, 대표적인 예로는 C++의 표준 템플릿 라이브러리(STL), 자바 컬렉션 프레임워크, 그리고 마이크로소프트(Microsoft)의 .NET Framework가 있다.

현대 언어는 일반적으로 모듈형 프로그래밍을 지원하여 라이브러리 모듈의 인터페이스와 실제 구현을 분리한다. 일부 언어는 클라이언트 프로그램이 구현 세부 사항을 알 필요 없이 자료 구조를 사용할 수 있도록 불투명 자료형 기능을 제공하여 구현을 숨긴다. C++, Java, 스몰토크와 같은 객체 지향 프로그래밍 언어에서는 주로 클래스를 사용하여 이러한 목적을 달성한다.

참조

_[1] 서적 Introduction to Algorithms, Third Edition https://dl.acm.org/c[...] The MIT Press 2009
_[2] 서적 Dictionary of Algorithms and Data Structures [online] National Institute of Standards and Technology 2018-11-06
_[3] 백과사전 Data structure https://www.britanni[...] 2017-04-17
_[4] 서적 Encyclopedia of Computer Science http://dl.acm.org/ci[...] John Wiley and Sons 2003-08-29
_[5] 웹사이트 Abstract Data Types https://opendsa-serv[...] 2023-02-15
_[6] 서적 Beginning Database Design Wrox Publishing
_[7] 웹사이트 1.5 Applications of a Hash Table http://www.cs.uregin[...] 2018-06-14
_[8] 웹사이트 When data is too big to fit into the main memory http://homes.sice.in[...]
_[9] 간행물 Survey Paper on Fine-Grained Facial Expression Recognition using Machine Learning http://www.ijcaonlin[...] 2021-06-21
_[10] 간행물 Chapter 17 - Spatial Data Structures: Concepts and Design Choices https://www.scienced[...] North-Holland 2023-11-12
_[11] 서적 Advanced biotechnology : For B Sc and M Sc students of biotechnology and other biological sciences. S Chand 2014
_[12] 서적 Data structures McGraw Hill Education 2014
_[13] 웹사이트 C++ Language Note: POD Types http://www.fnal.gov/[...] Fermi National Accelerator Laboratory 1999-09-29
_[14] 웹사이트 The GNU C Manual https://www.gnu.org/[...] Free Software Foundation 2014-10-15
_[15] 웹사이트 Free Pascal: Reference Guide http://www.freepasca[...] Free Pascal 2017-09
_[16] 웹사이트 Concurrent Data Structures https://www.cs.tau.a[...]
_[17] 서적 Introduction to Algorithms, Third Edition https://dl.acm.org/c[...] The MIT Press 2009
_[18] 서적 Dictionary of Algorithms and Data Structures [online] National Institute of Standards and Technology 2018-11-06
_[19] 백과사전 Data structure https://www.britanni[...] 2017-04-17
_[20] 서적 "コンパクトデータ構造\u3000実践的アプローチ" 講談社サイエンティフィク 2023-07-26
_[21] 서적 簡潔データ構造 共立出版 2018-02-25
_[22] 서적 Encyclopedia of Computer Science http://dl.acm.org/ci[...] John Wiley and Sons 2003-08-29
_[23] 서적 Introduction to Algorithms, Third Edition https://dl.acm.org/c[...] The MIT Press 2009
_[24] 서적 Dictionary of Algorithms and Data Structures [online] National Institute of Standards and Technology 2018-11-06
_[25] 백과사전 Data structure https://www.britanni[...] 2017-04-17
_[26] 서적 Encyclopedia of Computer Science http://dl.acm.org/ci[...] John Wiley and Sons 2003-08-29
_[27] 서적 C로 배우는 쉬운 자료구조 한빛미디어