[자료구조] ch 1. 자료구조 소개

자료 구조란

​ 자료구조란 데이터에 효율적으로 접근하고 수정할 수 있도록 저장, 조직, 관리하는 방법에 관한 이론이며, 특히 자료구조는 알고리즘과 밀접하게 관련되어 있는데, 자료구조는 알고리즘에 필요한 부품 같은 역할입니다. 또한 자료구조는 생각하는 방법을 훈련하는 도구가 되기도 합니다. 자료구조를 구현하는 과정과 그 자료구조를 이용해서 문제를 해결하는 과정이 이에 해당합니다.

자료구조와 추상타입

​ ‘추상적이다’ 라는 건 애매하다는 의미로 사용되기도 하지만 여기서 말하는 ‘추상’ 이란 ‘관점이 계층화되어 상승한 것’ 입니다. 프로젝트 단에서 새로운 의미 단위를 분리하여 계층화하는 작업을 반복하는 것이지요. 객체 지향 언어의 클래스가 대표적인 예입니다.

​ 의미의 단위를 ‘모듈(Module)’ 이라고 하는데, 모듈은 먼저 추상 레벨에서 설계되고 후에 구체화됩니다. 추상화된다는 것은 세부 사항을 생략하고 가장 중요한 기능만 드러내는 것입니다.

추상 데이터 타입 ADT

자바에서 Primitive Type 을 제외하고는 대부분 추상적 성격의 데이터 타입이라고 볼 수 있습니다. 추상 데이터 타입(ADT, Abstract Data Type) 은 추상적으로 정의한 데이터 타입으로, 어떤 작업으로 이루어지는지만 표현한 것입니다.

예를 들어, List 를 다음과 같이 표현할 수 있습니다.

원소를 첫 번째, 두 번째, ..., i 번째 원소로 가리킬 수 있는 자료구조

이렇게 표현한 것을 추상 데이터 타입이라고 합니다.

또한 List 가 지원하는 작업을 아래와 같이 나열할 수 있습니다.

i번째 자리에 새 원소 넣기
원소 x 찾기
i번째 자리의 원소 삭제하기

이렇게 표현할 것을 ‘추상적으로 표현한다’ 라고 합니다.

​ 자바에서 primitive type 을 제외한 나머지는 추상 데이터 타입이고, 대략 하나의 클래스에 대응됩니다. 어떤 클래스가 ADT 로 잘 표현되어 있으면 사용자는 그 내부의 세부 구현은 신경쓰지 않고 이용할 수 있습니다. 즉, ADT 는 내부에 작업을 ‘어떻게’ 하는지 신경쓰지 않게 하며 ‘무엇을’ 하는지만 신경쓰게 합니다. 자바에서 이러한 ADT 에 가장 가까운 기능이 인터페이스입니다. ADT(인터페이스) 의 규약만 분명하면 구현 프로그래머와 사용 프로그래머의 추가적인 소통도 필요가 없죠.