[자료구조] 자료구조(Data Structure)의 개념과 종류
1. 왜 자료구조를 알아야 하는가
알고리즘은 컴퓨터가 무슨 일을 해야 할지 지시하고, 자료구조는 컴퓨터에게 알고리즘에서 사용하는 자료를 어떻게 저장할지 지시하는 것이라고 할 수 있다.
즉, 프로그래밍이란 알고리즘을 작성하고, 그에 맞는 자료구조를 선택하는 것이라고도 할 수 있다.
이런 시각에서 자료구조를 충분하게 이해하지 못한 개발자는 결코 좋은 개발자가 될 수 없다고도 할 수 있을 것이다.
동일선상에서 프로그래밍 언어 중 하나인 Pascal을 개발한 스위스의 컴퓨터 과학자 니클라우스 비르트( Niklaus Emil Wirth; 1934 ~ 2024)는 <
Algorithms + Data Structures = Programs(1976)> 라는 저서를 지을 정도로 자료구조의 중요성을 강조한 바 있다.
자료구조에는 수 많은 종류들이 있으며 각각의 자료구조는 장단점이 존재하기 때문에 애플리케이션 구현 시 해결하고자 하는 문제의 종류와 우선순위 등에 따라 효율적인 자료구조가 달라질 수 있다.
따라서 효율적인 애플리케이션을 구현하기 위해서 모든 자료구조를 이해하지는 못할지라도 적어도 대표적으로 사용되는 몇 가지들은 분명하게 알 필요가 있을 것이다.
Linux를 개발한 리누스 토르발스(LinusTorvalds; 1969 ~ )는 자료구조의 중요성에 대해 아래와 같이 말한 바 있다(2006).
나쁜 프로그래머와 좋은 프로그래머의 차이는 그가 코드보다 자료구조를 더 중요하게 여기는지 여부에 달려 있다. 나쁜 프로그래머는 코드에만 신경을 쓰고, 좋은 프로그래머는 자료구조와 그 관계에 집중한다.
(the difference between a bad programmer and a good one is whether he considers his code or his data structures more important.
Bad programmers worry about the code.
Good programmers worry about data structures and their relationships)
2. 자료구조의 정의
2.1. 자료구조의 정의
자료구조란 개발자가 데이터를 효율적으로 사용할 수 있도록 정리하는 방법을 의미한다.
사람들에게 대표적인 자료구조의 예를 묻는다면, 흔히 리스트나 스택 등을 말할 것이다.
허나 엄밀히 말해 리스트나 스택, 큐 등은 자료구조라기 보다는 추상 데이터 형식(ADT)라고 할 수 있다.
그렇다면 추상 데이터 형식이란 무엇인가?
2.2. 추상 데이터 형식(ADT)
추상 데이터 형식(Abstract Data Types; ADT)이란 자료구조를 설명하는 데이터의 타입을 의미한다.
그리고 자료구조는 추상 데이터 타입을 실제로 구현한 결과를 말한다.
즉, ADT는 개념(청사진)을 제시하고 자료구조는 구현을 포함한다고 할 수 있다.
예컨대 스택이라는 추상 데이터 타입을 내부적으로 배열로 구현할지, 연결 리스트로 구현할지, 연산은 어떤 방식으로 구현할지 등의 세부 사항을 다루기 시작한다면 자료구조의 영역으로 넘어간다고 할 수 있다.
3. 자료구조의 분류
자료구조는 단순/복합, 선형/비선형 등 여러 속성을 기반으로 분류할 수 있다.
3.1. 단순(Primitive) / 복합(Non-Primitive)
단순 자료구조
- int와 같이 프로그래밍 언어에서 통상적으로 제공하는 기본 데이터 형식을 의미
복합 자료구조
- 단순 자료구조 이외의 자료구조
- 복합 자료구조는 다시 선형 자료구조와 비선형 자료구조로 분류
3.2. 선형(Linear) / 비선형(Non-Linear)
선형 자료구조
- 데이터 요소를 순차적으로 연결하는 자료구조(하단 그림 참고)
- 구현 및 사용 용이
- 배열(Array), 링크드 리스트(Linked List), 스택(Stack), 큐(Queue) 등
비선형 자료구조
- 데이터를 비연속적으로 연결하는 자료구조
- 한 데이터 요소에서 여러 데이터 요소로 연결되기도 하고 반대의 상황도 존재
- 트리(Tree), 그래프(Graph) 등
선형 자료구조는 첫 번째 요소에서 마지막 요소까지 순회하기 용이하나 비선형 자료구조는 종종 되돌아가야하는 (Backtracking) 상황이 발생할 수 있다.
따라서 개별 요소에 접근하는 작업에는 선형 자료구조가 더 효율적이나 소셜 네트워크의 연결과 같은 데이터는 비선형 자료구조가 더 알맞을 수 있다.
3.3. 정적(Static) / 동적(Dynamic)
정적 자료구조
- 크기가 고정되어 있는 자료구조
- 통상 프로그램 생성 시 크기 정의하므로 메모리를 비효율적으로 사용할 수 있음
- 저장할 요소의 갯수를 미리 알고 있고 해당 갯수가 변하지 않는 상황일 시 성능 우수
동적 자료구조
- 크기가 가변적인 자료구조
- 요소 추가 시 컴퓨터가 추가로 메모리 할당, 요소 제거 시 메모리 지움(요소 추가 및 제거 시 효율적)
- 저장할 데이터의 양을 특정할 수 없고 메모리 공간이 한정적일 시 성능 우수
3.4. 어떤 자료구조를 선택해야 하는가?
동일한 ADT를 사용할 지라도 자료구조에 따라 데이터의 삽입 / 삭제 / 탐색의 효율성과 연관되며 애플리케이션의 성능이 크게 달라질 수 있다.
예컨대 네트워크 애플리케이션의 입출력 버퍼에는 링크드 큐보다 환형 큐를 사용하는 것이 처리 속도 면에서 유리하고, 메모리의 효율이 더 중요한 애플리케이션에는 링크드 큐가 환형 큐보다 나은 선택일 수 있다.
운영 체제를 사용할 저수준 코드를 작성하거나 극한의 효율을 추구하는 상황이 아니라면 동적/정적 자료구조의 선택보다는 선형/비선형의 선택이 더욱 중요할 수 있다.