자구/ADT(Abstract Data Type), 추상 자료형이란?

1. 개요

보통 자료구조 책 처음에 ADT를 소개하고, 각 자료구조마다 먼저 ADT를 정의한 다음 각 자료구조의 소개를 시작한다. ADT, 추상 자료형이란 무엇이고 왜 자료형이라고 부를까? 왜 각 자료구조를 소개할 때마다 ADT가 들어갈까? 또 자료구조 공부에 있어서 ADT는 왜 중요할까?

2. 정의

 ADT 혹은 추상 자료형은 소프트웨어에서 자료와 그 자료에 대한 연산들을 모아 놓은 것으로, 연산의 구현은 명시하지 않는다.

3. 왜 추상 '자료형' 인가?

기능의 명세인데 왜 추상'자료형(data type)'이라고 할까? 자료형을 어떻게 사용하는지 즉 구조체와 관련된 연산의 종류를 결정하는 것까지도 자료형 정의의 일부로 보기 때문이다.
우선 형(type)이란 말을 살펴보자. 형이라고 하면 내게는 어감이 좀 이상하니까 그냥 타입입라고 부르는 게 낫겠다. 타입이란 값들의 모임이다. Boolean type은 true와 false라는 두 값으로 이루어져 있고, integer type은 정수들로 이루어져 있다. 타입에는 단순한 타입(simple type)이 있고, 합성 타입(composite type)이 있는데 정수 타입의 경우 별다른 부분 없이 정 수 값들로만 이루어져 있으므로 단순한 타입이다. 만약 여러 부분들로 이루어져 있다면 합성 타입이다.
자료형(data type)이란 타입의 일종인데, 그 타입을 다루는 연산들을 함께 모아놓은 것이다. 정수 자료형이라고 하면 정수의 덧셈, 뺄셈, 곱셈, 나눗셈 등 정수로 할 수 있는 연산들을 모아놓은 것이다. 자료형의 논리적인 개념과 컴퓨터 프로그램에서의 실제 구현은 구분해야 한다. 가령 list라는 자료형의 구현은 전통적으로 '배열 기반 구현'과 '연결 리스트 구현'으로 나뉜다. 어떤 자료형의 개념은 하나지만 자료형의 구현은 여러 방법이 있을 수 있다.

4. 개념과 구현의 구분

추상 자료형은 핵심은 캡슐화(encapsulation)이다. 어떤 자료구조의 실제 구현은 캡슐화되어서 사용자가 굳이 알 필요가 없다. 가령 내가 stack을 사용한다고 하면, push와 pop만 알아도 상관이 없고 그 내부가 연결 리스트로 구현이 되어 있는지 어떤지는 알 필요가 없다. 따라서 추상 자료형은 어떤 자료구조가 가지는 '기능의 명세'라고 할 수 있다. 일단 그 자료구조에 필요한 기능들을 쭉 나열해놓고 구현 부분은 따로 하는 것이다. 그래서 어떤 자료구조의 구체적인 구현을 모르고 추상 자료형만 보더라도 기능을 사용하는 데에는 문제가 없게 된다.

5. 자료구조 공부와 ADT

학교 커리큘럼 상에 '자료구조'과목이 있기는 하지만 예습이 좀 필요할 것 같다. 구글 검색하면  <윤성우의 열혈 자료구조>가 자료구조 입문자에게 최고라고 하더라. 이 책을 보면 자료구조를 공부할 때에는

1. 자료구조의 ADT 정의
2. 정의한 ADT의 구현
3. 구현이 완료된 자료구조의 활용

이 세 단계를 따라서 공부하라고 한다. 그래서 앞으로 쓸 자구 공부 글은 이 세 가지 단계를 잘 따르면서 작성할 생각이다.

1번과 2번도 물론 중요하지만, 자주 쓰는 자료구조는 꼭 구현을 하지 못하더라도 활용을 할 수는 있어야 한다. C++에서 많이 쓰이는 vector 라는 자료형을 보자. vector 자료형은 push_back(), pop_back(), erase() 등, 데이터를 넣고 내보내고 지우고 하는 여러 가지 기능을 가지고 있지만 그걸 쓸 때에는 vector가 어떻게 구현되어 있는지 알 필요는 전혀 없다. 물론 알면 좋겠지만서도.