[자료구조] 연결 리스트(Linked List) 개념 정리 및 C 구현

1. 리스트의 분류

자료구조는 크게 선형과 비선형으로 나뉩니다.

선형 리스트 (Linear List)

• Stack
• Queue
• List

연결 리스트 (Linked List)

• Stack, Queue, List 등을 '노드(Node)'를 사용하여 구현
• 단순 연결 리스트, 단순 선형 연결 리스트 등이 있음

비선형 리스트 (Non-Linear List)

• Tree
• Graph

---

2. 연결 리스트의 구조와 노드(Node)

연결 리스트는 데이터와 주소(Link)를 담은 노드들의 연결로 이루어집니다.

노드(Node)의 특징

• [ data | link ] 구조로 되어 있음
• data: 실제 저장할 값 (정수, 실수, 문자열 등)
• link: 다음 노드의 주소를 저장하는 포인터 변수
• 데이터를 가지고 있지 않으면 노드로서의 의미가 없음

C언어에서의 구현

• 서로 다른 데이터 타입을 묶어야 하므로 구조체(struct) 사용이 필수적입니다.

    struct listNode {
        char data[4];
        struct listNode* link;
    };

헤드 노드(Head Node)

• 리스트의 시작 위치를 알려주는 기준 노드입니다.
• 데이터는 저장하지 않고, 첫 번째 노드의 주소만 보관합니다.

    typedef struct {
        listNode* head;
    } linkedList_h;

---

3. 새로운 노드 삽입 프로세스

1. 삽입할 노드를 준비하고 데이터 필드에 값을 저장합니다.
2. 이전 노드(pre)가 가리키던 주소를 새 노드의 링크에 저장합니다.
3. 이전 노드의 링크가 새 노드를 가리키도록 업데이트합니다.

---

4. C언어 구현 코드

(1) 헤더 파일: InsertLinkedList.h

	#pragma once

    typedef struct ListNode {
        char data[4];
        struct ListNode* link;
    } listNode;

    typedef struct {
        listNode* head;
    } linkedList_h;

    linkedList_h* createLinkedList_h(void);
    void freeLinkedList_h(linkedList_h* L);
    void printList(linkedList_h* L);
    void insertFirstNode(linkedList_h* L, char* x);
    void insertMiddleNode(linkedList_h* L, listNode* pre, char* x);
    void insertLastNode(linkedList_h* L, char* x);

(2) 소스 파일: InsertLinkedList.c

	#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include "InsertLinkedList.h"

    // 리스트 생성
    linkedList_h* createLinkedList_h(void) {
        linkedList_h* L;
        L = (linkedList_h*)malloc(sizeof(linkedList_h));
        L->head = NULL;
        return L;
    }

    // 메모리 해제
    void freeLinkedList_h(linkedList_h* L) {
        listNode* p;
        while (L->head != NULL) {
            p = L->head;
            L->head = L->head->link;
            free(p);
            p = NULL;
        }
    }

    // 리스트 출력
    void printList(linkedList_h* L) {
        listNode* p;
        printf("L = (");
        p = L->head;
        while (p != NULL) {
            printf("%s", p->data);
            p = p->link;
            if (p != NULL) printf(", ");
        }
        printf(") \n");
    }

    // 첫 번째 노드로 삽입
    void insertFirstNode(linkedList_h* L, char* x) {
        listNode* newNode;
        newNode = (listNode*)malloc(sizeof(listNode));
        strcpy(newNode->data, x);
        newNode->link = L->head;
        L->head = newNode;
    }

    // 중간 삽입 (pre 노드 뒤)
    void insertMiddleNode(linkedList_h* L, listNode* pre, char* x) {
        listNode* newNode;
        newNode = (listNode*)malloc(sizeof(listNode));
        strcpy(newNode->data, x);
        if (L->head == NULL) {
            newNode->link = NULL;
            L->head = newNode;
        }
        else if (pre == NULL) {
            newNode->link = L->head;
            L->head = newNode;
        }
        else {
            newNode->link = pre->link;
            pre->link = newNode;
        }
    }

    // 마지막 노드로 삽입
    void insertLastNode(linkedList_h* L, char* x) {
        listNode* newNode;
        listNode* temp;
        newNode = (listNode*)malloc(sizeof(listNode));
        strcpy(newNode->data, x);
        newNode->link = NULL;
        if (L->head == NULL) {
            L->head = newNode;
            return;
        }
        temp = L->head;
        while (temp->link != NULL) temp = temp->link;
        temp->link = newNode;
    }

(3) 실행 파일: sampleLink.c

    #include <stdio.h>
    #include "InsertLinkedList.h"

    int main(void) {
        linkedList_h* L;
        L = createLinkedList_h();
        printf("(1) 공백 리스트 생성하기! \n");
        printList(L);

        printf("\n(2) 리스트에 [수] 노드 삽입하기! \n");
        insertFirstNode(L, "수");
        printList(L);

        printf("\n(3) 리스트 마지막에 [금] 노드 삽입하기! \n");
        insertLastNode(L, "금");
        printList(L);

        printf("\n(4) 리스트 첫 번째에 [월] 노드 삽입하기! \n");
        insertFirstNode(L, "월");
        printList(L);

        printf("\n(5) 리스트 공간을 해제하여 공백 리스트로 만들기! \n");
        freeLinkedList_h(L);
        printList(L);

        return 0;
    }