배열로 구현된 리스트

리스트의 순차적 표현(sequential representation): 배열로 리스트를 구현하면 순차적인 메모리 공간이 할당

리스트의 정의

#define MAX_LIST_SIZE 100

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

- 배열과 항목 개수를 구조체로 묶어 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");
}

항목 추가 연산

- 리스트의 맨 끝에 항목을 추가하는 insert_last() 함수와 임의의 위치에 삽입하는 insert() 함수 구현

//리스트 끝에 삽입
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++;
	}
}

- 리스트의 pos 위치에 새로운 항목을 추가

- pos번째부터 마지막 항목까지 한 칸씩 이동하여 빈 자리를 만든 후에 새로운 항목을 pos 위치에 저장

- 빈 자리를 만들기 위해 array[1]부터 array[3]까지 한 칸씩 오른쪽으로 이동

- for 루프를 돌며 array[1]은 array[2]로, array[2]는 array[3]...으로 이동

- 새로운 항목을 array[1]에 저장

항목 삭제 연산

- pos 위치의 항목을 삭제하는 delete(list, pos) 구현

- 삽입 연산과 마찬가지로 삭제한 후 array[pos+1]부터 array[size-1]까지 한 칸씩 앞으로 이동

//임의의 위치에서 삭제
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;
}

전체 프로그램

#include <stdio.h>
#include <stdlib.h>
#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(void) {
	ArrayListType list;

	init(&list);
	insert(&list, 0, 10);	print_list(&list);	//0번째 위치에 10을 삽입하고 출력
	insert(&list, 0, 20);	print_list(&list);	//0번째 위치에 20을 삽입하고 출력
	insert(&list, 0, 30);	print_list(&list);	//0번째 위치에 30을 삽입하고 출력
	insert_last(&list, 40); print_list(&list);	//맨 끝에 40 삽입하고 출력
	delete(&list, 0);	print_list(&list);	//0번째 요소 삭제하고 출력

	return 0;
}