리스트의 구현 (연결리스트)

먼저 리스트를 추성 데이터 타입으로 정의한 리스트 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) := 리스트의 모든 요소를 표시한다

리스트는 배열과 연결 리스트를 이용하여 구현할 수 있다. 배열을 이용하면 리스트 ADT 를 가장 간단하게 구현할 수 있다. 하지만 크기가 고정되는 점은 단점이다. 다른 방법으로는 포인터를 이용하여 연결 리스트를 만드는 방법이 있다. 연결 리스트는 필요할 때마다 중간에 속지를 추가해서 사용할 수 있는 바인더 공책과 비슷하다. 배열을 사용하여 리스트를 구현하면 장점과 단점이 존재한다. 장점은 구현이 간단하고 속도가 빠르다는 것이다. 단점으로는 리스트의 크기가 고정된다는 것이다. 즉 배열의 특성상 동적으로 크기를 늘리거나 줄이는 것이 힘들다. 따라서 만약 데이터를 추가하고 싶은데 더 이상 남은 공간이 없다면 문제가 발생한다. 물론 메모리 공간이 부족해지면 더 큰 배열을 만들어서 기존 배열의 데이터들을 전부 복사하면 되지만 이것은 CPU 시간을 낭비한다. 또한 리스트의 중간에 새로운 데이터를 삽입하거나 삭제하기 위해서는 기존의 데이터들을 이동하여야 한다. 연결리스트는 크기가 제한되지 않고, 중간에서 쉽게 삽입하거나 삭제할 수 있는 유연한 리스트를 구현할 수 있다. 하지만 연결 리스트도 단점이 있는데 구현이 복잡하고 임의의 항목(i번째) 을 추출하려고 할 때는 배열을 사용하는 방법보다 시간이 많이 걸린다.

 

 

배열로 리스트를 구현하기 위하여 배열과 항목의 개수를 구조체로 묶어서 ArrayListType이라는 새로운 타입을 정의하도록 하자

#define MAX_LIST_SIZE 5

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

이제 리스트의 연산들을 함수로 구현해보자. 모든 연산은 구조체 포인터를 받는다. 구조체 포인터를 받아야 하는 이유는 함수 안에서 구조체를 변경할 필요도 있기 때문이다. 포인터를 사용하지 않으면 구조체의 복사본이 전달되어서 원본 구조체를 변경할 수 없다. 일단 쉽게 구현할 수 있는 연산부터 구현해보자.

 

#include <stdio.h>
#include <stdlib.h>
#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:4996)
#include <malloc.h>
#include <string.h>

#define MAX_LIST_SIZE 5

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()
{
  //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;
}