C 언어 단일 연결 리스트
단일 연결 리스트(Single Linked List)는 노드(Node)라는 구조체에 데이터와 다음 노드를 가리키는 포인터를 갖는 자료 구조입니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터를 가지고 있고, 마지막 노드는 다음 노드를 가리키는 포인터가 NULL이 됩니다. 이렇게 구성된 단일 연결 리스트는 데이터의 삽입, 삭제, 검색이 빠르다는 장점을 가지고 있지만, 데이터의 크기에 따라 저장 공간이 많이 필요한 단점이 있습니다.
C 언어 코드로 표현하면 다음과 같습니다.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
int main() {
struct Node *head = NULL;
head = (struct Node*) malloc(sizeof(struct Node));
head->data = 1;
head->next = NULL;
return 0;
}
위 코드는 단일 연결 리스트의 가장 간단한 예시입니다. head 포인터가 가리키는 노드가 단일 연결 리스트의 첫 번째 노드입니다.
첫 번째 노드의 데이터 값은 1이고, 다음 노드를 가리키는 포인터가 NULL입니다.
다음 노드를 추가하려면, 다음과 같이 새 노드를 동적할당하고, 첫 번째 노드의 next 포인터를 새 노드로 업데이트하면 됩니다.
struct Node *second = NULL;
second = (struct Node*) malloc(sizeof(struct Node));
second->data = 2;
second->next = NULL;
head->next = second;
새로운 노드를 추가할 때마다 마지막 노드의 next 포인터를 새 노드로 업데이트하면 단일 연결 리스트가 생성됩니다.
단일 연결 리스트에서 데이터를 검색하려면, 첫 번째 노드부터 끝까지 노드를 순회하면서 각 노드의 데이터를 비교하여 원하는 데이터를 찾으면 됩니다.
int search(struct Node *head, int x) {
struct Node *current = head;
while (current != NULL) {
if (current->data == x)
return 1;
current = current->next;
}
return 0;
}
위와 같은 방식으로 단일 연결 리스트에서 데이터를 삭제하려면, 삭제하려는 노드의 이전 노드와 다음 노드를 찾아, 이전 노드의 next 포인터를 삭제하려는 노드의 다음 노드로 업데이트하면 됩니다.
void deleteNode(struct Node *head, int x) {
struct Node *current = head;
struct Node *previous = NULL;
while (current != NULL) {
if (current->data == x) {
if (previous == NULL) {
head = current->next;
free(current);
return;
} else {
previous->next = current->next;
free(current);
return;
}
}
previous = current;
current = current->next;
}
}
위와 같이 구현하면, 단일 연결 리스트에서 데이터를 삭제할 수 있습니다.
단일 연결 리스트의 크기는 각 노드를 순회하면서 노드의 개수를 세면서 구할 수 있습니다.
int getCount(struct Node *head) {
int count = 0;
struct Node *current = head;
while (current != NULL) {
count++;
current = current->next;
}
return count;
}
위와 같이 구현하면, 단일 연결 리스트의 크기를 구할 수 있습니다.
다음은 C언어에서 "단일 연결 리스트"를 구현하는 간단한 예제입니다.
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
void insert_at_beginning(int data) {
struct node *new_node = (struct node*) malloc(sizeof(struct node));
new_node->data = data;
new_node->next = head;
head = new_node;
}
void print_list() {
struct node *temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int main() {
insert_at_beginning(3);
insert_at_beginning(2);
insert_at_beginning(1);
print_list();
return 0;
}
위의 코드에서 struct node 구조체는 "단일 연결 리스트"의 노드를 나타냅니다. 각 노드는 int 형 data 필드와 next 필드(다음 노드의 주소)를 가집니다. head 포인터는 리스트의 첫 번째 노드를 가리킵니다. insert_at_beginning 함수는 리스트의 첫 번째에 새 노드를 추가하는 것입니다. print_list 함수는 리스트의 내용을 출력하는 것입니다.