Linked List I(배열로 구현)

1. List 추상 데이터 타입

list는 항목들이 순서 또는 위치를 가지는 자료형이다.(항목 간 순서가 없는 집합과 비교된다)

<List 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): 리스트의 모든 요소를 표시

2. List 구현 in array

배열로 list를 구현할 시 다음과 같은 장단점이 있다.

장점: 구현이 간단하고, 속도가 빠름
단점: 리스트의 크기가 고정됨

배열을 이용하여 list를 구현하면 순차적인 메모리 공간이 할당된다.
이를 '리스트의 순차적 표현(sequential representation)'이라 한다.

이제 코드로 구현한다.

• 리스트의 정의: 배열과 항목의 개수를 구조체 'ArrayListType'으로 정의한다.

#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", message);
	exit(1);
}
//리스트 초기화 함수
void init(ArrayLsitType *L){
	L->size = 0;
}
//리스트가 비어있으면 1, 그렇지 않으면 0을 반환
int is_empty(ArrayListType *L){
	return L->size == 0;
}
//리스트가 가득차있으면 1, 그렇지 않으면 0을 반환
int is_full(ArrayListType *L){
	return L->size == MAX_LIST_SIZE;
}
element get_entry(ArrayListType *L, int pos){
	if(pos < 0 || pos >= L->MAX_LIST_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");
}

• 항목 추가 연산: 첫째로, 리스트의 맨 끝에 항목을 추가하는 함수를 구현한다.
  둘째로, pos 위치에 새로운 항목을 추가하려면, pos번째부터 마지막 항목까지 한칸씩 오른쪽으로 이동하여 빈자리를 만든 후에 pos위치에 저장한다.

// 리스트 맨 끝에 항목을 추가
void insert_last(ArrayListType *L, element item){
	if(L->size >= MAX_LIST_SIZE){
    	error("리스트 오버플로우");
    }
    L->array[L->size++] = item;
}
// pos위치에 새로운 항목을 추가
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위치의 항목을 삭제하기 위해 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>

// 앞의 코드들을 넣는다//

int main(void)
{
	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, 0, 40); print_list(&list);
    delete(&list, 0); print_list(&list);
    return 0;
}

시간복잡도는 O(1)이다. 최악의 경우 O(n)이 된다.