단일 연결리스트(Linked List)
링크드 리스트는 자료 구조 중 하나로, 노드라 불리는 개별 요소들이 데이터와 다음 노드를 가리키는 포인터로 구성되어 선형적으로 연결된 구조를 갖는 것을 말합니다.
C언어에서 링크드 리스트를 구현하기 위해서는 노드를 나타내는 구조체(struct)를 정의하고, 이 구조체를 동적으로 할당하여 노드를 생성합니다. 각 노드는 해당 노드의 데이터와 다음 노드를 가리키는 포인터를 저장하고 있습니다. 이렇게 생성된 노드들은 포인터를 통해 서로 연결됩니다.
예를 들어, 정수형 데이터를 저장하는 링크드 리스트를 구현하려면 다음과 같은 구조체를 정의할 수 있습니다.
typedef struct Node {
int data;
struct Node* next;
} Node;여기서 data는 노드에 저장될 데이터를 나타내고, next는 다음 노드를 가리키는 포인터입니다.
이제 새로운 노드를 동적으로 할당하고 데이터를 저장하는 코드를 작성해보겠습니다.
Node* head = NULL;
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = 10;
newNode->next = NULL;
head = newNode;위 코드에서는 먼저 head 포인터를 초기화합니다. 그리고 새로운 노드를 동적으로 할당하고 데이터를 저장합니다. 마지막으로 head 포인터를 새로운 노드를 가리키도록 업데이트합니다.
이렇게 생성된 링크드 리스트는 새로운 노드를 추가하거나 기존 노드를 삭제하는 등의 연산이 쉽게 가능합니다.
동적 할당을 이용하여 링크드 리스트를 구현하는 과정은 다음과 같습니다.
- 노드를 정의합니다. 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있습니다.
struct node {
int data;
struct node* next;
};- 리스트의 시작 지점을 나타내는 포인터를 선언합니다.
struct node* head = NULL;- 노드를 추가하는 함수를 작성합니다. 이 함수는 새로운 노드를 동적으로 할당하고, 리스트의 시작 지점을 가리키는 포인터가 새로운 노드를 가리키도록 변경합니다.
void add_node(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* current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
}이제 add_node 함수를 호출하여 새로운 노드를 추가하고, print_list 함수를 호출하여 리스트를 출력할 수 있습니다.
add_node(1);
add_node(2);
add_node(3);
print_list(); // 출력: 3 2 1이와 같은 방식으로 동적 할당을 이용한 링크드 리스트를 구현할 수 있습니다. 링크드 리스트는 데이터의 추가, 삭제가 빈번한 경우에 유용하게 사용될 수 있는 자료 구조입니다.
링크드 리스트를 공부하면서 이전에는 배열과 같은 선형 자료구조만 다뤄봤기 때문에 처음에는 포인터 개념과 링크드 리스트의 동작 원리를 이해하는 것이 어려웠습니다. 하지만 여러 자료와 예제들을 참고하며 점점 익숙해지고, 실습을 해보니 이해할 수 있게 되었습니다.
또한 링크드 리스트를 사용하면 메모리를 더 효율적으로 사용할 수 있으며, 원하는 위치에 노드를 추가하거나 삭제할 수 있어서 유용하다는 것을 알게 되었습니다. 이를 통해 배열이나 스택, 큐와 같은 다른 자료구조와는 다른 유용한 기능들을 제공한다는 것을 알게 되었습니다.
그리고 프로그래밍에서는 링크드 리스트를 비롯한 여러 자료구조를 이해하고 활용하는 것이 중요하다는 것을 깨달았습니다. 이를 통해 알고리즘을 더 효율적으로 구현할 수 있고, 복잡한 문제도 해결할 수 있다는 것을 느꼈습니다.
