[C언어] 배열로 구현한 리스트

리스트의 추상 데이터 타입 
리스트는 자료를 정리하는 방법 중의 하나입니다. 
일상생활에서 할일... 버킷리스트.. 요일.... 등등 
다양한 리스트가 존재합니다. 

리스트에는 항목들이 차례대로 저장되어 있다. 리스트의 항목들은 운서 또는 위치를 가집니다. 

L = (item0,item1,item2,....,itemn-1)

 

리스트 ADT 
리스트를 활용하면 어떤 연산을 할 수 있을까요? 
- 리스트에 새로운 항목 추가 (삽입, 연산)
- 리스트 항목 삭제 (삭제 연산)

- 리스트 특정 항목 검색(탐색 연산)

 

이를 추상 데이터 타입으로 간단히 몇개만 정의 해보면 

- 객체 : n개의 element형으로 구성된 순서 있는 모임 

- 연산: 
insert(list,pos,item)::= pos 위치에 요소 추가 
delete(list,pos) ::= pos 위치에 요소 제거 
get_entry(list, pos) ::= pos 위치의 요소를 반환

 

이외에 길이를 구한다던가, 꽉찼다던가, 비여있다던가, 출력한다던가, 중간에 삽입한다던가 등등 
다양한 기능을 만들 수 있겠습니다. 

 

리스트 구현

그럼 앞서 만든 ADT 를 통해 구현해봅시다. 이번글에선 리스트는 배열과 연결리스트를 이용하여 구현합니다. 

배열을 이용하면 ADT 리스트를 가장 간단하게 구현할 수 있습니다. 하지만 크기가 고정되는 단점을 가지고 있습니다.

 

장점 : 구현이 간단하고 빠르다.
단점 : 배열의 특성상 동적으로 크기를 늘리거나 줄이는 것이 불가능 -> CPU 시간 낭비 초래

또한 중간에 새로운 리스트를 삽입 또는 삭제를 하면 기존의 데이터들을 모두 이동시켜야함. 

 

그렇다면 연결리스트로 리스트를 만들면 어떨까? 
장점: 중간에 쉽게 삽입하거나 삭제할 수 있는 유연한 리스트 구현
단점 : 구현이 복잡하고, 임의의 항목을 추출하려고 할 때는 배열을 사용하는 방법보다 시간이 많이 걸림

 

각각의 장단점이 존재합니다. 데이터의 수를 생각하고, 해당 데이터의 물리설계를 고려해서 리스트를 짜면 될겁니다. 

 

구현 코드를 살펴보겠습니다. 

#include <stdio.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;
}
// 리스트가 비어 있으면 1을 반환
// 그렇지 않으면 0을 반환
int is_empty(ArrayListType* L)
{
	return L->size == 0;
}
// 리스트가 가득 차 있으면 1을 반환
// 그렇지 많으면 1을 반환
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) { //full을 호출 해줘도 된다. 
		error("리스트 오버플로우");
	}
	L->array[L->size++] = item; //증가 시키는 오퍼레이션이 중요! 
	//대입하는 연산이 우선 -> 그 다음 size를 늘려주는 것이 중요하다. 
}
//
void insert(ArrayListType* L, int pos, element item) //중요!! 
{
	if (!is_full(L) && (pos >= 0) && (pos <= L->size)) { 
		// pos <= L->size 라고 하는 이유는 새로 추가되는 데이터까지 고려하여 =을 넣었다.
		for (int i = (L->size - 1); i >= pos; i--) //shift 하는 과정 //for의 조건을 제대로 쓰는게 중요하다! 
			//shift 연산을 할떄는 i 가 0부터 시작하면 뒤에 있는애한테 엎어쓰게 된다. 그러므로 마지막부터 시작해줘야지 제대로 옮길 수 있다. 
			L->array[i + 1] = L->array[i]; 
		L->array[pos] = item;
		L->size++;
	}
}
//
element delete(ArrayListType* L, int pos)
{
	element item;
	//insert 0<= pos <= L->size 3개 0,1,2...(3)을 넣는 것이 말이 된다. 
	//delete 0,1,2,...() 여기서 3은 유효하지 않은 위치라서 걸러준다. 
	//insert와 delete에 따라 유효한 위치를 체크하는 범위가 다르다.! 
	if (pos < 0 || pos >= L->size)  
		error("위치 오류");
	item = L->array[pos]; 
	for (int i = pos; i < (L->size - 1); i++) //이번엔 앞에 아이부터 땡긴다. 뒤에서부터 땡기면 또 엎어쓰게 된다.
		//size 가 4니깐 size-1까지 for 문이 돌도록 해야한다. <=를 안하고 <만 한다.
		L->array[i] = L->array[i + 1]; //이 부분을 어떻게 하냐에 따라 for 문 안의 조건이 달라진다. 
	L->size--;
	return item;
}
void insert_first(ArrayListType* L, element item) {
	if (!is_full(L)) {
		//pos 0 index 값을 저장할 계획 
		// 0, 1, ...,size-1 -> 1,2,...,size

		for (int i = L->size - 1; i >= 0; i--) {
			L->array[i + 1] = L->array[i];
		}
		L->array[0] = item;
		L->size++;
	}
}

//
int main(void)
{
	// ArrayListType를 정적으로 생성하고 ArrayListType를 	
	// 가리키는 포인터를 함수의 매개변수로 전달한다.
	ArrayListType list;

	init(&list); //size = 0
	insert_first(&list, 10);	print_list(&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;
}

실행시간 분석 

배열로 구현한 리스트의 시간복잡도는 get과 같은 요소를 찾는 연산은 인덱스를 사용하여 접근하니 O(1)이 되겠습니다. 하지만 삽입이나 삭제는 다른 항목들이 이동하는 경우가 많으므로 최악의 경우는 O(n)이 되겠습니다.