연결 리스트(Linked List)란?
연결 리스트는 동적 메모리 할당(dynamic memory allocation) 방식을 사용하는 자료구조로, 데이터의 양에 따라 크기가 유연하게 늘어나거나 줄어듭니다. 연결 리스트는 여러 개의 노드(node)가 모여 이루어진 집합체로 정의되며, 각 노드는 데이터(data)와 링크(link)라는 두 부분으로 구성됩니다.
데이터, 링크, 그리고 연결 리스트의 전체 구조는 아래 그림과 같이 표현됩니다.
연결 리스트의 주요 연산
C 언어에서 연결 리스트에 수행할 수 있는 대표적인 연산은 다음 세 가지입니다.
- 삽입(Insertion) — 리스트에 새로운 노드를 추가
- 삭제(Deletion) — 리스트에서 기존 노드를 제거
- 순회(Traversing) — 리스트의 각 노드를 처음부터 끝까지 차례대로 방문
삽입(Insertion)의 세 가지 위치
먼저 노드 2와 노드 3 사이에 노드 5를 삽입하는 예시를 살펴보겠습니다.
다음은 노드 5를 리스트의 맨 앞에 삽입하는 경우입니다.
이어서 노드 5를 리스트의 맨 끝에 삽입하는 경우입니다.
마지막으로 노드 5를 끝에 삽입한 최종 결과입니다.
참고 사항:
- 각 노드에는 이름이 없기 때문에 노드 2 앞에 곧바로 노드 5를 삽입할 수 없습니다.
- 하지만 노드 2의 위치(position)가 주어진다면, 그 앞에 노드 5를 삽입하는 것이 가능합니다.
C 언어 구현 프로그램
다음은 연결 리스트에 요소를 삽입하는 전체 C 언어 프로그램입니다. 맨 앞 삽입(insert_front), 맨 끝 삽입(insert_end), 특정 값 뒤 삽입(insert_after), 특정 값 앞 삽입(insert_before) 네 가지 함수를 모두 포함하고 있습니다.
#include <stdio.h>
#include <stdlib.h>
struct node{
int val;
struct node *next;
};
void print_list(struct node *head){
printf("H->");
while(head){
printf("%d->", head->val);
head = head->next;
}
printf("……
");
}
void insert_front(struct node **head, int value){
struct node * new_node = NULL;
new_node = (struct node *)malloc(sizeof(struct node));
if (new_node == NULL){
printf(" Out of memory");
}
new_node->val = value;
new_node->next = *head;
*head = new_node;
}
void insert_end(struct node **head, int value){
struct node * new_node = NULL;
struct node * last = NULL;
new_node = (struct node *)malloc(sizeof(struct node));
if (new_node == NULL){
printf(" Out of memory");
}
new_node->val = value;
new_node->next = NULL;
if( *head == NULL){
*head = new_node;
return;
}
last = *head;
while(last->next) last = last->next;
last->next = new_node;
}
void insert_after(struct node *head, int value, int after){
struct node * new_node = NULL;
struct node *tmp = head;
while(tmp) {
if(tmp->val == after) { /*found the node*/
new_node = (struct node *)malloc(sizeof(struct node));
if (new_node == NULL) {
printf("Out of memory");
}
new_node->val = value;
new_node->next = tmp->next;
tmp->next = new_node;
return;
}
tmp = tmp->next;
}
}
void insert_before(struct node **head, int value, int before){
struct node * new_node = NULL;
struct node * tmp = *head;
new_node = (struct node *)malloc(sizeof(struct node));
if (new_node == NULL){
printf("Out of memory");
return;
}
new_node->val = value;
if((*head)->val == before){
new_node->next = *head;
*head = new_node;
return;
}
while(tmp && tmp->next) {
if(tmp->next->val == before) {
new_node->next = tmp->next;
tmp->next = new_node;
return;
}
tmp = tmp->next;
}
/*Before node not found*/
free(new_node);
}
void main(){
int count = 0, i, val, after, before;
struct node * head = NULL;
printf("Enter no: of elements: ");
scanf("%d", &count);
for (i = 0; i < count; i++){
printf("Enter %dth element: ", i);
scanf("%d", &val);
insert_front(&head, val);
}
printf("starting list: ");
print_list(head);
printf("enter front element: ");
scanf("%d", &val);
insert_front(&head, val);
printf("items after insertion: ");
print_list(head);
printf("enter last element: ");
scanf("%d", &val);
insert_end(&head, val);
printf("items after insertion: ");
print_list(head);
printf("Enter an ele to insert in the list: ");
scanf("%d", &val);
printf("Insert after: ");
scanf("%d", &after);
insert_after(head, val, after);
printf("List after insertion: ");
print_list(head);
printf("Enter an ele to insert in the list: ");
scanf("%d", &val);
printf("Insert before: ");
scanf("%d", &before);
insert_before(&head, val, before);
printf("List after insertion: ");
print_list(head);
}실행 결과(Output)
위 프로그램을 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다. 입력한 요소들이 맨 앞 삽입 방식으로 역순 저장된 후, 앞·뒤·특정 위치 삽입이 순차적으로 적용되는 과정을 확인할 수 있습니다.
Enter no: of elements: 4 Enter 0th element: 1 Enter 1th element: 2 Enter 2th element: 3 Enter 3th element: 4 starting list: H->4->3->2->1->...... enter front element: 5 items after insertion: H->5->4->3->2->1->...... enter last element: 0 items after insertion: H->5->4->3->2->1->0->...... Enter an ele to insert in the list: 6 Insert after: 0 List after insertion: H->5->4->3->2->1->0->6->...... Enter an ele to insert in the list: 7 Insert before: 5 List after insertion: H->7->5->4->3->2->1->0->6->......