C 링크드 리스트 구현

임베디드에서 링크드 리스트는 동적 크기의 데이터 관리에 사용한다. malloc/free 기반, 메모리 풀 기반, 침투형(intrusive) 등 구현 방식에 따라 특성이 크게 다르다.

Singly Linked List

typedef struct node {
    int data;
    struct node *next;
} node_t;

node_t *list_prepend(node_t *head, int data) {
    node_t *new = malloc(sizeof(node_t));
    new->data = data;
    new->next = head;
    return new;
}

node_t *list_find(node_t *head, int data) {
    for (node_t *cur = head; cur != NULL; cur = cur->next) {
        if (cur->data == data) return cur;
    }
    return NULL;
}

node_t *list_remove(node_t *head, int data) {
    node_t **pp = &head;
    while (*pp) {
        if ((*pp)->data == data) {
            node_t *del = *pp;
            *pp = del->next;
            free(del);
            return head;
        }
        pp = &(*pp)->next;
    }
    return head;
}

void list_destroy(node_t *head) {
    while (head) {
        node_t *next = head->next;
        free(head);
        head = next;
    }
}

이중 포인터(node_t **pp) 삭제 패턴: head 노드와 중간 노드를 동일한 코드로 삭제할 수 있다. pp는 “이 노드를 가리키는 포인터”를 가리킨다. head의 경우 &head, 나머지는 &prev->next다.

Doubly Linked List

typedef struct dnode {
    int data;
    struct dnode *prev;
    struct dnode *next;
} dnode_t;

void dlist_insert_after(dnode_t *node, dnode_t *new) {
    new->prev = node;
    new->next = node->next;
    if (node->next) node->next->prev = new;
    node->next = new;
}

void dlist_remove(dnode_t *node) {
    if (node->prev) node->prev->next = node->next;
    if (node->next) node->next->prev = node->prev;
    free(node);
}

삭제 시 prev 포인터로 이전 노드에 직접 접근하므로 탐색이 필요 없다. 대신 노드당 포인터 2개(8~16바이트)를 소비한다.

	Singly	Doubly
노드 크기	data + 포인터 1개	data + 포인터 2개
삭제	O(n) 탐색 필요 (또는 이중 포인터)	O(1) 직접 삭제
역방향 순회	불가	가능

침투형 리스트 (Intrusive Linked List)

Linux 커널의 list_head 패턴이다. 리스트 노드가 데이터를 포함하는 대신, 데이터 구조체가 리스트 노드를 포함한다.

// 리스트 노드 (데이터 없음)
typedef struct list_head {
    struct list_head *prev;
    struct list_head *next;
} list_head_t;

// 데이터 구조체가 리스트 노드를 내장
typedef struct {
    int id;
    char name[32];
    list_head_t list;  // 리스트 연결용
} device_t;

// container_of: 멤버 포인터로 부모 구조체 포인터를 역산
#define container_of(ptr, type, member) \
    ((type *)((char *)(ptr) - offsetof(type, member)))

// 사용
void print_devices(list_head_t *head) {
    for (list_head_t *pos = head->next; pos != head; pos = pos->next) {
        device_t *dev = container_of(pos, device_t, list);
        printf("device: %d %s\n", dev->id, dev->name);
    }
}

왜 침투형인가

일반 리스트:

[node] → data_ptr → [device_t]
[node] → data_ptr → [sensor_t]

침투형 리스트:

[device_t 내부의 list_head] ↔ [device_t 내부의 list_head]

• 별도 할당 불필요: 데이터 구조체만 할당하면 리스트 노드가 포함되어 있다
• 타입 무관: list_head는 어떤 구조체에든 내장할 수 있다
• 다중 리스트: 하나의 구조체에 list_head를 여러 개 두면 동시에 여러 리스트에 속할 수 있다
• 간접 참조 없음: container_of는 컴파일 타임 포인터 산술이다

Linux 커널에서 10,000곳 이상 사용되는 패턴이다.

메모리 풀 기반 할당

임베디드에서는 malloc/free 반복으로 인한 힙 파편화가 문제가 된다. 메모리 풀은 노드 크기의 블록을 미리 할당하고, free list로 관리한다.

#define POOL_SIZE 32

typedef struct pool_node {
    int data;
    struct pool_node *next;
} pool_node_t;

static pool_node_t pool[POOL_SIZE];
static pool_node_t *free_list = NULL;

void pool_init(void) {
    for (int i = 0; i < POOL_SIZE - 1; i++) {
        pool[i].next = &pool[i + 1];
    }
    pool[POOL_SIZE - 1].next = NULL;
    free_list = &pool[0];
}

pool_node_t *pool_alloc(void) {
    if (!free_list) return NULL;  // 풀 고갈
    pool_node_t *node = free_list;
    free_list = free_list->next;
    return node;
}

void pool_free(pool_node_t *node) {
    node->next = free_list;
    free_list = node;
}

• 할당/해제 모두 O(1)
• 파편화 없음
• 최대 개수가 컴파일 타임에 결정됨

메모

• list_destroy에서 free(head) 후 head = head->next를 하면 use-after-free다. 반드시 next를 먼저 저장한다
• 이중 포인터 삭제 패턴은 Linus Torvalds가 “좋은 코드와 나쁜 코드의 차이”로 언급한 패턴이다
• container_of의 offsetof는 <stddef.h>에 정의되어 있다. 표준 C다
• 메모리 풀에서 pool_alloc 실패(NULL 반환) 처리를 빠뜨리면 NULL 역참조 크래시가 발생한다
• 임베디드에서 malloc을 사용하더라도, 초기화 시점에만 할당하고 런타임에는 해제하지 않는 패턴이 안전하다. 해제가 필요하면 메모리 풀을 사용한다