C 언어로 링크드 리스트 쉽게 배우기
링크드 리스트는 C 언어에서 중요한 자료구조 중 하나입니다. 이 글에서는 C 링크드 리스트를 쉽게 이해하고 구현하는 방법을 친근하게 설명합니다. 링크드 리스트의 기본 개념부터 실습 예제까지, 단계별로 배워보세요!
링크드 리스트란?
링크드 리스트는 노드라는 개별 요소들이 포인터를 통해 서로 연결된 선형 자료구조입니다. 각 노드는 데이터를 저장하는 데이터 필드와 다음 노드를 가리키는 포인터 필드로 구성됩니다. 배열과 달리, 링크드 리스트는 동적으로 크기를 변경할 수 있어 유연성이 뛰어납니다.
링크드 리스트의 구조
링크드 리스트의 기본 구조는 다음과 같습니다
struct Node {
int data; // 데이터 필드
struct Node* next; // 포인터 필드
};노드 생성
노드는 struct를 사용하여 정의됩니다. 각 노드는 데이터를 저장하는 data 필드와 다음 노드를 가리키는 next 포인터를 가집니다.
리스트 초기화
링크드 리스트는 일반적으로 헤드 포인터를 통해 관리됩니다. 헤드 포인터는 리스트의 첫 번째 노드를 가리키며, 리스트가 비어 있으면 NULL 값을 가집니다.
struct Node* head = NULL;링크드 리스트 구현
노드 추가
링크드 리스트에 노드를 추가하는 방법에는 리스트의 앞에 추가하는 방법과 리스트의 끝에 추가하는 방법이 있습니다.
리스트의 앞에 추가
void push(struct Node** head_ref, int new_data) {
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}리스트의 끝에 추가
void append(struct Node** head_ref, int new_data) {
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
struct Node* last = *head_ref;
new_node->data = new_data;
new_node->next = NULL;
if (*head_ref == NULL) {
*head_ref = new_node;
return;
}
while (last->next != NULL) {
last = last->next;
}
last->next = new_node;
}노드 삭제
링크드 리스트에서 노드를 삭제하는 방법에는 특정 값을 가진 노드를 삭제하는 방법이 있습니다.
void deleteNode(struct Node** head_ref, int key) {
struct Node* temp = *head_ref, *prev;
if (temp != NULL && temp->data == key) {
*head_ref = temp->next;
free(temp);
return;
}
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) return;
prev->next = temp->next;
free(temp);
}리스트 출력
링크드 리스트의 모든 노드를 순차적으로 출력하는 함수는 다음과 같습니다
void printList(struct Node* node) {
while (node != NULL) {
printf("%d -> ", node->data);
node = node->next;
}
printf("NULL\n");
}링크드 리스트 사용 예제
이제 링크드 리스트의 기본 동작을 살펴보겠습니다. 아래 예제는 링크드 리스트에 노드를 추가하고, 삭제하며, 출력하는 과정을 보여줍니다.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void push(struct Node** head_ref, int new_data) {
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void append(struct Node** head_ref, int new_data) {
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
struct Node* last = *head_ref;
new_node->data = new_data;
new_node->next = NULL;
if (*head_ref == NULL) {
*head_ref = new_node;
return;
}
while (last->next != NULL) {
last = last->next;
}
last->next = new_node;
}
void deleteNode(struct Node** head_ref, int key) {
struct Node* temp = *head_ref, *prev;
if (temp != NULL && temp->data == key) {
*head_ref = temp->next;
free(temp);
return;
}
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) return;
prev->next = temp->next;
free(temp);
}
void printList(struct Node* node) {
while (node != NULL) {
printf("%d -> ", node->data);
node = node->next;
}
printf("NULL\n");
}
int main() {
struct Node* head = NULL;
append(&head, 1);
append(&head, 2);
push(&head, 3);
push(&head, 4);
printf("Created Linked list ");
printList(head);
deleteNode(&head, 3);
printf("Linked list after deletion of 3 ");
printList(head);
return 0;
}링크드 리스트의 장점과 단점
장점
- 동적 크기 조정 배열과 달리 링크드 리스트는 동적으로 크기를 변경할 수 있습니다.
- 효율적인 삽입 및 삭제 특정 위치에서의 삽입 및 삭제가 배열보다 효율적입니다.
단점
- 메모리 사용량 증가 각 노드는 추가적인 포인터 필드를 가지므로 메모리 사용량이 증가합니다.
- 랜덤 접근 불가능 배열과 달리 인덱스를 사용한 랜덤 접근이 불가능하여, 특정 위치에 접근하려면 순차적으로 탐색해야 합니다.
결론
링크드 리스트는 C 언어에서 매우 중요한 자료구조로, 동적 메모리 할당을 통해 유연한 데이터 처리가 가능합니다. 이 글을 통해 링크드 리스트의 기본 개념과 구현 방법을 이해하고, 직접 실습해보세요. 이제 자신 있게 링크드 리스트를 활용할 수 있을 것입니다!
여기까지가 링크드 리스트에 대한 모든 내용이었습니다. 링크드 리스트의 구조와 구현 방법을 잘 이해하고, 실습을 통해 더욱 깊이 있는 학습을 해보세요. Happy coding!
댓글