#include <stdlib.h>

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

int push_front(Node head, int value) {
    if (head == NULL) return 0;

    Node *node = malloc(sizeof *node);
    if (node == NULL) return 0;
    node->val = value;
    node->next = *head;
    *head = node;           /* head 자체를 바꾼다. */
    return 1;
}

void free_all(Node head) {
    if (head == NULL) return;

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

문법

head 포인터가 바뀌는지 아닌지가 연결 리스트 코드의 첫 번째 분기입니다. 앞 삽입과 head 삭제는 포인터 자체를 다시 연결해야 하므로 여기서 코드가 많이 갈립니다.

빈 리스트는 head == NULL로 표현합니다. delete_val은 이 상태를 자연스럽게 처리하지만, 중복 값에서 첫 노드만 지울지 전부 지울지와, caller가 삭제 뒤 head 값을 어떻게 계속 사용할지를 API 계약으로 정합니다.

앞 삽입은 새 노드가 새 head가 됩니다.

Node *push_front(Node *head, int val) {
    Node *n = malloc(sizeof(Node));
    if (n == NULL) {
        return head;
    }

    n->val = val;
    n->next = head;
    return n;
}

삭제도 head가 바뀔 수 있으면 Node ** 패턴이 강합니다.

void delete_val(Node head, int val) {
    Node cur = head;

    while (*cur != NULL) {
        if ((*cur)->val == val) {
            Node *victim = *cur;
            *cur = victim->next;
            free(victim);
            return;
        }
        cur = &(*cur)->next;
    }
}

이 패턴의 장점은 "head 삭제"와 "중간 삭제"를 같은 코드로 처리한다는 점입니다.

순회와 해제

순회:

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

해제:

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

해제에서 중요한 것은 free 전에 다음 포인터를 저장하는 것입니다.

앞 삽입은 node allocation이 성공하고 head 주소를 알고 있을 때 O(1)입니다. 특정 노드의 삭제도 이전 링크를 알고 있을 때만 O(1)이며, 값으로 노드를 찾는 비용과 tail을 유지하는 비용은 별도입니다. free_list 뒤 caller의 head도 NULL로 만들려면 Node **를 받아 *head = NULL로 갱신합니다.

빠른 점검

• 인덱스로 바로 접근해야 하면 배열
• 중간 삽입/삭제가 더 중요하면 연결 리스트
• head가 바뀌면 Node ** 패턴이 강하다
• 해제 전에 next를 먼저 저장한다

다만 C에서는 연결 리스트가 메모리 할당/해제 책임까지 같이 와서, 단순히 "삽입이 편하다"만 보고 쓰기엔 비용이 큽니다.

주의할 점