연결 리스트는 문법보다 head 변경, 순회, 해제 책임이 더 중요합니다.
- head가 바뀌는 삭제/삽입에서 왜
Node **가 필요한지 다시 보고 싶다 - 배열 대신 연결 리스트를 쓰는 이유를 짧게 정리하고 싶다
- 순회는 되는데 해제나 삭제에서 자꾸 터진다
숏컷 코드
c
typedef struct Node {
int val;
struct Node *next;
} Node;연결 리스트는 결국 "다음 노드 주소를 저장하는 구조체의 사슬"입니다.
- 임의 접근은 느림
- 중간 삽입/삭제는 링크 조정으로 해결
문법
head 포인터가 바뀌는지 아닌지가 연결 리스트 코드의 첫 번째 분기입니다. 앞 삽입과 head 삭제는 포인터 자체를 다시 연결해야 하므로 여기서 코드가 많이 갈립니다.
앞 삽입은 새 노드가 새 head가 됩니다.
c
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 ** 패턴이 강합니다.
c
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 삭제"와 "중간 삭제"를 같은 코드로 처리한다는 점입니다.
순회와 해제
순회:
c
for (Node *cur = head; cur != NULL; cur = cur->next) {
printf("%d\n", cur->val);
}해제:
c
void free_list(Node *head) {
while (head != NULL) {
Node *next = head->next;
free(head);
head = next;
}
}해제에서 중요한 것은 free 전에 다음 포인터를 저장하는 것입니다.
체크포인트
- 인덱스로 바로 접근해야 하면 배열
- 중간 삽입/삭제가 더 중요하면 연결 리스트
- head가 바뀌면
Node **패턴이 강하다 - 해제 전에
next를 먼저 저장한다
다만 C에서는 연결 리스트가 메모리 할당/해제 책임까지 같이 와서, 단순히 "삽입이 편하다"만 보고 쓰기엔 비용이 큽니다.
주의할 점
연결 리스트 버그는 보통 "문법"이 아니라 소유권과 포인터 갱신 순서에서 납니다. 특히 삭제에서 링크를 먼저 끊을지, 해제를 먼저 할지 순서를 잘못 잡으면 use-after-free가 바로 나옵니다.