연결 리스트(Linked List)란?
연결 리스트는 동적 메모리 할당을 기반으로 구현되는 자료구조로, 여러 개의 노드(Node)가 서로 연결되어 이루어진 집합입니다. 배열과 달리 크기를 미리 정하지 않아도 되므로, 필요할 때마다 메모리를 할당해 유연하게 데이터를 관리할 수 있습니다.
노드는 크게 두 부분으로 구성됩니다.
- 데이터(data) : 실제로 저장할 값
- 링크(link) : 다음 노드의 주소를 가리키는 포인터
연결 리스트의 종류
C 언어에서 구현할 수 있는 대표적인 연결 리스트는 다음과 같습니다.
- 단일 연결 리스트(Singly Linked List)
- 이중 연결 리스트(Doubly Linked List)
- 원형 단일 연결 리스트(Circular Singly Linked List)
- 원형 이중 연결 리스트(Circular Doubly Linked List)
단일 연결 리스트의 구조
단일 연결 리스트는 가장 기본적인 형태의 연결 리스트로, 각 노드가 하나의 링크만 가지고 있어 한 방향으로만 탐색이 가능합니다. 아래 그림은 단일 연결 리스트의 구조를 나타낸 것입니다.
예제 : 숫자를 역순으로 출력하는 C 프로그램
다음은 단일 연결 리스트를 사용해 입력받은 숫자들을 역순으로 출력하는 C 프로그램입니다. 노드 생성, 리스트 출력, 리스트 뒤집기의 세 가지 함수로 구성되어 있습니다.
#include <stdio.h>
#include <stdlib.h>
struct node {
int num;
struct node *nextptr;
}*stnode;
void createNodeList(int n);
void reverseDispList();
void displayList();
int main(){
int n;
printf("\n\n 단일 연결 리스트 : 역순으로 출력하기 :\n");
printf("------------------------------------------------------------------------------\n");
printf(" 노드의 개수를 입력하세요 : ");
scanf("%d", &n);
createNodeList(n);
printf("\n 리스트에 입력된 데이터 : \n");
displayList();
reverseDispList();
printf("\n 역순으로 뒤집힌 리스트 : \n");
displayList();
return 0;
}
void createNodeList(int n){
struct node *fnNode, *tmp;
int num, i;
stnode = (struct node *)malloc(sizeof(struct node));
if(stnode == NULL) {
printf(" 메모리를 할당할 수 없습니다.");
}
else{
// 키보드로부터 첫 번째 노드의 데이터를 입력받음
printf(" 노드 1의 데이터 입력 : ");
scanf("%d", &num);
stnode->num = num;
stnode->nextptr = NULL;
tmp = stnode;
// n개의 노드를 생성하여 연결 리스트에 추가
for(i=2; i<=n; i++){
fnNode = (struct node *)malloc(sizeof(struct node));
if(fnNode == NULL) {
printf(" 메모리를 할당할 수 없습니다.");
break;
}
else{
printf(" 노드 %d의 데이터 입력 : ", i);
scanf(" %d", &num);
fnNode->num = num;
fnNode->nextptr = NULL;
tmp->nextptr = fnNode;
tmp = tmp->nextptr;
}
}
}
}
void reverseDispList(){
struct node *prevNode, *curNode;
if(stnode != NULL){
prevNode = stnode;
curNode = stnode->nextptr;
stnode = stnode->nextptr;
prevNode->nextptr = NULL; // 첫 번째 노드를 마지막 노드로 변경
while(stnode != NULL){
stnode = stnode->nextptr;
curNode->nextptr = prevNode;
prevNode = curNode;
curNode = stnode;
}
stnode = prevNode; // 마지막 노드를 새로운 헤드로 변경
}
}
void displayList(){
struct node *tmp;
if(stnode == NULL){
printf(" 리스트에 데이터가 없습니다.");
}
else{
tmp = stnode;
while(tmp != NULL){
printf(" Data = %d\n", tmp->num);
tmp = tmp->nextptr;
}
}
}프로그램 동작 원리
- createNodeList() : 사용자로부터 노드 개수와 각 노드의 데이터를 입력받아 malloc()으로 메모리를 동적으로 할당하고, 노드들을 순서대로 연결해 리스트를 생성합니다.
- displayList() : 첫 번째 노드부터 마지막 노드까지 순차적으로 순회하면서 각 노드의 데이터를 화면에 출력합니다.
- reverseDispList() : 포인터 세 개(prevNode, curNode, stnode)를 활용해 각 노드의 링크 방향을 반대로 바꿉니다. 그 결과 첫 번째 노드는 마지막 노드가 되고, 기존의 마지막 노드는 새로운 헤드(head)가 되어 리스트 전체가 뒤집힙니다.
실행 결과
위 프로그램을 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.
단일 연결 리스트 : 역순으로 출력하기 : ------------------------------------------------------------------------------ 노드의 개수를 입력하세요 : 5 노드 1의 데이터 입력 : 12 노드 2의 데이터 입력 : 45 노드 3의 데이터 입력 : 11 노드 4의 데이터 입력 : 9 노드 5의 데이터 입력 : 10 리스트에 입력된 데이터 : Data = 12 Data = 45 Data = 11 Data = 9 Data = 10 역순으로 뒤집힌 리스트 : Data = 10 Data = 9 Data = 11 Data = 45 Data = 12