[C언어 50강] 38강. 연결 리스트(단일): 노드/삽입/삭제/순회 구현

Last updated on 
[C언어 50강] 38강. 연결 리스트(단일): 노드/삽입/삭제/순회 구현

배열 기반 자료구조를 익힌 뒤 연결 리스트를 만나면, 처음에는 오히려 불편하게 느껴질 수 있습니다. 인덱스로 바로 접근도 못 하고, 포인터를 계속 따라가야 하고, 코드도 길어 보이기 때문입니다. 하지만 실제 소프트웨어에서는 “중간 삽입/삭제가 자주 일어나는 데이터”를 다룰 때 연결 리스트 사고방식이 매우 강력합니다. 오늘은 단일 연결 리스트(singly linked list)를 구현 자체보다 왜 이런 구조가 필요한지, 그리고 어떤 불변식을 지켜야 안정적인 코드가 되는지에 초점을 맞춰 정리하겠습니다.

핵심 개념

  • 단일 연결 리스트는 각 노드가 데이터 + 다음 노드 주소(next)를 가지는 선형 구조다.
  • 배열과 달리 물리적으로 연속 메모리가 아니어도 되며, 노드를 동적으로 할당해 크기를 유연하게 늘릴 수 있다.
  • 삽입/삭제의 본질은 “포인터 재연결(re-linking)”이며, 데이터 이동이 아니라 링크 변경이 핵심이다.
  • head(필요하면 tail) 포인터를 어떤 규칙으로 유지하는지가 리스트 안정성을 결정한다.
  • 메모리 할당/해제 정책을 명확히 하지 않으면 누수(leak), 댕글링 포인터, 이중 해제 버그로 바로 이어진다.

개념 먼저 이해하기

연결 리스트를 배울 때 가장 먼저 버려야 할 습관은 “순서가 있으면 인덱스로 접근해야 한다”는 생각입니다. 배열에서는 arr[i]가 자연스럽지만, 연결 리스트에서는 i번째 원소를 찾기 위해 head부터 next를 하나씩 따라가야 합니다. 즉, 연결 리스트는 랜덤 접근(random access)에 강한 구조가 아니라, 순차 접근과 구조 변경(삽입/삭제)에 강한 구조입니다. 이 차이를 이해하지 못하면 리스트를 배열처럼 쓰려고 하다가 성능과 코드 복잡도를 동시에 잃게 됩니다.

그렇다면 왜 굳이 연결 리스트를 쓰는가? 대표 이유는 중간 삽입/삭제 비용 때문입니다. 배열에서 중간에 원소 하나를 넣으려면 뒤쪽 원소를 줄줄이 밀어야 하고, 삭제하려면 당겨야 합니다. 반면 연결 리스트는 삽입/삭제 위치의 “이전 노드”만 알고 있으면 포인터 두세 개만 바꿔 끝납니다. 데이터량이 크거나 이동 비용이 비싼 구조체일수록 이 장점이 큽니다. 핵심은 데이터를 옮기지 않고 연결 관계만 바꾼다는 점입니다.

물론 연결 리스트가 만능은 아닙니다. 각 노드마다 next 포인터를 저장해야 하므로 메모리 오버헤드가 있고, 캐시 지역성(cache locality)도 배열보다 불리합니다. 즉 CPU 입장에서는 연속 메모리를 순차 스캔하는 배열이 더 빠른 경우가 많습니다. 그래서 실무에서는 “삽입/삭제 빈도와 위치”, “순회 패턴”, “메모리/성능 제약”을 보고 구조를 고릅니다. 연결 리스트를 배운다는 건 “무조건 이걸 쓰자”가 아니라, 문제 특성에 맞는 자료구조를 선택하는 기준을 갖추는 일입니다.

