[자료구조] 연결리스트

리스트란?

순서를 가진 항목들의 모임이다. 

리스트 구현방법으로 배열을 이용한 구현과 연결리스트를 이용한 구현이 있다.

 

배열로 구현된 리스트

• 배열을 이용하여 리스트를 구현하면 순차적인 메모리 공간이 할당되므로, 이것을 리스트의 순차적 표현(sequential representation)이라고 한다.

#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 ) {
		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를 정적으로 생성하고 ArrayListType를 	
	// 가리키는 포인터를 함수의 매개변수로 전달한다.
	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;
}

연결된 표현

• 리스트의 항목들을 노드(node)라고 하는 곳에 분산하여 저장
• ¨노드는 데이타 필드와 링크 필드로 구성
  데이타 필드 – 리스트의 원소, 즉 데이타 값을 저장하는 곳
  링크 필드 – 다른 노드의 주소값을 저장하는 장소 (포인터)
• 장점 : 삽입, 삭제가 보다 용이하고 연속된 메모리 공간이 필요 없으며 크기 제한이 없다.
• 단점 : 구현이 어렵고 오류가 발생하기 쉽다.

단순 연결 리스트

• 하나의 링크 필드를 이용하여 연결
• 마지막 노드의 링크 값은 NULL

• 연산

insert_first(): 리스트의 시작 부분에 항목을 삽입하는 함수

insert(): 리스트의 중간 부분에 항목을 삽입하는 함수

delete_first(): 리스트의 첫 번째 항목을 삭제하는 함수

delete(): 리스트의 중간 항목을 삭제하는 함수(도전 문제)

print_list(): 리스트를 방문하여 모든 항목을 출력하는 함수