연결리스트 삽입·삭제·정렬

# 연결리스트 삽입·삭제·정렬

## 왜 연결리스트인가

배열은 크기가 고정이고, 중간 삽입·삭제 시 요소를 밀어야 한다. 연결리스트는 포인터로 연결되므로 삽입·삭제가 O(1)이지만 임의 접근이 O(n)이다. 임베디드에서는 큐·이벤트 버퍼·디바이스 드라이버 목록에 쓰인다.

---

## 기본 구조

```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node {
    int         id;
    char        name[32];
    struct Node *next;   /* 자기 참조 포인터 */
} Node;
```

---

## 삽입

### 앞에 삽입 (Prepend)

```c
Node *prepend(Node *head, int id, const char *name) {
    Node *n = (Node *)malloc(sizeof(Node));
    if (!n) return head;
    n->id   = id;
    strncpy(n->name, name, 31);
    n->name[31] = '\0';
    n->next = head;
    return n;   /* 새 헤드 반환 */
}
```

### 정렬 삽입 (id 오름차순 유지)

```c
Node *insert_sorted(Node *head, int id, const char *name) {
    Node *n = (Node *)malloc(sizeof(Node));
    if (!n) return head;
    n->id = id;
    strncpy(n->name, name, 31);
    n->name[31] = '\0';

/* 삽입 위치 탐색 */
    if (!head || head->id >= id) {
        n->next = head;
        return n;
    }
    Node *cur = head;
    while (cur->next && cur->next->id < id) {
        cur = cur->next;
    }
    n->next   = cur->next;
    cur->next = n;
    return head;
}
```

---

## 삭제

```c
Node *delete_by_id(Node *head, int id) {
    if (!head) return NULL;

/* 헤드 삭제 */
    if (head->id == id) {
        Node *tmp = head->next;
        free(head);
        return tmp;
    }
    /* 중간/끝 삭제 */
    Node *cur = head;
    while (cur->next && cur->next->id != id) {
        cur = cur->next;
    }
    if (cur->next) {
        Node *tmp  = cur->next;
        cur->next  = tmp->next;
        free(tmp);
    }
    return head;
}
```

---

## 전체 해제

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

연결리스트를 쓰면 **반드시 free_list를 호출**해야 메모리 누수가 없다.

---

## 사용 예

```c
int main(void) {
    Node *list = NULL;
    list = insert_sorted(list, 3, "Park");
    list = insert_sorted(list, 1, "Kim");
    list = insert_sorted(list, 2, "Lee");

for (Node *p = list; p; p = p->next) {
        printf("[%d] %s\n", p->id, p->name);
    }
    /* 출력: [1]Kim [2]Lee [3]Park */

list = delete_by_id(list, 2);
    free_list(list);
    return 0;
}
```

---

## 임베디드에서의 주의점

MCU에서 `malloc`/`free`를 반복하면 힙 단편화가 발생한다. 동적 할당 대신 정적 풀(static pool)에서 노드를 가져오는 방식을 쓴다.

```c
#define POOL_SIZE 16
static Node  node_pool[POOL_SIZE];
static bool  pool_used[POOL_SIZE] = {false};

Node *pool_alloc(void) {
    for (int i = 0; i < POOL_SIZE; i++) {
        if (!pool_used[i]) {
            pool_used[i] = true;
            memset(&node_pool[i], 0, sizeof(Node));
            return &node_pool[i];
        }
    }
    return NULL;   /* 풀 고갈 */
}

void pool_free(Node *n) {
    int idx = (int)(n - node_pool);
    if (idx >= 0 && idx < POOL_SIZE) pool_used[idx] = false;
}
```

연결리스트 삽입·삭제·정렬

// COMMENTS

ON THIS PAGE