단일 연결 리스트 구현에서 반드시 고정해야 할 불변식(invariant)도 있습니다. 첫째, 빈 리스트는 head == NULL이다. 둘째, 리스트의 마지막 노드는 next == NULL이다. 셋째, 어떤 노드도 해제된 메모리를 가리키면 안 된다. 넷째, 리스트를 순회할 때는 반드시 NULL에서 종료돼야 한다(사이클이 생기지 않도록). 이 규칙이 깨지면 증상은 다양하게 나타납니다. 어떤 경우엔 출력이 무한루프에 빠지고, 어떤 경우엔 전혀 다른 함수에서 세그멘테이션 폴트가 납니다. 그래서 리스트 코드는 “동작 예제 한 번 성공”보다, 연산 직후 불변식이 유지되는지를 반복적으로 점검하는 습관이 훨씬 중요합니다.

삽입 연산을 개념적으로 보면 세 단계입니다. (1) 새 노드 생성 및 데이터 저장, (2) 새 노드의 next를 기존 연결로 지정, (3) 이전 노드(또는 head)의 next를 새 노드로 교체. 삭제는 반대로 (1) 우회 링크 연결, (2) 대상 노드 해제. 여기서 순서를 잘못 잡으면 즉시 버그가 납니다. 예를 들어 삭제할 노드를 먼저 free해버리고 나중에 target->next를 읽으려 하면 이미 해제된 메모리에 접근하게 됩니다. 즉 연결 리스트는 포인터 문법보다 연산 순서의 정확성이 더 중요합니다.

또 하나 놓치기 쉬운 부분이 “소유권(ownership)”입니다. 누가 노드를 만들고, 누가 해제할 책임이 있는지 함수 계약에서 명확해야 합니다. 예를 들어 list_push_front가 내부에서 malloc을 했다면, 리스트 전체를 파기하는 list_clear 또는 list_destroy가 반드시 있어야 합니다. 반대로 외부에서 노드를 만들어 전달하는 설계라면, 해제 책임도 문서화해야 합니다. C에서 자료구조 품질은 API 디자인에서 결정됩니다. 코드 몇 줄 줄이는 것보다, 실패 시 반환 정책과 메모리 책임을 분명히 하는 편이 유지보수에 훨씬 큰 가치를 줍니다.

마지막으로, 단일 연결 리스트에서 “이전 노드 접근이 어렵다”는 제약을 의식해야 합니다. 현재 노드만으로는 이전 노드를 알 수 없기 때문에, 특정 노드를 삭제하려면 보통 이전 노드를 함께 추적해야 합니다. 이 제약 때문에 일부 문제에서는 이중 연결 리스트가 더 적합합니다. 오늘 단일 연결 리스트를 정확히 이해하면, 왜 이중 연결 리스트가 존재하는지까지 자연스럽게 이어집니다. 즉 오늘의 목표는 구현 완성 자체보다, 포인터 기반 선형 구조의 사고 체계를 몸에 익히는 것입니다.

기본 사용

예제 1) 최소 단일 연결 리스트: 앞쪽 삽입 + 순회

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

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

Node* list_push_front(Node *head, int value) {
    Node *n = (Node*)malloc(sizeof(Node));
    if (!n) return head; // 실패 시 기존 head 유지

    n->value = value;
    n->next = head;
    return n; // 새 head
}

void list_print(const Node *head) {
    const Node *cur = head;
    while (cur != NULL) {
        printf("%d ", cur->value);
        cur = cur->next;
    }
    printf("\n");
}

void list_clear(Node **head_ref) {
    Node *cur = *head_ref;
    while (cur != NULL) {
        Node *next = cur->next;
        free(cur);
        cur = next;
    }
    *head_ref = NULL;
}

int main(void) {
    Node *head = NULL;

    head = list_push_front(head, 30);
    head = list_push_front(head, 20);
    head = list_push_front(head, 10);

    list_print(head); // 10 20 30
    list_clear(&head);
    return 0;
}

설명:

  • 앞쪽 삽입은 O(1)이며, 기존 head를 새 노드의 next로 연결한 뒤 head를 교체하면 된다.
  • list_clear는 Node**를 받아 마지막에 head를 NULL로 만들면, 호출자 쪽 댕글링 포인터를 예방할 수 있다.
  • malloc 실패 정책을 단순히 “삽입 생략”으로 두었지만, 실무에서는 오류코드/로그 전략을 함께 둔다.

