Overview

추상적이고 논리적인 고급적 표현의 데이터와 연산자들은 결국 구체적이고 물리적인 저급 데이터와 연산자들로 구현되어야 실행될 수 있다.

그런데 연산자의 구현은 데이터의 표현 방법에 크게 의존하기 때문에 데이터 표현은 중요하다.

고급으로 표현된 데이터에 대한 저급 표현은 크게 순차 표현(sequential representation)과 연결 표현(linked representation)으로 구분할 수 있다.

순차 표현은 기본적으로 연속된 메모리 블록을 이용하여 데이터를 표현한다.

이 포스트에서는 순차 데이터 표현에 대해 알아보고 연결 데이터 표현에 대해서는 다음 포스트에서 살펴본다.

---

배열 추상 데이터 타입

거의 모든 프로그래밍 언어들은 배열(array)을 시스템 데이터 타입으로 지원하고 있다.

배열이 물리적으로는 연속적인 메모리 할당 방식으로 구현되어 있기 때문에 보통 배열을 연속된 메모리 주소의 집합이라고 정의하고 있다.

그러나 이것은 배열의 메모리 구현 측면에서 강조된 표현이다.

배열의 본질은 순차적 메모리 할당 방식에다 <인덱스(index), 원소(element)> 쌍의 집합으로, 각 쌍은 어느 한 인덱스가 주어지면 그와 연관된 원소 값이 결정되는 대응 관계를 나타내는 것이다.

여기서 인덱스는 순서를 나타내는 원소의 유한 집합이다.

순서가 있다는 것은 집합 내에서의 상대적 위치, 즉 첫 번째 원소, 두 번째 원소 등으로 식별할 수 있으며, 유한하다는 것은 원소 수가 한정되어 있어 항상 마지막 원소가 존재한다는 뜻이다.

배열의 또 다른 특성 중 하나는 원소들이 모두 같은 타입: 동질(homogeneous)의 값으로 그 크기도 같다는 것이다.

배열의 접근 방식은 직접 접근(direct access)이다.

원하는 원소는 어떤 것이고 순서에 따라 접근하지 않고 인덱스에 따라 직접 접근 할 수 있다.

따라서 접근하고자 하는 원소값은 상대적 위치를 표시하는 인덱스로 명세하면 된다.

사용자가 배열 데이터 타입을 사용하고자 할 때, 만일 시스템이 시스템 데이터 타입으로 제공하지 않는다면, 사용자는 이 배열 데이터 타입을 사용자 데이터 타입으로 직접 정의해야할 것이다.

이런 환경에서 배열 추상 데이터 타입(array abstract data type)을 정의해보면 다음과 같다.

ADT Array

데이터 : <i\(\in\)Index, e\(\in\)Element> 쌍들의 집합. 여기서 Index는 순서를 나타내는 원소의 유한 집합이고 Element는 타입이 같은 원소의 집합
연산 : a\(\in\)Array; i\(\in\)Index; x, e\(\in\)Element; n\(\in\)Integer;
      create(n) ::= return an array to hold n elements;
      retrieve(a,i) ::= if (i\(\in\)Index) then return e where <i, e>\(\in\)a
          else return error;
      store(a,i,e) ::= if (i\(\in\)Index) then return (a\(\cup\)<i,e>)
          else return error;
End Array

연산 create()는 n개의 원소들을 저장할 수 있는 공백 배열(empty array)을 생성한다.

초기에는 모든 원소값들이 정의되지 않은 상태이다.

연산 retrieve()는 Array와 Index를 매개 변수로 전달받아 Index를 검사하여 유효하면 이 Index에 대응되는 원소를 반환하고 무효이면 error를 반환한다.

연산 store()는 Array, Index, Element를 매개변수로 전달받아 Index를 검사하여 유효하면 <인덱스, 원소>쌍이 되게 원소를 저장한 뒤 Array를 반환한다.

이때 어떤 원소 x가 이미 이 Index와 대응 관계에 있으면, 이 x는 매개 변수로 전달받은 원소로 대체되며 Index가 무효이면 error를 반환한다.

여기서 Index가 유효, 무효인지는 그 Index값이 Index 집합의 원소인지 아닌지를 의미하는 것이다.

또한 이 배열 ADT 정의는 배열이 단순히 연속적 메모리 주소의 집합이라는 구현적인 명세보다는 배열에 포함되는 데이터와 연산들을 명확하게 정의함으로써, 배열의 본질을 더 정확하게 이해할 수 있도록 표현하고 있는 이점을 가진다.

---

참고 문서

• 이석호. (2004). 자료 구조와 JAVA. 정익사.