초급편 8. 리스트 구조

                                          포인터 토대가 된 책

                                              리스트 구조

구조체를 이용한 응용 예로서 리스트 구조를들 수있다. 리스트 구조는 매우 필수적인 데이터 구조의 하나이며, 응용 범위가 매우 넓다. 이 리스트 구조에 익숙 할 C 언어 초급 졸업 시험이라고해도 과언이 아니다.

왜 리스트 구조가 이토록 중요한인가하면, 삭제 및 삽입을 쉽게 할 수 있기 때문이다. 배열의 경우, 특히 삽입은 고비용이다. 배열 데이터 다음에 새로운 데이터를 삽입하려면 그 이후의 데이터를 전부 하나씩 밀어 주어야한다. 삭제의 경우에도 데이터를 채우는 작업을하거나 별도로 플래그를 갖게하고 "잘못된 데이터"를 마킹 해 줄 필요가있다.

반면 리스트 구조는 삽입을 낮은 비용으로 할 수 있지만, 대신 배열처럼 인덱스에 의한 랜덤 액세스 할 수 없게된다. 그래서 첨자에 의한 랜덤 액세스의 비용과 삽입의 비용 사이의 균형으로 선택해야하지만, 일반적으로 유용한 사례는 매우 많다.

또한 리스트 구조는보다 복잡한 구조를 만들어내는 기초가되는 데이터 구조이다. 다음과 이전 양방향 포인터를 가진 양방향 리스트도 있고, 이원 나무처럼 두 개의 포인터를 가지고도 아마 나무처럼 그 이상의 포인터를 가져도 좋지만, 그 해부 위한 기초는 간단한 리스트 구조이다.

또한 검색의 국면에서는 정렬 된 배열에서 이진 검색을 사용할 수있어 빠른 것이지만, 리스트 구조는 기본적으로 순차 액세스 의한 선형 탐사에 한정되게 늦어진다. 이를 효율화하기 위해 이원 나무 탐사와 해시 같은 수의 좋은 알고리즘이 존재한다. 이러한 기초 역시 리스트 구조이다. 따라서 리스트 구조를 제대로 이해하는 것이, 중급 프로그램의 전제이다.

포인터를 사용하지 않는 리스트 구조

먼저 포인터를 사용하지 않고 리스트 구조를 실현 해 보자.

struct List {
	int data;
	int next;
};
struct List MyList [128];

우선, 전역으로 선언되는 것으로한다. 그러므로 확보 된 MyList 배열은 현재 모든 0이 들어있다. 이때 다음의 규칙을 정한다.

1. data 멤버에 유용한 데이터가 들어있다.
2. next 멤버는 데이터의 다음 데이터를 나타내는 인덱스 번호가 들어있다.
3. next 멤버가 0이면, 미사용이다.
4. next 멤버가 -1이면, 그것이 마지막 데이터이다.
5. MyList [0]에 들어있는 유효한 데이터가 아니라 단순히 첫 번째 데이터의 색인 번호가 MyList [0] .next에 들어있을 뿐이다.

즉, 데이터를 참조하면, 그 다음 데이터는 next 멤버로 나타나는 데이터이라는 것이다. 선두는 데이터 값이 거짓이다 MyList [0]이며, 앞으로 시작하여 차례로 "체인을 따르도록」참조 해 나가면된다. 그리고 체인의 마지막을 나타내는 MyList [i] .next == -1 을 찾으면 거기서 끝난다. 이 리스트 구조이다.

리스트 구조 참조

이때 "10/100/1000"의 3 개의 데이터가 들어있는 목록을 만든다고하자. 그 구체적인 표현은 하나 정해지지 않고, 여러가지 있어도 좋다. 예를 들어,

MyList [0] .data = 0; / *이 데이터는 더미. * /
MyList [0] .next = 1;
MyList [1] .data = 10;
MyList [1] .next = 2;
MyList [2] .data = 100;
MyList [2] .next = 3;
MyList [3] .data = 1000;
MyList [3] .next = -1; / * 다음의 데이터는 없다. * /

그렇지만,

MyList [0] .data = 0; / *이 데이터는 더미. * /
MyList [0] .next = 4;
MyList [1] .data = 100; / * 두 번째 데이터 * /
MyList [1] .next = 3;
MyList [2] .data = 100;
MyList [2] .next = 0;    / *이 데이터는 사용되지 않는다 * / 
MyList [3] .data = 1000; / * 세 번째 데이터 * / 
MyList [3] .next = -1;   / * 다음 데이터는 없다. * / 
MyList [4] .data = 10;   / * 첫 번째 데이터 * /
MyList [4] .next = 1;

하지만 상관 없다. 데이터를 순서대로 참조 가면 첫 번째 구조에서는 "(0) → 1 → 2 → 3"의 순서로 액세스하지만, 후 구조에서는 "(0) → 4 → 1 → 3"의 순서로 액세스하는 하게된다. 이와 같이, 참조하는 순서를 색인 번호와 분리하는 것이 핵심 아이디어이다.

그래서이 참조 프로그램은 다음과 같다.

void chaseList (void)
{
    int at = MyList [0] .next;
    while (at! = -1) {
        printf ( "data = % d \ n", MyList [at] .data);
        at = MyList [at] .next;
        if (at == 0) {
            fprintf (stderr, "일어날 수없는 \ n");
            exit (1);
        }
    }
}

