추상 자료형(Abstract Data Type, ADT)이란?
구현하고자 하는 구조에 대해 구현 방법은 명시하지 않고 자료구조의 특성들과 어떤 Operations들이 있는지를 설명하는 자료구조의 한가지 형태. 즉, 일종의 '규칙'들의 나열이라고 쉽게 이해할 수 있다.
ADT의 가장 대표적 예로는 스택(Stack)과 큐(Queue)가 있다.
Abstract Data Type vs Data Structure
우리가 알고 있는 자료구조(Data structure)는 추상 자료형이 정의한 연산들을 구현한 구현체를 가리킨다. 즉, 추상 자료형은 구현 방법을 명시하고 있지 않다는 점에서 자료구조와는 다르다.
예를 들어, 스택(Stack)의 형태는 LIFO 값들의 모임이고 push, pop, size 등의 연산을 정의할 수 있다. 그렇지만 스택이 내부적으로 배열로 구현되는지 연결 리스트로 구현되는지, 또는 size 연산을 수행할 때 원소의 개수를 일일이 세는지 아니면 개수를 따로 저장해 두는지와 같은 세부 사항들은 추상 자료형에서는 다루지 않으며, 그걸 다루기 시작하면 자료구조의 영역으로 넘어가게 된다.
둘은 명백히 구분되지만, 추상 자료형과 그것을 구현한 자료구조의 이름이 비슷하거나 아예 같은 경우가 많다. 이를 구분하는 법은 조금이라도 구현 방법이 정해져 있는지 보는 것이다.
자바(Java)로 치면 클래스인지 인터페이스인지를 확인하면 된다. 스택이나 큐는 구현 방법이 전혀 정의되어 있지 않으니 추상 자료형이고, 배열은 연속적으로 저장되어 있도록 구현되어 있어야 하므로 자료구조이며, 연결 리스트도 다음 데이터의 위치를 저장하는 방식으로 정해져 있으니 자료구조이다. 이렇듯 추상 자료형은 구현 방법을 명시하고 있지 않다.
실무에도 중요할까?
위 설명처럼 자바의 인터페이스는 ADT라고 할 수 있으며 이를 실제로 구현한 class를 DS라고 볼 수 있다는 것이다. 이렇듯 ADT에 대한 이해도는 실무에서 설계작업할 때, 의사소통적인 면에서 중요하므로 꼭 개념을 이해하는 것이 중요하다.
ex) 스택이 어쩌고 저쩌고 -> ADT적 관점
ex) 그래서 스택을 어떤 구현체를 써서 구현했어 -> DS적 관점
참고
- https://www.youtube.com/watch?v=QcsQKgXemtA