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 |
연결 리스트란?
연결 리스트(Linked List) 는 각 요소(노드)가 데이터와 다음 노드의 주소를 함께 저장하는 자료구조입니다.
배열과 달리 메모리에 연속적으로 저장되지 않고, 포인터로 연결됩니다.
노드를 먼저 생성하고 나중에 연결하는 방식도 있습니다. 실기 문제에서 자주 출제되는 형태입니다.
연결 리스트 순회
순회(Traversal) 는 리스트의 모든 노드를 처음부터 끝까지 방문하는 것입니다.
위에서 만든 연결 리스트를 순회하면서 각 노드의 데이터를 출력해봅시다.
실행 과정:
| 반복 | 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)은 while (curr != NULL)과 같습니다. C언어에서 NULL은 0이고, 0은 거짓(false)으로 평가됩니다.
연쇄 화살표 연산자 접근
연결 리스트에서 화살표 연산자(->)를 연속으로 사용하여 여러 노드를 거쳐 데이터에 접근할 수 있습니다.
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 |
다양한 접근 예시
연결 리스트 노드 값 스왑
연결 리스트를 순회하면서 인접한 두 노드의 값을 교환(스왑) 하는 패턴입니다. 노드 자체를 교환하는 것이 아니라 노드 안의 데이터 값만 교환합니다.
스왑의 원리
스왑은 임시 변수를 사용해 두 값을 교환하는 기본 알고리즘입니다.
연결 리스트에서는 n->v와 n->next->v를 스왑합니다.
실행 과정 예시
연결 리스트: n1(1) -> n3(3) -> n2(2) -> NULL
| 반복 | n 위치 | n->v | n->next->v | 스왑 후 | 다음 n |
|---|---|---|---|---|---|
| 1회 | n1 | 1 | 3 | n1.v=3, n3.v=1 | n2 |
| 2회 | n2 | - | NULL | 조건 거짓, 종료 | - |
최종 리스트: n1(3) -> n3(1) -> n2(2) -> NULL
while 조건의 의미
n != NULL: 현재 노드가 존재하는지 확인n->next != NULL: 다음 노드가 존재하는지 확인 (스왑 대상)
두 조건 모두 만족해야 스왑이 가능합니다. 하나라도 NULL이면 스왑할 쌍이 없으므로 종료합니다.