예제 2) 값 기준 삭제: 이전/현재 포인터 동시 추적

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

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

bool list_remove_first(Node **head_ref, int target) {
    if (!head_ref || !(*head_ref)) return false;

    Node *prev = NULL;
    Node *cur = *head_ref;

    while (cur != NULL) {
        if (cur->value == target) {
            if (prev == NULL) {
                // head 삭제
                *head_ref = cur->next;
            } else {
                prev->next = cur->next;
            }
            free(cur);
            return true;
        }
        prev = cur;
        cur = cur->next;
    }
    return false;
}

설명:

  • 단일 연결 리스트 삭제의 핵심은 prev와 cur를 함께 유지하는 것이다.
  • head 삭제는 일반 노드 삭제와 분기 처리해야 하므로, Node**를 받으면 head 갱신이 쉽다.
  • 삭제 순서는 “우회 링크 연결 → free”가 안전하며, free 후 필드 접근은 금지다.

예제 3) 꼬리 삽입 + 길이 계산 + 디버깅 출력

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

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

Node* list_push_back(Node *head, int value) {
    Node *n = (Node*)malloc(sizeof(Node));
    if (!n) return head;
    n->value = value;
    n->next = NULL;

    if (head == NULL) {
        return n;
    }

    Node *cur = head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = n;
    return head;
}

int list_length(const Node *head) {
    int cnt = 0;
    const Node *cur = head;
    while (cur != NULL) {
        cnt++;
        cur = cur->next;
    }
    return cnt;
}

void list_debug(const Node *head) {
    const Node *cur = head;
    while (cur != NULL) {
        printf("[addr=%p value=%d next=%p]\n", (void*)cur, cur->value, (void*)cur->next);
        cur = cur->next;
    }
}

설명:

  • tail 포인터가 없으면 뒤쪽 삽입은 O(n)이다. 삽입이 자주 발생하면 tail 유지 설계를 검토해야 한다.
  • list_debug처럼 주소를 함께 출력하면 링크 끊김/순환 의심 상황을 빠르게 진단할 수 있다.
  • 리스트 길이 함수는 단순하지만, 성능 민감 코드에서 반복 호출하면 전체가 O(n²)로 악화될 수 있어 캐시 전략이 필요할 수 있다.

자주 하는 실수

실수 1) 삭제할 노드를 free한 뒤 next를 읽음

  • 원인: 연산 순서를 정확히 설계하지 않고 즉흥적으로 작성.
  • 해결: 항상 next를 미리 보관하거나 우회 링크를 먼저 연결한 다음 free한다.

실수 2) head 삭제 케이스를 일반 케이스와 동일하게 처리

  • 원인: prev == NULL 분기를 빠뜨림.
  • 해결: head를 수정할 수 있도록 Node** head_ref 인터페이스를 사용하고, 첫 노드 삭제 분기를 명시한다.

실수 3) 리스트 파기 함수 없이 프로그램 종료에만 의존

  • 원인: “짧은 프로그램이니 괜찮다”는 인식.
  • 해결: 생성 함수가 있다면 반드시 대칭되는 clear/destroy 함수를 제공하고 테스트에 포함한다.

실수 4) 순회 종료 조건 실수로 무한 루프 발생

  • 원인: cur = cur->next 갱신 누락 혹은 잘못된 링크 재연결로 사이클 생성.
  • 해결: 디버그 출력에 노드 주소를 포함하고, 삽입/삭제 후 제한된 단계에서 순회 검증을 수행한다.

