링크드 리스트는 데이터 요소들을 노드라 부르는 객체로 유지하는 자료구조이다. 이 노드들은 각자 다음 노드를 가리키는 포인터를 갖고 있어, 연결 리스트를 형성한다.
링크드 리스트의 기본 개념
링크드 리스트는 순차적 접근이 용이하며, 동적 크기를 가지기 때문에 유연하게 데이터를 삽입 및 삭제할 수 있다.
노드 구조체
링크드 리스트의 노드는 데이터와 다음 노드를 가리키는 포인터로 구성된 구조체이다. 예제 코드를 통해 쉽게 이해할 수 있다.
struct Node {
int data;
struct Node* next;
};메모리 레이아웃
링크드 리스트의 메모리 레이아웃은 다음과 같은 형태로 시각화할 수 있다:
[Head] -> [Data|Next] -> [Data|Next] -> [Data|Next] -> NULL링크드 리스트의 초기화
링크드 리스트를 구현하기 위해 먼저 리스트를 초기화해야 한다. 초기화하는 방법은 매우 간단하다.
struct Node* head = NULL;노드 추가
새로운 노드를 링크드 리스트에 추가하는 과정 역시 중요하다. 우리는 리스트의 끝에 노드를 추가하는 예제를 살펴볼 것이다.
가장 끝에 노드 추가하기
리스트 끝에 노드를 추가하는 함수는 다음과 같다:
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);
}링크드 리스트의 검색
마지막으로, 링크드 리스트에서 특정 값을 가진 노드를 검색하는 방법을 알아보자.
노드 검색하기
검색 함수는 다음과 같다:
struct Node* search(struct Node* head, int key) {
struct Node* current = head;
while (current != NULL) {
if (current->data == key)
return current;
current = current->next;
}
return NULL;
}예제 코드 종합
위의 예제를 종합하여 통합적인 예제 코드를 작성해보자:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
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);
}
struct Node* search(struct Node* head, int key) {
struct Node* current = head;
while (current != NULL) {
if (current->data == key)
return current;
current = current->next;
}
return NULL;
}
int main() {
struct Node* head = NULL;
append(&head, 1);
append(&head, 2);
append(&head, 3);
printf("Linked List created: ");
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
deleteNode(&head, 2);
printf("Linked List after deletion of 2: ");
temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
struct Node* found = search(head, 3);
if (found != NULL) printf("Element 3 found in the list.\n");
else printf("Element 3 not found in the list.\n");
return 0;
}