리스트 1 (ArrayList)

리스트 ADT

• 객체: n개의 element형으로 구성된 순서 있는 모임
• 연산:
  • insert(list,pos,item) ::= pos 위치에 요소를 추가한다.
  • insert_last(list,item) ::= 맨 끝에 요소를 추가한다.
  • insert_first(list,item) ::= 맨 앞에 요소를 추가한다.
  • delete(list,pos) ::= pos 위치의 요소를 제거한다.
  • clear(list) ::= 리스트의 모든 요소를 제거한다.
  • get_entry(list,pos) ::= pos 위치의 요소를 반환한다.
  • get_length(list) ::= 리스트의 길이를 구한다.
  • is_empty(list) ::= 리스트가 비었는지를 검사한다.
  • is_full(list) ::= 리스트가 꽉 찾는지를 검사한다.
  • print_list(list) ::= 리스트의 모든 요소를 표시한다.

 

구현

배열을 사용한 리스트의 구현

배열을 사용하였기때문에 크기제한이 있으며 원하는 위치에 요소를 삽입할 경우 배열을 한칸씩 밀어줘야한다.

#define MAX_LIST_SIZE 100

typedef int element;
typedef struct {
	element array[MAX_LIST_SIZE];
    int size;
}ArrayListType;

기초 연산

void error(char* message)
{
	fprintf(stderr, "%s\n", message);
	exit(1);
}
void init(ArrayListType* l)
{
	l->size = 0;
}
int is_empty(ArrayListType* l)
{
	return l->size == 0;
}
int is_full(ArrayListType* l)
{
	return l->size == MAX_LIST_SIZE;
}
element get_entry(ArrayListType* l, int pos)
{
	if (pos < 0 || pos >= l->size) {
		error("위치오류");
	}
	return l->array[pos];
}
void print_list(ArrayListType* l)
{
	int i;
	for (i = 0; i < l->size; i++) {
		printf("%d->", l->array[i]);
	}
	printf("\n");
}

항목 추가 연산

void insert_last(ArrayListType* l, element item)
{
	if (l->size >= MAX_LIST_SIZE) {
		error("리스트 오버플로우");
	}
	l->array[l->size++] = item;
}

void insert(ArrayListType* l, int pos, element item)
{
	if (!is_full(l) && (pos >= 0) && (pos <= l->size)) {
		for (int i = (l->size - 1); i >= pos; i--) {
			l->array[i + 1] = l->array[i];
		}
		l->array[pos] = item;
		l->size++;
	}
}

항목 삭제 연산

element delete(ArrayListType* l, int pos)
{
	element item;
	if (pos < 0 || pos >= l->size) {
		error("위치 오류");
	}
	item = l->array[pos];
	for (int i = pos; i < (l->size - 1); i++) {
		l->array[i] = l->array[i + 1];
	}
	l->size--;
	return item;
}

실행

int main()
{
	ArrayListType list;
	init(&list);
	insert(&list, 0, 10);	print_list(&list);
	insert(&list, 0, 20);	print_list(&list);
	insert(&list, 0, 30);	print_list(&list);
	insert_last(&list,40);	print_list(&list);
	delete(&list, 0);	print_list(&list);
	return 0;
}

실행 시간 분석

get_entry() 연산은 시간복잡도 O(1), 삽입이나 삭제연산은 최대 O(n) ; 배열을 이동하기때문, 맨끝에 삽입하는경우는 O(1).