[C] 리스트와 연결리스트(1)

 

단순 연결리스트(simply linked list)로 리스트를 구현해보자.

이름이 비슷해서 헷갈릴 수 있겠지만, 리스트는 자료구조의 한 형태이고 연결리스트는 자료구조를 구현하는 방법이다.

예를 들면, 선형자료구조에는 스택, 큐, 리스트(+덱)이 있고, 이 자료구조들은 배열이나 연결리스트를 이용해 각각 구현이 가능하다.

 

데이터 필드에는 구조체를 이용해서 원하는 값을 저장한다. 일단은 전역변수가 있는 기본 테스트 프로그램을 짤 것이다(시험에는 전역변수 없이 이중포인터를 이용하라는 문제가 나올 것 같지만...). 각 함수들을 제대로 정의해야 이해가 쉬운 코드를 짤 수 있을 듯.

 

• init(): 리스트를 초기화한다.
• is_empty(): 리스트가 비어있는지를 검사한다.
• is_full(): 리스트가 가득 차 있는지를 검사한다.(근데 이걸 할 필요가 있나? 연결리스트로 구현하면 끝도 없이 늘어날텐데 굳이 꽉 차 있는지를 알아봐야할 이유가 있는지 궁금. 실제로도 구현할 때 이 함수는 안썼음)
• size(): 리스트 안의 요소의 개수를 반환한다.
• get_entry(pos): pos의 위치요소를 반환한다.
• inset_next(*prev, *n): 요소를 추가한다.
• insert(pos, item): inset_next함수를 이용해 위치설정 후 추가
• remove_next(*prev): 요소를 삭제한다.
• remove(pos): remove_next함수를 이용해 위치설정 후 삭제
• find(item): 리스트에 요소 item이 있는지 search함.
• print_all(): 리스트 안의 모든 요소를 순차적으로 출력한다.

** 모든 값과 position은 사용자가 입력하는 방식(User input)

** 조건은 position이 차례대로 증가한다고 가정

** 이 코드에는 오류가 있다!(find할 때 리스트에 없는 값 입력하면 Not in list를 출력하는게 아니라 그냥 종료됨ㅎㅎ main에서 find함수 호출해서 경우의 수 나눈 부분에 오류가 있는 것 같다)

 

 

<소스코드>

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
 
typedef int element;
typedef struct LinkedNode {
    element data;
    struct LinkdedNode* link;
}Node;
 
Node* head;
 
void init() {
    head = NULL;
}
int is_empty() {
    if (head == NULL) return 0;
    else return 1;
}
int size() {
    Node* p;
    int count = 0;
    for (p = head; p != NULL; p = p->link) //p라는 노드가 head부터 시작해서 NULL값(즉 끄트머리)까지 따라다님
        count++;
    return count;
}
Node* get_entry(int pos) {
    Node* n = head;
    for (int i = 0; i < pos; i++, n = n->link)
        if (n == NULL) return NULL; //n이라는 노드가 pos를 따라다니면서(? data값을 찾아다닌다는 얘긴가?) 구조체 반환
    return n;
}
void insert_next(Node* prev, Node* n) {
    if (n != NULL) {
        n->link = prev->link;
        prev->link = n;
    }
}
void insert(int pos, element value) {
    Node* new_node, * prev;
    new_node = (Node*)malloc(sizeof(Node)); //삽입할 새로운 노드 동적할당(이거 따로 함수로 뺄 수도 있을거같은데)
    new_node->data = value;
    new_node->link = NULL;
    /*
    여기서 경우가 두개로 나누어진다
    1. new_node가 맨 앞에 들어간다. head가 NULL인 경우, 즉 공백리스트 일 때!
    2. new_node가 중간에 들어간다.
    */
    if (head == NULL)
        head = new_node;
    else {
        prev = get_entry(pos - 1); //한 개 전의 노드를 prev로 불러온다.
        if (prev != NULL)
            insert_next(prev, new_node);
    }
}
Node* remove_next(Node* prev) {
    Node* removed = prev->link;
    if (removed != NULL) //삭제될 노드가 존재할 경우
        prev->link = removed->link;
    return removed;
}
void delete(int pos) {
    Node* prev, * removed;
    /*
    삭제도 두가지 경우의 수가 있다.
    1. 삭제할 노드가 맨 첫 노드, 즉 head일 때
    2. 중간의 노드를 삭제할 때
    */
    if (pos == 0 && is_empty() == 0) {
        removed = head;
        head = head->link;
        free(removed);
    }
    else {
        prev = get_entry(pos - 1);
        if (prev != NULL) {
            removed = remove_next(prev);
            free(removed);
        }
    }
}
int find(int item) {
    Node* p = head ;
    while (is_empty() != 0) {
        if (p->data == item) return item;
        else p = p->link;
    }
    return item;
}
void print_all() {
    Node* p;
    int i;
    for (i = 0, p = head; p != NULL; i++, p = p->link) {
        printf("0%d:%d", i, p->data);
        printf("\n");
    }
}
int main(void) {
    int sel, pos, value, get_num;
    
    init();
    while (1) {
        do {
            printf("[ 1.Display 2.Insert 3.Delete 4.Find 0.Exit ] : ");
            scanf("%d", &sel);
        } while (sel < 0 || sel > 4);
        if (sel == 1) {
            if (is_empty() == 0) {
                printf("Empty List!!\n");
            }
            else print_all();
            printf("\n");
        }
        else if (sel == 2) {
            printf("To Which position?: ");
            scanf("%d", &pos);
            printf("Enter value: ");
            scanf("%d", &value);
            insert(pos, value);
            printf("\n");
        }
        else if (sel == 3) {
            printf("To Which position?: ");
            scanf("%d", &pos);
            delete(pos);
            printf("\n");
        }
        else if (sel == 4) {
            printf("Enter the value that you want to find: ");
            scanf("%d", &value);
            if (is_empty() == 0) printf("[%d]는 리스트에 없습니다(Empty list)\n", value);
            else {
                get_num = find(value);
                if (get_num != NULL) printf("[%d]는 리스트에 있습니다\n\n", value);
                else printf("[%d]는 리스트에 없습니다(Not in list)\n\n", value); //여기에 오류있다... 근데 왜????
            }
        }
        else break;
    }
    printf("\nE N D  O F  P R O G R A M");
    return 0;
}

 

 

<결과 창>

 

 

+ 사실 이게 중요한게 아니다. 이중포인터로 구현하는게 핵심이다. 근데 전역변수 쓰면 이렇게 편한 걸 왜 쓰지 말라고 하지?? 매개변수로 일일이 넘겨줄 필요도 없잖아..?