기본적인 연결리스트를 구현해보자

Node* Create_Node(int newData);
void Destroy_Node(Node* node);
void Append_Node(Node** head, Node* newNode);

연결리스트는 데이터 값을 저장하는 변수와 다음 노드를 가리키는 포인터를 가지고 있는 선형 자료구조이다. 배열과 달리 메모리 공간이 연속적으로 할당하지 않으며, 각 노드들이 포인터로 연결되어 있고 메모리 상으로 불연속적으로 저장되어있다. 또 연결리스트는 동적으로 크기를 조정할 수 있다는 점이 배열과 큰 차이점이다.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { 
	int data; //변수의 값 저장
	struct Node* link; //다음 노드 저장
}Node;

Node* Create_Node(int newData) {
	Node* newNode = (Node*)malloc(sizeof(Node)); //새로운 노드를 동적할당한다.
	newNode->data = newData;
	newNode->link = NULL; //링크를 NULL로 초기화
	return newNode;
}

void Destroy_Node(Node* node) {
	if (node != NULL) { //노드가 존재한다면 free
		free(node);
	}
}

void Append_Node(Node** head, Node* newNode) {
	if (*head == NULL) { //헤드가 NULL일때 = 노드가 존재하지 않을 때
		*head = newNode;
	}
	else
	{
		Node *tail = *head;
		while (tail->link != NULL)
		{
			tail = tail->link; //꼬리를 한 칸씩 전진
		}
		tail->link = newNode; //마지막 노드 뒤에 새로운 노드를 연결
	}
}

void Print_Liked_List(Node* head)
{
	Node* iter = head;
	int i = 0;
	while (iter != NULL) //노드를 끝까지 돌림
	{
		printf("node[%d]:%d", i, iter->data);
		iter = iter->link; //다음 노드로 전진
		if (iter != NULL) printf(" -> ");
		i++;
	}
	printf("\\n");
}

int main() {
	Node* head = NULL;
	Node* newNode = NULL;

	newNode = Create_Node(15);
	Append_Node(&head, newNode);

	newNode = Create_Node(31);
	Append_Node(&head, newNode);

	Print_Liked_List(head);
	return 0;
}

결과

과제에 대한 고찰

자료구조를 배우기전 연결리스트를 접할 때는 그 당시 파이썬을 이용해서 알고리즘을 공부하던 때라 연결리스트의 필요성을 많이 느끼지 못했다. 하지만 C언어 처럼 배열을 정적으로 설정하는 언어에서는 연결리스트의 동적배열이 커다란 장점처럼 느껴졌다. 연결리스트를 구현하면서 포인터 부분에서 아직 부족한 점을 많이 느꼈고 앞으로 공부의 필요성을 많이 느끼게 되었다.