단일 연결 리스트(Singly Linked List) - C언어 구현

연결 리스트: 노드를 연결해서 만든 리스트

• 노드는 데이터 필드와 다음 노드에 대한 포인터로 구성
• 첫 번째 노드를 헤드(head), 마지막 노드를 테일(tail)이라고 함
• 장점: 배열에 비해 추가/삽입/삭제 연산이 쉬움
• 단점: 탐색이 오래걸림(헤드부터 순차적 탐색), 포인터 크기만큼의 추가 메모리가 노드 수만큼 필요
  
  

---

0. 노드 구조체

typedef struct Node {
    int data;
    struct Node* nextNode;
} Node;

---

1. 노드 생성

Node* CreateNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->nextNode = NULL;
    return newNode;
}

---

2. 리스트 비었는지 검사

int IsEmpty(Node* list) {
    if(list == NULL) {
        printf("빈 리스트입니다.\n");
        return 0;
    }
    return 0;
}

---

3. 노드 삭제

Node* RemoveNode(Node** head, int data) {
    if(IsEmpty(*head)) return NULL;
    // 삭제 원하는 데이터 검색
    Node* target = SearchNode(*head, data);
    if(target == NULL) return NULL;
    
    if(*head == target) *head = target->nextNode;
    else {
        Node* current = *head;
        while(current->nextNode != target) {
            current = current->nextNode;
        }
        current->nextNode = target->nextNode;
    }
    target->nextNode = NULL;
    return target;
}

void DestroyNode(Node* target) {
	free(target);
}

---

4. 노드 검색

Node* SearchNode(Node* list, int data) {
    if(IsEmpty(list)) return NULL;
    
    while(list != NULL) {
        if(list->data == data) return list;
        list = list->nextNode;
    }
    
    printf("검색 결과 없음.\n");
    return NULL;
}

---

5. 노드 추가

void AppendNode(Node** head, Node* newNode) {
    if(*head == NULL) *head = newNode;
    else {
        Node* tail = *head;
        while(tail->nextNode != NULL) tail = tail->nextNode;
        tail->nextNode = newNode;
    }
}

---

6. 리스트 출력

void PrintList(Node* current) {
    if(!IsEmpty(current)) {
        while(current != NULL) {
            printf("[%p] %d [%p]\n", current, current->data, current->nextNode);
            current = current->nextNode;
        }
    }
}

---

7. 리스트 삭제

void DestroyList(Node** head) {
    Node* remove = *head;
    Node* next = *head;
    while(remove != NULL) {
        next = next->nextNode;
        free(remove);
        remove = next;
    }
    *head = NULL;
}

---

8. 예시

int main(void)
{
    Node* list = NULL;
    Node* newNode = NULL;
    int input, data;

    newNode = CreateNode(10);
    AppendNode(&list, newNode);
    newNode = CreateNode(20);
    AppendNode(&list, newNode);
    newNode = CreateNode(30);
    AppendNode(&list, newNode);
    PrintList(list);

    DestroyNode(RemoveNode(&list, 10));
    PrintList(list);
    DestroyNode(RemoveNode(&list, 30));
    PrintList(list);
    DestroyNode(RemoveNode(&list, 20));
    PrintList(list);

    DestroyList(&list);
    return 0;
}