순차 리스트

리스트의 기본 특징은 데이터를 나란히 저장하고 데이터의 중복을 막지 않는다는 점이다

위와 같은 특징으로 리스트의 ADT를 정의하면 다음과 같다

// pos 위치에 요소를 추가
insert(list, pos, item)

// 맨 끝에 요소를 추가
insert_last(list, item)

// 맨 처음에 요소를 추가
insert_first(list, item)

// pos 위치의 요소를 제거
delete(list, pos)

// 리스트의 모든 요소를 제거
clear(list)

// pos 위치의 요소를 반환
get_entry(list, pos)

// 리스트의 길이를 구함
get_length(list)

// 리스트가 비었는지 검사
is_empty(list)

// 리스트가 꽉 찼는지 검사
is_full(list)

// 리스트의 모든 요소를 표시
print_list(list)

위와 같은 리스트 ADT는 포인터를 이용해서 구현할 수 있지만, 배열을 사용하면 더 간단하게 구현할 수 있다

배열로 만든 리스트를 순차 리스트라고 한다

 

이제 리스트 ADT를 토대로 순차 리스트와 기본 연산들을 정의해보자

#define MAX_LIST_SIZE 100

typedef int element;
typedef struct
{
    element array[MAX_LIST_SIZE];
    int size;			// 리스트에 저장된 항목들의 개수
} ArrayListType;

// 리스트 초기화
void init(ArrayListType *L)
{
    L -> size = 0;
}

// 리스트가 비어 있으면 1 반환
int is_empty(ArrayListType *L)
{
    return L -> size == 0;
}

// 리스트가 가득 차 있으면 1 반환
int is_full(ArrayListType *L)
{
    return L -> size == MAX_LIST_SIZE;
}

// 리스트 출력
void print_list(ArrayListType *L)
{
    for (int i = 0; i < L -> size; i++)
    {
        printf("%d -> ", (L -> array)[i]);        
    }
    printf("\n");
}

// 맨 뒤에 항목 추가
void insert_last(ArrayListType *L, element item)
{
    if (is_full(L))
    {
        printf("Overflow!\n");
        return;
    }
    (L -> array)[(L -> size)++] = item;
}

// Pos 위치에 항목 추가
void inser(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)
    {
        printf("Pos Error!\n");
        exit(1);
    }
    else if (is_empty)
    {
        printf("Underflow!\n");
        exit(1);
    }
    item = (L -> array)[pos];
    for (int i = pos; i < (L -> size - 1); i++)
    {
        (L -> array)[i] = (L -> array)[i + 1];
    }
    (L -> size)--;
    
    return item;
}

 

마지막으로 순차 리스트의 장단점을 알아보면,

장점 : 구현이 간단하고 속도가 빠르다

단점 : 리스트의 크기가 고정되고 데이터의 이동이 빈번하게 일어난다