[자료구조] - 4. 추상자료형, 리스트 ADT

추상자료형, 리스트 ADT

• 추상자료형(abstract data type, ADT): 데이터구조의 추상형
  • ADT는 다음을 명세
    • 1. 저장된 데이터
    • 2. 데이터에 대한 작업들
    • 3. 작업 중 발생 가능한 에러 상황들
  • 예: 주식거래 시스템을 모델링한 ADT
    • 1. 데이터 : 구매, 판매 주문들
    • 2. 지원하는 작업  : 주식 구매, 판매, 취소
    • 3. 에러 상황 : 존재하지 않는 주식에 대한 주문

 

 추상자료형(abstract data type, ADT)에 대해서 알아보겠습니다. 추상자료형은 자료구조를 추상적으로 표현한 것으로, 사람이 자료를 다루는 관점에서 자료구조를 표현한 것입니다.

 

 쉽게 말하면 실제 기능의 구현방법을 제외하고, 기능이 무엇인지만 설명하는 것이 추상자료형입니다. 예를 들어 카카오톡을 추상자료형으로 나타내면 채팅하기, 친구 추가하기, 프로필 사진 바꾸기 ... 등으로 나타낼 수 있습니다. 여기에는 채팅등이 어떤 과정으로 이루어지는지는 설명할 필요가 없습니다.

 

---

• 리스트 ADT
  • 원소들의 순서(ordered) 집단을 저장하기 위한 기초적이고, 일반적 목적의 데이터구조
  • 원소(element)에 대한 접근 도구 : 순위(rank)
  • 원소는 그 순위(rank), 즉, 그 원소 앞의 원소 개수를 특정함으로써 접근, 삽입, 또는 삭제
•  예외(exception): 어떤 ADT 작업을 실행하고자 할 때 발생할 수도 있는 오류 상황
  • “실행 불가능한 작업때문에 예외를 발령한다(throw)”고 말한다

 

• 배열을 이용한 구현
  • N개의 단순 또는 복잡한 원소들로 구성된 배열로 구현
  • 장점 : 쉬운 구현, 쉬운 참조 ( 인덱스 값 = rank → 참조시 실행 시간 O(1) )
  • 단점 : 삭제, 추가 과정이 번거로움 ( 맨 앞 원소를 제거 또는 추가하는 경우 실행 시간 O(n) )

• 연결리스트를 이용한 구현
  • 원소 및 링크를 저장하는 노드를 이용하여 구현
  • 이중연결리스트를 이용하는 것이 접근과 조작이 더 쉬움
  • 장점 : 삭제, 추가 과정이 비교적 쉬움 ( 맨 앞 원소 제거 or 추가시 실행 시간 O(1) )
  • 단점 : 참조 과정이 번거로움 ( 참조시 실행 시간 O(n) )

 

 리스트 ADT는 연속적인 개체들을 다루는 가장 단순한 추상자료형입니다. 배열 또는 연결리스트로 구현할 수 있는데요, 배열로 구현하는 경우 rank가 주어지면 참조가 쉽다는 장점이 있습니다. 연결리스트로 구현하는 경우 연속된 데이터 중간에 데이터를 추가하거나 제거하는 것이 쉽다는 장점이 있습니다.

 

 먼저, 배열을 이용하여 리스트 ADT를 구현해 보겠습니다. 구현은 C언어를 이용했습니다.

typedef struct arraylist {	
	int arr[100];	// 배열
	int n;			// 저장된 원소의 크기
}arraylist;

// 초기화, 실행시간 O(1)
void initialization(arraylist* list) {
	list->n = 0;
}

// rank r인 원소 참조, 실행시간 O(1)
void reference(arraylist* list, int r) {
	printf("%d ", list->arr[r]);
}

 

 배열의 선언, 초기화, 참조입니다. 배열의 index가 rank와 같기 때문에 굉장히 간단합니다. 실행시간 역시 짧습니다.

 

// r 위치에 element 추가, 실행시간 O(n)
void add(arraylist* list, int element, int r) {
	if (r<0 || r>list->n) {
		printf("error");
		return;
	}
	for (int i = list->n - 1; i >= r; i--) {
		list->arr[i + 1] = list->arr[i];
	}
	list->arr[r] = element;
	list->n++;
}

// r 위치의 원소 제거, 실행시간 O(n)
void delete(arraylist* list, int r) {
	if (r<0 || r>list->n) {
		printf("error");
		return;
	}
	for (int i = r + 1; i <= list->n - 1; i++) {
		list->arr[i - 1] = list->arr[i];
	}
	list->n--;
}

 

 배열을 이용하여 만든 리스트 ADT의 원소 추가와 제거 부분입니다. C언어를 이용해서 구현해 보았습니다. 중간에 원소를 삽입하면 그 자리 뒤의 원소들은 하나하나 뒤로 밀려나기 때문에 시간이 오래 걸립니다. 중간에 원소를 제거하는 경우도 마찬가지입니다. 중간의 원소가 비면 그 뒤의 원소들을 다 앞당겨서 저장해야 하므로 실행 시간이 길어지게 되는 단점이 있습니다. 

 

 연결리스트를 이용한 리스트 ADT의 구현은 다음 게시글을 통해 살펴보겠습니다.

 

---