리스트 구조의 데이터 삭제

값이 100 인 데이터를 삭제 해 보자.

void delete100 (void)
{
    int at = MyList [0] .next;
    int prev = 0;
    while (at! = -1) {
        if (MyList [at] .data == 100) {
            MyList [prev] .next = MyList [at] .next;
            MyList [at] .next = 0;   / * 유효하지 않은 데이터로 * /
            printf ( "값이 100의 데이터를 삭제했습니다! \ n");
            break;
        }
        prev = at;
        at = MyList [at] .next;
        if (at == 0) {
            fprintf (stderr, "일어날 수없는 \ n");
            exit (1);
        }
    }
    if (at == -1) {
        printf ( "값이 100의 데이터를 찾을 수 없습니다. \ n");
    }
}

된다. 후 데이터 구조에서이 함수를 실행하면 다음과 같은 데이터로 업데이트된다.

MyList [0] .data = 0; / *이 데이터는 더미. * /
MyList [0] .next = 4;
MyList [1] .data = 100; / * 두 번째 데이터 * / 
MyList [1] .next = 0 ;
MyList [2] .data = 100;
MyList [2] .next = 0;    / *이 데이터는 사용되지 않는다 * / 
MyList [3] .data = 1000; / * 세 번째 데이터 * / 
MyList [3] .next = -1;   / * 다음 데이터는 없다. * / 
MyList [4] .data = 10;   / * 첫 번째 데이터 * / 
MyList [4] .next = 3 ;

이 알고리즘 목록의 첫 번째 데이터를 삭제하는 경우에도 마지막 데이터를 삭제하는 경우에도 제대로 움직이는 지 확인하기 바란다.

포인터를 사용한 리스트 구조

복습이라고리스트 구조는 자기 참조 구조체라는 구조에 의해 정의된다.

struct List {
        int data;
        struct List * next;
};

이 선언에서 struct List를 정의하고있는 가운데, strut List를 사용하는 것은 모순 된 것이 아닐까 생각한다면, 이전 페이지를 참조하기 바란다. 규칙은 약간 변경된다.

1. data 멤버에 유용한 데이터가 들어있다.
2. next 멤버는 데이터의 다음 데이터를 가리키는 포인터가 들어있다.
3. next 멤버가 NULL (== 0)이면, 사용되지 않는 마지막 데이터이다.
4. MyList [0]에 들어있는 유효한 데이터가 아니라 단순히 첫 번째 데이터 포인터가 MyList [0] .next에 들어있을 뿐이다.

이제 순차적으로 참조 제거를 만들어 보는. 그렇다면,

void chaseList (void)
{
    struct List * at = MyList [0] .next;
    while (at! = NULL) {
        printf ( "data = % d \ n", at-> data);
        at = at-> next;
    }
}


void delete100 (void)
{
    struct List * at = MyList [0] .next;
    struct List * prev = & MyList [0];
    while (at! = NULL) {
        if (at-> data == 100) {
            prev-> next = at-> next;
            at-> next = NULL;   / * 유효하지 않은 데이터로 * /
            printf ( "값이 100의 데이터를 삭제했습니다! \ n");
            break;
        }
        prev = at;
        at = at-> next;
    }
    if (at == NULL) {
        printf ( "값이 100의 데이터를 찾을 수 없습니다. \ n");
    }
}

이제 동등한 처리가 가능하게된다. 구조체 포인터 멤버 참조이므로 화살 연산자를 사용하는 것에주의하라. 또한 목록의 이음 기준은 순서가 중요한 것을 기억하기 바란다.

리스트 구조 삽입

에서는 삽입 해 보자. 말인가 순차적으로 읽어 가고, 결과적으로 정렬 된 목록을 얻을 같은 삽입 정렬 알고리즘된다.

void insertList (struct List * ins)
{
    struct List * at = myList [0] .next;
    struct List * prev = & myList [0];
    while (at! = NULL) {
        if (ins-> data> = at-> data) {
            ins-> next = prev-> next;
            prev-> next = ins;
            break;
        }
        prev = at;
        at = at-> next;
    }
    if (at == NULL) { / * 마지막으로 추가 특별 취급 * /
        ins-> next = NULL;
        prev-> next = ins;
    }
}

포인트는 조작이 하나 전의 것 (prev)에서 수행되는 것이다. 삽입의 이음 기준은 순서에주의하고 여전히 필요한 데이터를 없애 버리지 않게 조심 받고 싶다.

또한이 삽입 정렬은 배열의 경우에는 "비교 비용이 낮은 '가'교체 비용이 높은 '특징이 있기 위하여 거품 정렬보다 괜찮지 만 선택 정렬보다 효율이 나쁜 경향이 있지만 리스트 구조를 가지고 가면 교환 비용을 낮출 수 있기 때문에 빠른 정렬을하지 않으 추천 방식이되고, 이미 어느 정도 역순으로 갖추어져있는 것이 전제가되는 경우에는 편하고 효율적인 방법 그렇지만있다. (오름차순 정렬에 어느 정도 갖추어져있는 경우에는 직전에 삽입 된 데이터를 at와 prev 초기 값으로 포인트두면 좋다.)