연결 리스트는 대규모 데이터 저장을 위해 메모리 공간을 효율적으로 활용하는 자료구조입니다. 물리적으로 연속된 메모리 주소가 필요 없이 논리적으로 연속된 구조를 유지할 수 있다는 점이 핵심입니다.
구현 모델 개요 본 구현에서는 두 가지 접근 방식을 다룹니다. 첫 번째는 헤더 노드 방식으로서 별도의 헤더 구조체에链表의 크기와 첫 번째 데이터 노드를 가리키는 포인터를 저장합니다. 두 번째는 헤더 포인터 방식으로서 노드 구조체를 직접 가리키는 포인터 변수 하나로链表을 관리합니다. 두 방식 모두 개별 노드가 다음 노드를 가리키는 포인터를 포함하며, 이 포인터들의 연결을 통해 논리적 연속성을 확보합니다.
데이터 구조 정의 헤더 파일 (linked_list.h)
typedef int data_type;
/* 개별 노드 구조 */
typedef struct list_node {
data_type value;
struct list_node *next;
} ListNode;
/* 헤더 노드 방식용 관리 구조체 */
typedef struct {
ListNode head; /* 내부에 노드 구조체를 포함 */
int size; /* 저장된 노드 개수 추적 */
} HeadList;
/* 헤더 포인터 방식용 관리 구조체 */
typedef struct {
ListNode *first; /* 첫 번째 데이터 노드를 가리키는 포인터 */
int size;
} PtrList;
/* 헤더 노드 방식 함수 원형 */
/* 삽입 인터페이스:_front, _at, _back */
void addFront_H(HeadList *lst, data_type val);
void addAt_H(HeadList *lst, int idx, data_type val);
void addBack_H(HeadList *lst, data_type val);
/* 순회 출력 인터페이스 */
void display_H(HeadList *lst);
/* 삭제 인터페이스 */
void removeVal_H(HeadList *lst, data_type val);
void clear_H(HeadList *lst);
/* 헤더 포인터 방식 함수 원형 */
/* 삽입 인터페이스 */
void addFront_P(PtrList *lst, data_type val);
void addAt_P(PtrList *lst, int idx, data_type val);
void addBack_P(PtrList *lst, data_type val);
/* 순회 출력 인터페이스 */
void display_P(PtrList *lst);
/* 삭제 인터페이스 */
void removeVal_P(PtrList *lst, data_type val);
void clear_P(PtrList *lst);
핵심 구현 로직 소스 파일 (linked_list.c)
#include "linked_list.h"
#include <stdio.h>
#include <stdlib.h>
/* 내부 사용 함수: 새 노드 생성 및 연결 */
static int attachNode(ListNode *prev, data_type val) {
ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
if (newNode == NULL) {
return 0;
}
newNode->value = val;
newNode->next = prev->next;
prev->next = newNode;
return 1;
}
/* 내부 사용 함수: 노드 순회 출력 */
static void traverse(const ListNode *start) {
while (start != NULL) {
printf("%d ", start->value);
start = start->next;
}
printf("\n");
}
/* 내부 사용 함수: 노드 삭제 */
static void detachNode(ListNode *prev) {
ListNode *target = prev->next;
prev->next = target->next;
free(target);
}
/*** 헤더 노드 방식 구현 ***/
void addFront_H(HeadList *lst, data_type val) {
ListNode *prev = &lst->head;
if (attachNode(prev, val)) {
lst->size++;
}
}
void addAt_H(HeadList *lst, int idx, data_type val) {
if (idx < 0 || idx > lst->size) {
return;
}
ListNode *prev = &lst->head;
for (int i = 0; i < idx; i++) {
prev = prev->next;
}
if (attachNode(prev, val)) {
lst->size++;
}
}
void addBack_H(HeadList *lst, data_type val) {
ListNode *prev = &lst->head;
while (prev->next != NULL) {
prev = prev->next;
}
if (attachNode(prev, val)) {
lst->size++;
}
}
void display_H(HeadList *lst) {
printf("HeadList[%d]: ", lst->size);
traverse(lst->head.next);
}
void removeVal_H(HeadList *lst, data_type val) {
ListNode *prev = &lst->head;
while (prev != NULL && prev->next != NULL) {
if (prev->next->value == val) {
detachNode(prev);
lst->size--;
return;
}
prev = prev->next;
}
}
void clear_H(HeadList *lst) {
ListNode *prev = &lst->head;
while (prev->next != NULL) {
detachNode(prev);
lst->size--;
}
printf("Cleared, size = %d\n", lst->size);
}
/*** 헤더 포인터 방식 구현 ***/
/* 더미 노드를 활용하여 헤더 노드 방식과 동일한 로직 적용 */
void addFront_P(PtrList *lst, data_type val) {
ListNode dummy;
dummy.next = lst->first;
ListNode *prev = &dummy;
if (attachNode(prev, val)) {
lst->size++;
lst->first = dummy.next;
}
}
void addAt_P(PtrList *lst, int idx, data_type val) {
if (idx < 0 || idx > lst->size) {
return;
}
ListNode dummy;
dummy.next = lst->first;
ListNode *prev = &dummy;
for (int i = 0; i < idx; i++) {
prev = prev->next;
}
if (attachNode(prev, val)) {
lst->size++;
lst->first = dummy.next;
}
}
void addBack_P(PtrList *lst, data_type val) {
ListNode dummy;
dummy.next = lst->first;
ListNode *prev = &dummy;
while (prev->next != NULL) {
prev = prev->next;
}
if (attachNode(prev, val)) {
lst->size++;
lst->first = dummy.next;
}
}
void display_P(PtrList *lst) {
printf("PtrList[%d]: ", lst->size);
traverse(lst->first);
}
void removeVal_P(PtrList *lst, data_type val) {
ListNode dummy;
dummy.next = lst->first;
ListNode *prev = &dummy;
while (prev != NULL && prev->next != NULL) {
if (prev->next->value == val) {
detachNode(prev);
lst->size--;
lst->first = dummy.next;
return;
}
prev = prev->next;
}
}
void clear_P(PtrList *lst) {
ListNode dummy;
dummy.next = lst->first;
ListNode *prev = &dummy;
while (prev->next != NULL) {
detachNode(prev);
lst->size--;
}
printf("Cleared, size = %d\n", lst->size);
lst->first = NULL;
}
테스트 및 검증 메인 파일 (main.c)
#include "linked_list.h"
#include <stdio.h>
/* 헤더 노드 방식 테스트 */
void testHeadNode() {
HeadList list;
list.size = 0;
list.head.next = NULL;
for (int i = 0; i < 5; i++) {
addBack_H(&list, i + 100);
}
display_H(&list);
addAt_H(&list, 2, 500);
display_H(&list);
removeVal_H(&list, 500);
display_H(&list);
clear_H(&list);
}
/* 헤더 포인터 방식 테스트 */
void testHeadPointer() {
PtrList list;
list.first = NULL;
list.size = 0;
for (int i = 0; i < 5; i++) {
addBack_P(&list, i + 100);
}
display_P(&list);
addAt_P(&list, 2, 500);
display_P(&list);
removeVal_P(&list, 500);
display_P(&list);
clear_P(&list);
}
int main() {
testHeadNode();
printf("----------------------------------------\n");
testHeadPointer();
return 0;
}
실행 결과
HeadList[5]: 100 101 102 103 104
HeadList[5]: 100 101 500 102 103 104
HeadList[4]: 100 101 102 103 104
Cleared, size = 0
----------------------------------------
PtrList[5]: 100 101 102 103 104
PtrList[5]: 100 101 500 102 103 104
PtrList[4]: 100 101 102 103 104
Cleared, size = 0
알고리즘 핵심 포인트 두 구현 방식에서 공통적으로 사용되는 중요한 기법은 이전 노드 포인터(prev)를 활용하는 것입니다. 삽입이나 삭제 위치의 바로 이전 노드를 가리키는 포인터를事先确定하고, 이 포인터를 통해 노드 연결을 변경하면 복잡한 위치 추적 없이 효율적으로操作할 수 있습니다.
특히 헤더 포인터 방식에서는 실제 데이터 노드가 아닌 더미 노드(dummy)를 도입합니다. 이 더미 노드는 구조상 헤더 역할을 하는 가상의 노드로,/front 삽입 시 첫 번째 데이터 노드 앞에 새 노드를 넣어야 하는 경우에도 일관된 로직을 적용할 수 있게 해줍니다.