실무 패턴

  • API는 “행동 + 실패정책 + 소유권”을 함께 문서화한다. (예: malloc 실패 시 false 반환, 노드 해제 책임은 리스트 모듈)
  • head만으로 충분한지, tail/size 캐시가 필요한지 사용 패턴 기준으로 결정한다.
  • 리스트 연산은 단위 테스트에서 경계 케이스를 우선 검증한다: 빈 리스트, 원소 1개, head 삭제, 마지막 노드 삭제.
  • 성능 문제를 체감하면 무조건 미세 최적화하기보다, 먼저 자료구조 선택 자체가 맞는지 재평가한다.
  • 대규모 시스템에서는 연결 리스트 자체보다 “리스트를 감싼 도메인 API”를 안정적으로 설계하는 것이 유지보수 핵심이다.

오늘의 결론

한 줄 요약: 단일 연결 리스트의 본질은 포인터 문법이 아니라, 링크 재연결 순서와 메모리 소유권을 안전하게 통제하는 설계 습관이다.

배열과 연결 리스트는 경쟁 관계가 아니라 용도 분담 관계입니다. 임의 접근이 중요하면 배열, 중간 구조 변경이 중요하면 리스트가 유리할 수 있습니다. 중요한 건 “어떤 상황에서 어떤 비용을 지불하는지”를 이해하고 선택하는 능력입니다.

연습문제

  1. list_insert_after(Node* head, int key, int value)를 구현해 보세요. key를 처음 찾은 노드 뒤에 value를 삽입하고 성공/실패를 반환하도록 설계해 보세요.
  2. 현재 리스트에서 특정 값을 모두 삭제하는 list_remove_all(Node **head_ref, int target)를 작성해 보세요. head가 연속으로 지워지는 케이스를 반드시 통과해야 합니다.
  3. tail 포인터를 포함한 List 구조체(head, tail, size)를 설계하고, push_back을 O(1)로 바꿔 보세요.
  4. 의도적으로 잘못된 링크를 만들어 무한 루프가 나는 테스트를 만든 뒤, 디버그 출력으로 원인을 추적해 보세요.

이전 강의 정답

지난 37강 연습문제의 핵심은 “스택 ADT의 계약을 더 명확하게 만드는 것”이었습니다. 아래는 2번 문제(try_pop + enum 오류코드)의 한 가지 정답 예시입니다.

#include <stdio.h>
#include <stdbool.h>

#define CAP 4

typedef enum {
    STACK_OK = 0,
    STACK_EMPTY,
    STACK_BAD_ARG
} StackResult;

typedef struct {
    int data[CAP];
    int top;
} Stack;

void stack_init(Stack *s) {
    if (!s) return;
    s->top = -1;
}

bool stack_is_empty(const Stack *s) {
    return (!s || s->top < 0);
}

StackResult stack_try_pop(Stack *s, int *out) {
    if (!s || !out) return STACK_BAD_ARG;
    if (stack_is_empty(s)) return STACK_EMPTY;

    *out = s->data[s->top--];
    return STACK_OK;
}

int main(void) {
    Stack s;
    stack_init(&s);

    int v;
    StackResult r = stack_try_pop(&s, &v);
    if (r == STACK_EMPTY) {
        printf("stack is empty\n");
    }
    return 0;
}

해설 포인트:

  • 데이터(-1 등)와 오류 상태를 분리하면 인터페이스 모호성이 줄어든다.
  • 호출자는 switch나 if로 오류 원인을 분기해 로그/복구 전략을 세울 수 있다.
  • 이 패턴은 리스트 삭제/탐색 API에도 그대로 확장 가능하다.

실습 환경/재현 정보

  • 컴파일러: clang 17+ 또는 gcc 13+
  • 컴파일 옵션: -std=c11 -Wall -Wextra -O2 -g
  • 실행 환경: macOS(Apple Silicon), Linux x86_64 터미널
  • 재현 체크:
    • 예제 코드의 삽입/삭제/순회가 경고 없이 컴파일되는지 확인
    • 빈 리스트 삭제, head 삭제, 마지막 노드 삭제 케이스를 모두 검증
    • valgrind(또는 AddressSanitizer)로 메모리 누수/해제 오류가 없는지 점검
    • 디버그 출력에서 마지막 노드의 next == NULL 불변식이 유지되는지 확인