연결 리스트 기초

기본 패턴

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

typedef struct Node {
    int          val;
    struct Node *next;
} Node;

// 앞에 삽입 — O(1)
Node *push_front(Node *head, int val) {
    Node *n = malloc(sizeof(Node));
    if (!n) return head;
    n->val  = val;
    n->next = head;
    return n;   // 새 헤드 반환
}

// 순회
void print_list(const Node *head) {
    for (const Node *cur = head; cur != NULL; cur = cur->next)
        printf("%d ", cur->val);
    printf("\n");
}

설명

자기 참조 구조체

연결 리스트의 노드는 자기 자신과 같은 타입의 포인터를 멤버로 갖습니다. typedef 완성 전에 자기 참조가 필요하므로 포인터 타입에는 struct Node *를 사용합니다.

typedef struct Node {
    int          val;
    struct Node *next;   // ✅ struct Node * — typedef 완성 전이라 Node * 불가
} Node;

// 마지막 노드의 next는 항상 NULL (리스트 끝 표시)
Node *head = NULL;   // 빈 리스트

앞 삽입과 뒤 삽입

// 앞 삽입 — O(1): 새 노드 → 기존 head
Node *push_front(Node *head, int val) {
    Node *n = malloc(sizeof(Node));
    if (!n) return head;
    n->val = val; n->next = head;
    return n;
}

// 뒤 삽입 — O(n): tail까지 순회
Node *push_back(Node *head, int val) {
    Node *n = malloc(sizeof(Node));
    if (!n) return head;
    n->val = val; n->next = NULL;

    if (!head) return n;

    Node *tail = head;
    while (tail->next) tail = tail->next;
    tail->next = n;
    return head;
}

포인터-투-포인터로 삭제

삭제할 노드가 헤드일 수도 있으므로 Node **로 받으면 헤드 교체도 동일하게 처리할 수 있습니다.

// 값이 val인 첫 번째 노드 삭제
void delete_val(Node head, int val) {
    Node cur = head;
    while (*cur) {
        if ((*cur)->val == val) {
            Node *del = *cur;
            *cur = del->next;   // 이전 노드의 next를 건너뜀
            free(del);
            return;
        }
        cur = &(*cur)->next;
    }
}

// 사용 예
Node *list = NULL;
list = push_front(list, 3);
list = push_front(list, 2);
list = push_front(list, 1);   // 1 → 2 → 3

delete_val(&list, 2);          // 1 → 3
print_list(list);

전체 해제

리스트를 다 쓴 후 모든 노드를 free해야 합니다.

void free_list(Node *head) {
    while (head) {
        Node *next = head->next;
        free(head);
        head = next;
    }
}

빠른 정리

상황	방법
앞에 삽입	`new->next = head; head = new;` — O(1)
뒤에 삽입	tail까지 순회 후 연결 — O(n)
헤드 포함 삭제	`Node **` 포인터-투-포인터 패턴
배열 vs 연결 리스트	임의 접근 필요 → 배열, 잦은 삽입/삭제 → 연결 리스트
메모리 해제	`free_list`로 모든 노드 순회 해제

주의할 점

다음 노드 포인터를 저장하지 않고 free하면 이미 해제된 메모리에서 next를 읽게 됩니다.

// ❌ free 후 next 접근 — use-after-free
void free_list_bad(Node *head) {
    while (head) {
        free(head);
        head = head->next;   // ❌ 이미 해제된 메모리에서 읽음
    }
}

// ✅ next를 먼저 저장
void free_list_good(Node *head) {
    while (head) {
        Node *next = head->next;   // ✅ 먼저 저장
        free(head);
        head = next;
    }
}

삽입 함수에서 malloc 실패 시 기존 head를 그대로 반환해 리스트가 유지되도록 해야 합니다.