[알고리즘] 기본 추상자료형(1) - 설명(리스트ADT, 집합ADT)

추상자료형이란 데이터구조의 추상형으로서, 인간이 데이터를 다루는 관점에서 데이터구조를 명세한 것이다

종류로는 리스트ADT, 집합ADT, 큐ADT, 트리ADT등이 있다

기억장소 사용량은 모두 O(n)이다

추상자료형 가운데 가장 먼저 알아야할 것은 리스트ADT로, 리스트ADT는 연속적인 임의개체들을 모델링한다

리스트ADT 메소드

1) 일반 메소드

integer size() - 리스트의 크기, 즉 원소 수를 반환

boolean isEmpty() - 리스트가 비어 있는지 여부를 반환

iterator elements() - 원소 전체를 반환

2) 접근 메소드

element get(r) - 순위r에 저장된 원소를 반환

3) 갱신 메소드

element set(r, e) - 순위r에 저장된 원소를 e로 대체

add(r, e) - 순위r앞에 원소e를 삽입

addFirst(e) - 맨 앞에 원소e를 삽입

addLast(e) - 맨 뒤에 원소e를 추가

element remove(r) - 순위r에 저장된 원소를 삭제하여 반환

element removeFirst() - 맨 앞에 저장된 원소를 삭제하여 반환

element removeLast() - 맨 뒤에 저장된 원소를 삭제하여 반환

4) 예외 메소드

invalidRankException() - 부당한 순위에 대한 접근으로 인해 처리 불가능한 상황에서 사용

fullListException() - 리스트가 만원이라 처리 불가능한 상황에서 사용

emptyListException() - 리스트가 비어 있어 처리 불가능한 상황에서 사용

배열/연결리스트를 이용한 리스트ADT의 성능

	size, isEmpty	get, set	add, remove	addFirst, removeFirst
배열	O(1)	O(1)	O(n)	O(1) - 원형배열 이용시
연결리스트	O(1)	O(n)	O(n)	O(1)

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

집합ADT는 광범위하게 사용되는 데이터 모델이다

집합ADT메소드

1) 주요메소드

set union(B) - 집합B와의 합집합을 반환

set intersect(B) - 집합B와의 교집합을 반환

set subtract(B) - 집합B를 차감한 차집합을 반환

2) 일반메소드

integer size() - 집합의 원소 수를 반환

boolean isEmpty() - 집합이 비어 있는지 여부를 반환

iterator elements() - 집합의 전체 원소를 반환

3) 질의메소드

boolean member(x) - 개체x가 집합의 원소인지 여부를 반환

boolean subser(B) - 집합이 집합B의 부분집합인지 여부를 반환

4) 갱신메소드

addElem(x) - 집합에 원소x를 추가

removeElem(x) - 집합으로부터 원소x를 삭제

5) 예외메소드

emptySetException() - 비어 있는 집합에 대해 삭제 혹은 첫 원소 접근을 시도할 경우 사용

집합은 일반적으로 리스트로 구현할 수 있다(더 광범위한 집합에 사용될 수 있음으로 일반적)

집합A, B에 대해서의 성능

	union, intersect, subtract	member(e)	subset
연결리스트	O(|A| + |B|)	O(A)	O(|A| X |B|)

출처

제목: 알고리즘 원리와 응용

저자: 국형준

출판사: 21세기사