추상 자료형(Abstract Data Type)을 왜 알아야 할까

자료구조를 배우기도 전에 추상 자료형을 배워야 하는 게 좀 이상할 수 있다. 하지만, 특정한 자료구조는 추상 자료형을 구현한 것에 지나지 않는다. 똑같은 추상 자료형도, 다양한 방법과 다양한 프로그래밍 언어로 구현할 수 있고, 구현을 하기 전에 규칙을 정의하는 건 기본이기 때문에 추상 자료형을 잘 이해하는 것은 자료구조를 이해하기 위한 첫걸음이다. 

 

---

추상 자료형이란?

추상 자료형은 자료구조가 따라야 할 규칙들을 추상적으로 정의한 것이다. 추상 자료형은 실제로 이 자료구조를 어떻게 구현해야 하는지는 전혀 언급하지 않는다. 추상 자료형은, 영어로 Abstract Data Type라고도 하는데, 이를 줄여서 ADT로 나타내는 경우도 많다.

 

구체적으로는, 추상 자료형은 자료구조가 어떤 자료를 저장하는지와, 어떤 연산을 할 수 있는지(어떤 함수를 가지고 있는지)를 알려준다.

 

한 가지 주의해야 할 점은, 추상 자료형과 실제 구현된 자료구조의 이름이 같은 경우도 많다는 것이다. 예를 들어, 스택(Stack)이라고 불리는 추상 자료형은, 구현된 자료구조의 이름도 스택(Stack)이라 조금 헷갈린다.

---

추상 자료형과 실제 구현의 예시

추상 자료형을 더 잘 이해할 수 있게 한 가지 예를 들 수 있는것은 교통수단이 있다. 교통수단을 추상 자료형이라고 해 보자. 그렇다면 교통수단이라는 추상 자료형을 실제로 구현한 탈 것들은 자전거도 있을 수 있고, 자동차도 있을 수 있을 것이다.

 

추상 자료형 - 교통수단

실제 구현 - 자전거, 자동차, 스쿠터 등

 

여기서 중요한 것은, 교통수단은 목적이 있고, 그 목적을 수행하기 위한 조건들이 있다는 것이다. 교통수단의 목적은 이동하는 것이기 때문에, 일정한 속력으로 앞으로 갈 수 있어야 한다. 하지만 무조건 앞으로 갈 일만 있는 것은 아니기에 뒤로 갈 수도 있어야 한다. 이런 식으로, 교통수단이 갖추어야 할 필수적인 기능들이 있다. 이를 표로 나타내면 다음과 같다.

 

교통수단이 가져야 할 연산	연산 설명
정해진 속력으로 앞으로 가기(속력)	정해진 속력으로 앞으로 간다
정해진 속력으로 뒤로 가기(속력)	정해진 속력으로 뒤로 간다
정해진 속력으로 바꾸기(속력)	정해진 속력으로 바꾼다
멈추기()	멈춘다
현재속력()	현재 속력을 알려준다

 

실제 추상 자료형도 이것과 크게 다르지 않다. 교통 수단을 정의하면 실제로 이런 조건을 만족하는 교통수단을 만드는 것은 엔지니어들의 몫이듯이, 자료구조도 추상 자료형은 자료 구조의 사용법을 알려줄 뿐이고, 이를 구현하는 것은 프로그래머의 몫이다.

---

추상 자료형과 실제로 구현한 자료구조

실제 추상 자료형과, 그 추상 자료형을 구현한 자료구조의 대표적인 예를 아래와 같다.

 

추상자료형(ADT)	구현(자료구조)
리스트(List)	가변 배열(Dynamic Array), 연결 리스트(Linked List)
큐(Queue)	연결 리스트로 구현한 큐, 배열로 구현한 큐, 스택으로 구현한 큐
스택(Stack)	스택(Stack)
맵(Map)	트리 맵(Tree Map), 해쉬 맵(Hash Map)

 

추상 자료형과 자료구조의 이름이 다른 경우도 많지만, 이름이 같은 경우도 있다. 앞에서도 언급한 스택이 그러하다.

 

각각의 자료구조가 무엇이고, 어떨때 쓰면 좋고, 어떻게 구현해야 하고, 실제 사용한 예시들은 각각의 자료구조를 다룬 포스팅에서 확인할 수 있다. 아직 추상 자료형이 구체적으로 무엇인지 감이 안 온다면, 비교적 간단한 가변 배열을 가볍게 공부해 보는 것도 나쁘지 않다.

 

한 가지 흥미로운 것은, 추상 자료형에서는 자료구조가 가져야 할 함수들을 명시하지만, 이 함수들이 어떤 복잡도를 가질지는 명시하지 않기 때문에, 어떤 구현 방법을 쓰느냐에 따라 효율성이 달라질 수 있기 때문에, 자료구조를 구현하는 것을 자세히 알아두는 것도 매우 중요하다.

---