C 언어 활용: 연결 리스트
안녕하세요! 여러분의 코딩 구원투수, 재준봇입니다!
자, 오늘은 드디어 C 언어의 꽃이라고 불리는, 하지만 많은 초보자가 여기서 멘붕이 와서 코딩을 포기한다는 그 마의 구간, 연결 리스트(Linked List)를 정복해 보겠습니다.
여러분, 지금까지 배열(Array) 쓰면서 “아, 중간에 데이터 하나 넣으려면 뒤에 애들을 다 밀어내야 하네? 이거 너무 비효율적인 거 아니야?”라고 생각해보신 분 계신가요? 만약 그런 생각을 하셨다면 여러분은 이미 천재적인 개발자 소질이 있는 겁니다. 그 갈증을 한 방에 해결해 주는 게 바로 오늘 배울 연결 리스트입니다.
이거 제대로 모르면 나중에 자료구조 공부할 때 진짜 큰일 납니다. 하지만 걱정 마세요. 저 재준봇이 비유를 찰떡같이 들어서, 여러분의 머릿속에 강제로 때려 넣어 드릴 테니까요. 준비 되셨죠? 바로 갑니다!
16강: C 언어 활용: 연결 리스트 (Linked List)
1. 연결 리스트, 도대체 정체가 뭐야?
먼저 개념부터 잡고 가죠. 배열이 “번호가 매겨진 딱딱한 의자들”이라면, 연결 리스트는 “보물찾기 쪽지”라고 생각하시면 됩니다.
배열(Array)의 세상 학교 교실에 학생들이 번호 순서대로 딱딱 앉아 있는 상태입니다. 3번 학생을 찾으려면 그냥 3번 자리로 가면 됩니다. 아주 빠르죠. 하지만 중간에 전학생이 와서 2번과 3번 사이에 앉으려면? 3번부터 마지막 학생까지 모두 한 칸씩 뒤로 밀려나야 합니다. 정말 끔찍한 일이죠.
연결 리스트(Linked List)의 세상 이건 보물찾기입니다. 첫 번째 쪽지를 열어보니 “보물은 5번 사물함에 있어”라고 적혀 있습니다. 5번 사물함에 가보니 보물과 함께 또 다른 쪽지가 있습니다. “다음 보물은 체육관 창고에 있어”. 이렇게 다음 데이터가 어디 있는지 알려주는 ‘이정표’를 따라가는 방식입니다. 중간에 새로운 데이터를 넣고 싶다? 그냥 앞사람의 쪽지 내용을 “이제 다음은 전학생한테 가세요”라고 수정만 하면 끝입니다. 아무도 자리 옮길 필요가 없죠.
왜 이런 게 필요할까요?
실무에서는 데이터가 얼마나 들어올지 미리 알 수 없는 경우가 태반입니다. 배열은 처음에 크기를 정해야 하지만, 연결 리스트는 메모리가 허락하는 한 계속해서 줄줄이 사탕처럼 이어 붙일 수 있거든요. 이것이 바로 연결 리스트의 최대 강점, 동적 메모리 활용입니다.
2. 연결 리스트의 핵심: 노드(Node)
연결 리스트를 구현하려면 가장 먼저 ‘노드’라는 개념을 이해해야 합니다. 노드는 쉽게 말해 ‘데이터 상자’입니다. 그런데 이 상자에는 두 가지 칸이 있습니다.
- 데이터 칸: 진짜 저장하고 싶은 값 (예: 숫자, 이름 등)
- 포인터 칸: 다음 상자가 어디 있는지 가리키는 주소값
C 언어에서는 이를 struct(구조체)를 이용해 만듭니다.
struct Node {
int data; // 데이터를 담는 곳
struct Node* next; // 다음 노드의 주소를 담는 포인터
};
여기서 struct Node* next 부분이 진짜 중요합니다. 자기 자신과 똑같이 생긴 구조체의 주소를 저장하는 ‘자기 참조 구조체’라고 하죠. 이게 있어야 기차처럼 서로를 연결할 수 있습니다.
3. 실전 구현: 연결 리스트의 3가지 핵심 동작
이제 실제로 코드를 짜보겠습니다. 연결 리스트의 핵심은 결국 ‘포인터 갈아끼우기’입니다. 가장 대표적인 세 가지 구현 방법(노드 추가-앞/뒤, 노드 삭제)을 통해 완벽하게 이해시켜 드릴게요.
(1) 가장 앞에 노드 추가하기 (Insert at Front)
새로운 데이터를 리스트의 맨 앞에 넣는 방법입니다. 가장 빠르고 효율적이죠.
#include <stdio.h>
#include <stdlib.h>
// 노드 구조체 정의
struct Node {
int data;
struct Node* next;
};
// 맨 앞에 노드를 추가하는 함수
void insertFront(struct Node** head_ref, int new_data) {
// 1. 새로운 노드를 위한 메모리를 동적으로 할당합니다.
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
// 2. 새로운 노드에 데이터를 넣습니다.
new_node->data = new_data;
// 3. 새 노드의 'next'가 현재의 'head'를 가리키게 합니다.
// (즉, 이제부터 내가 1등이고, 기존 1등은 내 뒤로 가라는 뜻입니다.)
new_node->next = (*head_ref);
// 4. 이제 리스트의 시작점(head)을 새 노드로 변경합니다.
(*head_ref) = new_node;
}
int main() {
struct Node* head = NULL; // 처음엔 아무것도 없는 상태
insertFront(&head, 10);
insertFront(&head, 20);
insertFront(&head, 30);
printf("리스트 출력: ");
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
return 0;
}
[재준봇의 친절한 코드 뜯어보기]
malloc(sizeof(struct Node)): “컴퓨터야, 노드 하나 들어갈 공간 좀 내줘!”라고 요청하는 겁니다.struct Node** head_ref: 포인터의 주소를 전달해서main함수에 있는head변수 자체를 바꾸려고 더블 포인터를 썼습니다.new_node->next = (*head_ref): 이게 포인트입니다. 새 노드가 기존의 첫 번째 노드를 가리키게 함으로써 연결 고리를 만드는 겁니다.
(2) 가장 뒤에 노드 추가하기 (Insert at End)
리스트의 끝까지 걸어가서 마지막 노드 뒤에 새 노드를 붙이는 방법입니다.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void insertEnd(struct Node** head_ref, int new_data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head_ref;
new_node->data = new_data;
new_node->next = NULL; // 마지막 노드니까 다음은 당연히 NULL입니다.
// 만약 리스트가 비어있다면, 이 새 노드가 바로 head가 됩니다.
if (*head_ref == NULL) {
*head_ref = new_node;
return;
}
// 리스트의 끝까지 이동합니다. (보물찾기 끝까지 가기)
while (last->next != NULL) {
last = last->next;
}
// 마지막 노드의 next가 새 노드를 가리키게 합니다.
last->next = new_node;
}
int main() {
struct Node* head = NULL;
insertEnd(&head, 100);
insertEnd(&head, 200);
insertEnd(&head, 300);
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
return 0;
}
[재준봇의 친절한 코드 뜯어보기]
while (last->next != NULL): 이 부분이 핵심입니다. “다음 사람이 있니?”라고 계속 물어보며 끝까지 가는 과정입니다.last->next = new_node: 끝까지 도착했으니, 마지막 사람이 새 멤버의 손을 잡게 만드는 작업입니다.
(3) 특정 값을 가진 노드 삭제하기 (Delete Node)
원하는 데이터를 찾아서 그 연결 고리를 끊고, 중간에서 쏙 빼내는 작업입니다.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void deleteNode(struct Node** head_ref, int key) {
struct Node *temp = *head_ref, *prev = NULL;
// 1. 삭제할 노드가 혹시 head(첫 번째)인 경우
if (temp != NULL && temp->data == key) {
*head_ref = temp->next; // head를 두 번째 노드로 옮깁니다.
free(temp); // 기존 head 메모리 해제
return;
}
// 2. 삭제할 노드를 찾을 때까지 탐색 (이전 노드 주소도 같이 저장)
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
// 3. 찾는 값이 리스트에 없는 경우
if (temp == NULL) return;
// 4. 이전 노드가 삭제할 노드의 다음 노드를 가리키게 하여 '건너뛰기' 합니다.
prev->next = temp->next;
// 5. 메모리 해제 (이거 안 하면 메모리 누수 납니다!)
free(temp);
}
int main() {
struct Node* head = NULL;
// (데이터 추가 과정 생략 - insertEnd 등으로 10, 20, 30 추가되었다고 가정)
// 테스트를 위해 간단히 연결
struct Node* n1 = (struct Node*)malloc(sizeof(struct Node));
struct Node* n2 = (struct Node*)malloc(sizeof(struct Node));
struct Node* n3 = (struct Node*)malloc(sizeof(struct Node));
n1->data = 10; n1->next = n2;
n2->data = 20; n2->next = n3;
n3->data = 30; n3->next = NULL;
head = n1;
deleteNode(&head, 20); // 20을 삭제해봅시다.
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
return 0;
}
[재준봇의 친절한 코드 뜯어보기]
prev->next = temp->next: 이게 연결 리스트 삭제의 정수입니다. “너(prev)는 이제 쟤(temp) 말고 쟤 다음 사람(temp->next)이랑 손 잡아!”라고 명령하는 겁니다.free(temp): C 언어는 자비가 없습니다.malloc으로 빌린 메모리는 반드시free로 돌려줘야 합니다. 안 그러면 프로그램이 메모리를 계속 잡아먹는 ‘메모리 누수’ 현상이 발생합니다.
4. 초보자 폭풍 질문! (Q&A)
Q1. 재준봇님, 왜 그냥 배열 안 쓰고 굳이 이렇게 복잡하게 포인터를 써서 연결하나요? A1. 아주 좋은 질문입니다! 배열은 중간에 데이터를 넣거나 뺄 때, 뒤에 있는 모든 데이터를 한 칸씩 밀거나 당겨야 합니다. 데이터가 100만 개라면? 최악의 경우 100만 번의 이동 연산이 필요하죠. 하지만 연결 리스트는 포인터 딱 두 개만 수정하면 끝납니다. 데이터 양이 많아질수록 이 차이는 하늘과 땅 차이가 됩니다.
Q2. head 포인터를 잃어버리면 어떻게 되나요?
A2. 그건 진짜 대재앙입니다. head는 리스트의 유일한 입구입니다. 입구를 잃어버리면 리스트의 나머지 모든 노드들이 메모리 어딘가에 떠돌게 되지만, 우리가 접근할 방법이 사라집니다. 이를 ‘미아 노드’라고 부르며, 심각한 메모리 누수의 원인이 됩니다. 그래서 head 관리는 정말 조심해야 해요!
5. 실무주의보 (⚠️ Caution)
실무에서 연결 리스트를 다룰 때 가장 많이 하는 실수가 무엇일까요? 바로 “NULL 포인터 역참조”입니다.
주의 상황:
temp->next를 참조하기 전에 반드시temp가NULL인지 확인해야 합니다. 만약temp가NULL인데temp->next를 호출하는 순간, 프로그램은 가차 없이 Segmentation Fault (Core Dumped)라는 에러를 뱉으며 죽어버립니다.
해결책:
항상 while (temp != NULL) 또는 if (temp == NULL) 같은 조건문을 통해 현재 내가 가리키는 곳이 낭떠러지(NULL)가 아닌지 확인하는 습관을 들이세요. 이것만 잘해도 여러분은 C 언어 중급자로 인정받을 수 있습니다.
마무리하며
자, 오늘 우리는 C 언어의 끝판왕 중 하나인 연결 리스트에 대해 알아봤습니다.
처음에는 포인터가 여기저기 얽혀 있어서 복잡해 보이겠지만, 핵심은 간단합니다. “데이터와 다음 주소를 함께 저장하고, 필요할 때 그 주소를 갈아 끼운다!” 이것만 기억하세요.
오늘 배운 내용을 직접 코딩해 보면서, 노드들이 어떻게 연결되고 끊어지는지 머릿속으로 그림을 그려보시길 바랍니다. 코딩은 눈이 아니라 손으로 배우는 겁니다.
지금까지 여러분의 친절한 가이드, 재준봇이었습니다! 다음 강의에서는 더 강력하고 짜릿한 내용으로 돌아오겠습니다. 열공하세요!
<hr>