C언어 연결 리스트 (Linked List)
요약
C언어 연결 리스트의 기본 개념과 순회 방법을 알아봅니다. 정보처리기사 실기에 자주 출제되는 연결 리스트 순회 문제를 풀기 위한 핵심 개념을 정리합니다.
연결 리스트 핵심 정리
| 개념 | 설명 | 예시 |
|---|---|---|
| 노드(Node) | 데이터와 다음 노드 주소를 가진 구조체 | struct Node { int x; struct Node* next; }; |
| NULL | 리스트의 끝을 표시 | next = NULL 또는 next = 0 |
| 순회(Traversal) | 리스트의 모든 노드를 방문 | while (curr) { curr = curr->next; } |
| 연쇄 접근 | 포인터를 따라 여러 노드를 거쳐 접근 | head->next->data |
| 뒤집기(Reverse) | next 방향만 거꾸로 돌려 순서 반전 | prev/curr/next 3포인터 → 상세 |
연결 리스트란?
연결 리스트 (Linked List)는 각 요소(노드)가 데이터와 다음 노드의 주소를 함께 저장하는 자료구조입니다.
배열과 달리 메모리에 연속적으로 저장되지 않고, 포인터로 연결됩니다. 연결 리스트는 구조체와 포인터를 함께 사용하므로, 아직 익숙하지 않다면 해당 페이지를 먼저 읽고 돌아오세요.
struct Node* next는 같은 타입(struct Node)의 다른 노드를 가리키는 포인터입니다. 이처럼 자기 자신과 같은 타입의 포인터를 멤버로 가지는 것을 자기참조 구조체라고 합니다. 이 포인터를 통해 노드끼리 서로 연결됩니다.
노드를 먼저 생성하고 나중에 연결하는 방식도 있습니다. 실기 문제에서 자주 출제되는 형태입니다.
&는 주소 연산자로, &t2는 t2의 메모리 주소를 의미합니다. t3.next = &t2는 t3의 next에 t2의 주소를 저장하여 두 노드를 연결합니다.
연결 리스트 순회
순회 (Traversal)는 리스트의 모든 노드를 처음부터 끝까지 방문하는 것입니다.
위에서 만든 연결 리스트를 순회하면서 각 노드의 데이터를 출력해봅시다.
아래 코드에서 curr->x의 -> (화살표 연산자)는 포인터가 가리키는 구조체의 멤버에 접근하는 연산자입니다. curr->x는 "curr이 가리키는 노드의 x 값"을 의미합니다.
실행 과정:
| 반복 | curr | curr->x | curr->next | 출력 |
|---|---|---|---|---|
| 1회 | &t3 | 11 | &t2 | 11 |
| 2회 | &t2 | 7 | &t1 | 7 |
| 3회 | &t1 | 5 | NULL | 5 |
| 종료 | NULL | - | - | - |
최종 출력: 11 7 5
while(curr)의 의미
while문은 조건이 참인 동안 계속 반복합니다. curr이 유효한 주소를 가리키면 참이므로 반복을 계속하고, curr이 NULL이 되면 거짓이므로 반복을 멈춥니다.
구조체 초기화에서 struct Node t1 = { 0, 5u };처럼 next에 0을 넣으면 NULL 포인터를 의미합니다. 이 노드가 리스트의 마지막 노드가 되어 순회가 여기서 끝납니다.
연쇄 화살표 연산자 접근
연결 리스트에서 화살표 연산자(->)를 연속으로 사용하여 여러 노드를 거쳐 데이터에 접근할 수 있습니다.
head->n2->n1의 의미
head->n2->n1은 왼쪽에서 오른쪽으로 순서대로 해석합니다.
| 단계 | 표현 | 의미 | 결과 |
|---|---|---|---|
| 1 | head | head 포인터 | &a (a의 주소) |
| 2 | head->n2 | head가 가리키는 노드(a)의 n2 | &b (b의 주소) |
| 3 | head->n2->n1 | 그 노드(b)의 n1 | 20 |
다양한 접근 예시
단계별로 풀어서 해석하기
연쇄 화살표 표현이 길어지면, 각 단계를 하나씩 풀어서 해석하면 실수를 줄일 수 있습니다.
->가 3단 이상 연결되어도 같은 방식으로 왼쪽부터 한 단계씩 풀어가면 됩니다.
(&변수)->멤버가 변수.멤버와 같아지는 이유는, &변수가 해당 변수의 주소이고, -> 연산자가 그 주소에 있는 구조체의 멤버에 접근하기 때문입니다. 결국 같은 구조체의 같은 멤버를 가리키므로 결과가 동일합니다.
한 단계 더: 연결 리스트 뒤집기
순회까지 익혔다면 다음은 노드 순서를 거꾸로 바꾸는 in-place 알고리즘입니다. 새 노드를 만들지 않고 prev/curr/next 3포인터로 각 노드의 next 방향만 뒤집어 같은 메모리에서 리스트를 반대로 만듭니다.
단계별 다이어그램과 변수 추적은 연결 리스트 뒤집기 페이지에서 다룹니다.