🧩 [Data Structure] 자료구조의 추상데이터 타입

1️⃣ 추상.

• ‘추상의 레벨이 높다’
  • 사고의 수준이 높다라는 뜻
• ‘추상의 정의’
  • 관점이 계층화되어 상승한 것.
  • 하위의 개념들을 결합하여 상위의 고급 개념을 만들어나가는 지적 발전의 단계.
  • 계층와의 단계가 높으면 추상의 레벨이 높은 것이다.
• 추상의 역사
  • 인간의 사고가 진화해온 과정 자체.
  • 원시적이고 낮은 관점이 계층화를 거치면서 점점 차원이 높아져 옴.
• 객체 지향 언어의 클래스
  • 프로젝트나 문제 해결과정에서는 새로운 의미 단위를 분리하고 계층화하는 작업이 반복됨.
    • 클래스가 대표적 예.
• 모듈(Module)
  • 의미의 단위.
  • 통상적으로 모듈은 먼저 추상적인 레벨에서 설계되고, 후에 구체화된다.
• 모듈을 추상화(Abstraction)한다는 것.
  • 세부 사항을 생략하고 가장 중효한 기능만 드러내는 것.
• 추상화는 ‘위에서-아래로’ 이루어질 수도 있고, ‘아래에서-위로’ 이루어질 수도 있다.
  • 큰 그림을 먼저 그리고 점차 작은 모듈로 나누어가는 과정은 ‘위에서-아래로’ 방식.
  • 최하부 단위들을 준비하고 거기서부터 선택과 조합, 새로움을 가미하여 상위 헤벨의 그림을 만들어내는 과정은 ‘아래에서-위로’ 방식.
    • 일상에서 접하는 추상은 이 두 방식이 혼재함.

2️⃣ 추상 데이터 타임: ADT

• 자바의 8가지 기초 데이터 타입
  • byte
    • 정수 타입(1바이트)
  • short
    • 정수 타입(2바이트)
  • int
    • 정수 타입(4바이트)
  • long
    • 정수 타입(8바이트)
  • float
    • 실수 타입(4바이트)
  • double
    • 실수 타입(8바이트)
  • boolean
    • true
    • false
    • 논리타입(1비트 true or false)
  • char
    • 문자 타입(2바이트)
• 기초 데이터입이 아닌 데이터 타입에는 대부분 추상적 성격이 있다.
  • 어떤 성질을 공유하는 객체들의 집합은 하나의 데이터 타입을 이루기 좋은 후보다.
• 추상 데이터 타입(ADT, Abstract Data Type)
  • 세부 사항에서 벗어나 추상적으로 정의한 데이터 타입.
    • 즉, 어떤 데이터 타입이 어떤 작업으로 이루어지는지만 표현한 것이다.
      • 예를 들어 원소가 순서를 갖고 저장되는 자료구조인 리스트는 아래 그림의 (a)와 같이 표현 가능.
      • 또는 리스트가 지원하는 작업을(b)와 같이 좀 더 구체적으로 나열해 표현 가능.
        
• “추상적으로 표현한다”
  • 자료구조에서는 이런 식으로 어떤 대상이 지원하는 ‘작업을 나열해 표현’하는 것을 “추상적으로 표현한다”라고 한다.
    • 대상을 그렇게 표현한 것을 추상 데이터 타입이라 한다.
      • 이때 대상이 포함하는 데이터 속성에 제한이 있으면 데이터의 속성을 같이 서술해도 좋다.
• 위 그림의 (a)에서 3개의 작업을 지원하는 임의의 객체는 추상 데이터 타입(ADT) ‘리스트’에 속한다.
  • 달리 표현하면, ADT 리스트라는 데이터 타입에 속하는 객체는 이 3개의 작업을 지원한다.
• 자바에서 8가지 기초 데이터 타입을 제외한 나머지는 추상 데이터 타입이다.
  • 추상 데이터 타입은 대략 하나의 클래스에 대응된다.
    • 클래스는 자신의 규칙을 따르는 객체를 만들기 위한 틀이다.
      • 클래스는 (암묵적으로) 그런 객체들의 집합을 의미하기도 해서 하나의 데이터 타입이라 부르기도 한다.
• 하나의 ADT 아래에 여러 ADT가 포함될 수도 있다.
  • 자바에서 클래스의 상위 개념인 인터페이스(Interface) 기능이 ADT에 가장 잘 대응되는 개념이다.
• ADT는 어떤 데이터 타입이 어떤 작업으로 이루어지는지를 세부 사항 없이 표현한다.
  • 이때 아래 그림의 (a)처럼 핵심 작업만으로 표현할 수도 있고, (b)처럼 다른 작업을 더해 표현할 수도 있다.
    
• (a)처럼 최소한으로 표현해놓으면 대개 구현할 때 필요한 작업을 더 한다.
  • ADT 리스트는 ‘적어도 이 작업들은 포함해야 한다’는 뜻이다.
• 새 원소를 리스트의 첫자리에 넣거나 끝에 붙이는 것은 “i번째 자리에 새 원소 넣기”로 통합할 수 있다.
  • 그래도 첫자리나 끝자리에 새 원소를 넣는 작업이 아주 흔하면 따로 표현할 수도 있다.
    • 이처럼 특정 대상에 대한 ADT는 유동적이다.
      • 이런 면에서 ADT는 제공하는 사람의 주관적 관점이 반영된다.
• ADT는 프로그래밍 작업을 효율적이고 고급스럽게 할 수 있도록 돕기 위한 것이다.
  • ADT로 표현하는 것이 프로그래밍에 장애가 되어서는 안 된다.
  • ADT로 시작함으로써 자료구조 내부의 세세한 사항에 신경을 쓰지 않고 시작할 수 있다.
    • 즉, 자료구조와 접점을 이루는 함수들의 세부 사항에 집착하지 않고 자료구조가 하는 일만 생각하며 작업할 수 있다.
      • 이로 인해 협업도 원활해진다.
• 어떤 클래스 또는 클래스의 집단이 ADT나 ADT에 준할 만큼 잘 표현되어 있으면, 사용자는 그 내부의 세부 구현은 신경 쓰지 않고 ‘이용’할 수 있다.
  • 즉, ADT는 내부에서 작업을 ‘어떻게’하는지 신경 쓰지 않게 하며 ‘무엇을’ 하는지만 신경 쓰게 해준다.
    • 특히 여려 명이 진행하는 프로젝트에서 이 같은 개념의 추상화를 통한 인터페이스가 매우 유용하다.

3️⃣ 추상 데이터 타입과 자바 인터페이스.

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

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