JAVA 자료구조 - 자료구조의 추상 데이터 타입

자료구조의 추상 데이터 타입

 

1. 추상

의미의 단위를 흔히 모듈(Module)한다. 통상적으로 모듈은 먼저 추상적인 레벨에서 설계되고, 구체화 된다. 모듈을 추상화 Abstraction하나든 것은 세부 사항을 생략하고 가장 중요한 기능만 드러내는 것을 말한다. 추상화는 '위에서 - 아래로' 이루어질 수도 있고, '아래에서-위로' 이루어질 수도 있다. 큰 그림을 먼저 그리고 점차 작은 모듈로 나우어가는 과정은 '위에서 - 아래로 ' 방식이다. 반면 최하단 부 단위들을 준비하고 거기서부터 선택과 조합, 새로움을 가미하여 상위 레벨의 그림을 만들어 내는 과정은 '아래에서-위로' 방식이다. 일상에서 접하는 추상은 이 두 방식이 혼재한다.

 

2. 추상 데이터 타입 : ADT

추상 데이터 타입(ADT: Abstract Data Type)은 세부 사항에서 벗어나 추상적으로 정의한 데이터 타입이다. 즉, 어떤 데이터 타입이 어떤 작업으로 이루어지는 지만 표현한 것이다. 예를 들어 원소가 순서를 갖고 저장된는 자료구조인 리스트는 [그림 1-16]의 (a)와 같이 표현할 수 있다. 또는 리스트가 지원하는 작업을 (b)와 같이 좀 더 구체적으로 나열해 표현할 수 있다.

 

자료구조에서는 이런 식으로 어떤 대상이 지원하는 '작업을 나열해 표현'하는 것을 "추상적으로 표현한다."라고 하면, 대상을 그렇게 표현한 것을 추상 데이터 타입이라고 한다. 이때 대상이 포함하는 데이터 속성에 제한이 있으면 데이터 속성을 같이 서술해도 좋다.[그림 1-16]의 (b)에서 3개의 작업을 지원하는 임의의 객체는 추상 데이터 타입(ADT) '리스트'에 속한다. 달리 표현하면  ADT 리스트라는 데이터 타입에 속하는 객체는 이 3개의 작업을 지원한다.

 

자바에서 8가지 기초 데이터 타입을 제외한 나머지는 추상 데이터 타입이고 추상 데이터 타입은 대략 하나의 클래스에 대응된다. 클래스는 자신의 규칙을 따르는 객체를 만들기 위한 틀이다. 클래스는 (암묵적 으로) 그런 객체들의 집합을 의미하기도 해서 하나의 데이터 타입이라 부르기도 한다. 하나의 ADT아래 여러 ADT가 포함될 수도 있다. 자바에서 클래스의 상위 개념인 인터페이스(interface)기능이 ADT에 가장 잘 대응되는 개념이다.

 

 

 

그림 1-17 ADT 리스트

 

ADT는 어떤 데이터 타입이 어떤 작업으로 이루어지는지 세부 사항 없이 표현한다. 이때 [그림 1-17]의 (a)처럼 핵심 작업만으로 표현할 수도 있고, (b)처럼 다른 작업을 더해 표현할 수도 있다. (a)처럼 최소한으로 표현해놓으면 대개 구현할 때 필요한 작업을 더한다. ADT리스트는 '적어도 이 작업들은 포함해야 한다' 는 뜻이다. 

 

새 원소를 리스트의 첫자리에 넣거나 끝에 붙이는 것은 "i 번째 자리에 새 원소 넣기"로 통합할 수 있다. 그래도 첫자리나 끝자리에 새 원소를 넣는 작업이 해당 클래스에서 아주 흔하면 따로 표현할 수도 있다. 이처럼 특정 대상에 대한 ADT는 유동적이다. 

 

ADT로 시작함으로써 자료구조 내부의 세세한 사항에 신경을 쓰지 않고 시작할 수 있다. 즉, 자료구조와 접점을 이루는 함수들의 세부 사항에 집착하지 않고 자료구조가 하는 일만 생각하며 작업할 수 있다. 즉, ADT는 내부에서 작업을 '어떻게' 하는지 신경 쓰지 않게 하면 '무엇을'하는지만 신경 쓰게 해준다.

 

추상 데이터 타입과 자바 인터페이스

그림 1-18 ADT에서 사용자 프로그램까지

 

추상 데이터 타입이 자바 언어의 어떤 부분과 가장 연관이 깊은지 잠깐 살펴보자. 자바에서 ADT에 가장 가까운 기능을 인터페이스(interface)다. 예를 들어 [그림 1 - 18]의 (a)과 같은 ADT '리스트'를 (b)와 같이 인터페이스 기능을 이용해서 정의할 수 있다. 그러면 ListInterface란 이름의 인터페이스를 따르는 모든 클래스는 여기 나열된 3개의 작업을 제공하고, 각 작업의 리턴 타입과 파라키터의 수와 타입도 이 정의를 따라야 한다. 따라서 (c)와 같이 implements를 사용해 이 인터페이스를 따르는 클래스를 정의하면 클래스 LinkedList는 ListInterface 인터페이스를 따라 위 3개의 메서드를 지원한고, 각 함수의 리턴 타입과 파라미터 수와 타입도 따라야 한다.  그러면 (d)와 같이 사용자 프로그램에서는 이 인터페이스만 보고 1️⃣LinkedList 객체를 하나 할당받은 다음 2️⃣ListInterface에서 명시된 파라미터 수와 타입에 맞게 함수를 사용하면 된다. 그러면 사용자 프로그램 입장에서는 리스트의 내부가 어떻게 구현되었는지 있는지 알 필요 없이 "첫 번째 자리에 원소 x를 삽입하라", "3번째 원소를 삭제하라"와 같은 추상적 수중에서 리스트를 취급할 수 있다. 결국 추상 데이터 타입이 해당 타입의 객체를 '추상적인 수준에서' 사용할 수 있게 해주는 것이다.

 

그림 1-19 ADT 관련 업무 분담 구조의 예

 

규모가 큰 프로젝트라면 많은 ADT로 구성될 텐데, 기존 자료구조를 가져다 쓰기도 하고 새로 만들기도 한다.  [그림 1- 19]는 이 경우에 해당하는 ADT에 관한 업무 분담 구조의 예다. 팀장이 ADT를 설계하거나 결정하면 팀원이 그에 부응하는 자료구조를 구현하거나 오픈 소스를 가져다 쓴다. ADT의 규약만 분명하면 구현 프로그래머와 사용프로그래머도 이 데이터 타입에 관해 추가로 소통할 필요가 없다. 

 

 

 

[출처 - 쉽게 배우는 자료구조 with 자바,  저 문병로]
https://www.hanbit.co.kr/store/books/look.php?p_code=B7033044159

IT CookBook, 쉽게 배우는 자료구조 with 자바