[C] 단순 연결 리스트(Singly Linked List)

단순 연결 리스트(Singly Linked List)

• 단순 연결 리스트는 노드들이 하나의 링크 필드를 가지며 이 링크 필드를 이용하여 모든 노드들이 연결되어 있다.
• 마지막 노드의 링크 필드 값은 NULL이다.
• 첫 번째 노드를 가리키는 포인터(헤드 포인터) 값만 알고 있으면 연결 리스트 안의 모든 노드에 접근이 가능한다.
  • 하나의 단순 연결 리스트는 첫 번째 노드를 가리키는 하나의 포인터만 있으면 충분하다.
• 헤드 포인터(Head Pointer) : 첫 번째 노드를 가리키는 포인터

 

코드

#include <stdio.h>
#include <stdlib.h>

typedef int element;

typedef struct ListNode {
    element data;
    struct ListNode *link;
} ListNode;

void error(char *message) {
    fprintf(stderr, "%s\n", message);
    exit(1);
}

void insert_node(ListNode **phead, ListNode *p, ListNode *new_node) {
    if (*phead == NULL) { // 공백 리스트인 경우
        new_node->link = NULL;
        *phead = new_node;
    }
    else if (p = NULL) {    // p가 NULL이면 첫 번째 노드로 삽입
        new_node->link = *phead;
        *phead = new_node;
    }
}

void remove_node(ListNode **phead, ListNode *p, ListNode *removed) {
    if (p == NULL) {
        *phead = (*phead)->link;
    }
    else {
        p->link = removed->link;
    }
    free(removed);
}

ListNode *search(ListNode *head, int x) {
    ListNode *p;
    p = head;
    while (p != NULL) {
        if (p->data == x) return p;         // 탐색 성공
        p = p->link;
    }
    return p;
}

ListNode *concat(ListNode *head1, ListNode *head2) {
    ListNode *p;
    if (head1 == NULL) return head2;
    else if (head2 == NULL) return head1;
    else {
        p = head1;
        while (p->link != NULL) {
            p = p->link;
            p->link = head2;
            return head1;
        }
    }
}

ListNode *reverse(ListNode *head) {
    // 순회 포인터로 p, q, r을 사용
    ListNode *p, *q, *r;
    p = head;               // p는 아직 처리되지 않은 노드
    q = NULL;               // q는 역순으로 만들 노드
    while (p != NULL) {
        r = q;
        q = p;
        p = p->link;
        q->link = r;;       // q의 링크 방향을 바꾼다.
    }
    return q;               // q는 역순으로 된 리스트의 헤드 포인터
}

ListNode *create_node(element data, ListNode *link) {
    ListNode *new_node;
    new_node = (ListNode *)malloc(sizeof(ListNode));
    if (new_node == NULL) error("메모리 할당 에러");
    new_node->data = data;
    new_node->link = link;
    return new_node;
}

void display(ListNode *head) {
    ListNode *p = head;
    while (p != NULL) {
        printf("%d->", p->data);
        p = p->link;
    }
    printf("\b\b \n");      // 마지막에 -> 출력을 없애기 위함.
}

void display_recur(ListNode *head) {
    ListNode *p = head;
    if (p != NULL) {
        printf("%d->", p->data);
        display_recur(p->link);
    }
    else {
        printf("\b\b \n");  // 반복문 모습과 동일하게 출력하기 위함
    }
}

void free_list(ListNode **phead) {
    ListNode *removed, *p = *phead;
    while (p != NULL) {
        removed = p;
        p = p->link;
        *phead = p;
        free(removed);
    }
}

void main() {
    ListNode *list1 = NULL, *list2 = NULL;
    ListNode *p;

    insert_node(&list1, NULL, create_node(10, NULL));
    insert_node(&list1, NULL, create_node(20, NULL));
    insert_node(&list1, search(list1, 10), create_node(30, NULL));        // search 사용하여 중간노드 찾기
    insert_node(&list1, search(list1, 30), create_node(40, NULL));        // search 사용하여 중간노드 찾기
    insert_node(&list1, search(list1, 20), create_node(50, NULL));        // search 사용하여 중간노드 찾기
    insert_node(&list1, search(list1, 30), create_node(60, NULL));        // search 사용하여 중간노드 찾기
    display_recur(list1);        // list1 = 20->50->10->30->60->40

    remove_node(&list1, NULL, list1);        // 첫 번째 노드 삭제
    display(list1);            // list1 = 50->10->30->60->40
    remove_node(&list1, search(list1, 60), search(list1, 40));        // 마지막 노드 삭제
    display(list1);            // list1 = 50->10->30->60
    remove_node(&list1, search(list1, 50), search(list1, 10));        // 중간 노드 삭제
    display(list1);            // list1 = 50->30->60

    insert_node(&list2, NULL, create_node(80, NULL));
    insert_node(&list2, NULL, create_node(70, NULL));
    insert_node(&list2, search(list2, 70), create_node(90, NULL));
    display(list2);        // list2 = 79->90->80

    // list1 = list1 + list2
    list1 = concat(list1, list2);
    display(list1);            // list1 = 50->30->60->70->90->80

    // list1을 역순으로
    list1 = reverse(list1);
    display(list1);        // list1 = 80->90->70->60->30->50

    // list1에서 20 탐색
    p = search(list1, 20);
    if (p) {
        printf("탐색 성공: %d\n", p->data);
    }
    else {
        printf("탐색 실패\n");
    }
    free_list(&list1);        // 연결리스트에 있는 동적할당 받은 모든 노드 메모리 해제
    display(list1);            // 아무것도 안 나옴.
}