C언어로 Single Linked List 구현하기

C언어로 Single Linked List를 구현해보자.

(풀 코드는 맨 밑)

 

C언어에서 여러 값을 저장하기 위해 주로 배열을 사용한다.

이 배열은 메모리 크기가 정해져 있어 정해진 크기보다 많은 값을 저장할 수 없다.

 

그러나 Single Linked List는 값의 개수와 상관없이 값을 저장할 수 있다.

 

Single Linked List의 기본적인 구조는 다음과 같다.

리스트 구조

값을 저장할 공간과 다음 리스트를 가르키는 포인터를 담는 공간으로 구성되어 있다.

 

이를 연결하면 다음과 같다.

리스트

이 Single Linked List의 3가지 기능을 구현해보자.

1. List의 끝에 원하는 데이터을 가진 리스트를 추가하기

2. 원하는 위치에 리스트 추가하기

3. 원하는 위치의 리스트를 삭제하기

 

먼저 리스트의 기본 형태와 기준점을 만들자.

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

typedef struct Node_s
{
	struct Node_s* Next;
	int Data;
} Node_t;

int main(void)
{
	Node_t* list = malloc(sizeof(Node_t));
	list->Next = NULL;
	list->Data = 0;
	return 0;
}

Node_s라는 구조체에 

데이터를 담을 int Data와 다음 구조체의 주소를 저장할 Next라는 변수를 만들었다.

 

또한 리스트의 접근하기 위한 기준점인 Node_t* list를 만들었다.

Node_s 구조체를 list라는 이름으로 만든 것이다.

 

기본값으로 list의 다음 노드는 NULL을 가르키고,

데이터는 0이 들어간다.

 

 

1. List의 끝에 원하는 데이터을 가진 리스트를 추가하기

void Append(Node_t* head, int data) {
	Node_t* newnode = malloc(sizeof(Node_t));
	newnode->Next = NULL;
	newnode->Data = data;

	for (;head->Next != NULL; head = head->Next);

	head->Next = newnode;
    return;
}

head는 main에서의 list를 넣으면 되고, data는 리스트에 저장할 값을 넣으면 된다.

 

추가할 노드를 Node_s 구조체의 형태를 가진 newnode로 할당하자.

이 newnode에 다음 노드는 NULL이며,

저장할 데이터는 data의 값을 가진다.

 

리스트의 가장 끝에 노드를 추가하므로 리스트의 끝으로 가야한다.

리스트의 끝은 NULL을 가르킨다는 특징이 있기에

for (;head->Next != NULL; head = head->Next);

를 이용해 리스트의 끝으로 이동할 수 있다.

 

리스트의 끝 노드의 next를 newnode로 바꿔주면 끝이다!

head->Next = newnode;

 

 

2. 원하는 위치에 리스트 추가하기

//index번째 노드 추가
void Insert(Node_t* head, unsigned int index, int data) {
	Node_t* newnode = malloc(sizeof(Node_t));
	newnode->Data = data;

	for (int i = 0; i < index - 1; head = head->Next, i++);

	Node_t* nextnode = head->Next;

	head->Next = newnode;
	newnode->Next = nextnode;
	return;
}

index는 원하는 위치의 값을 넣고, data는 리스트에 저장할 값을 넣으면 된다.

다음은 원하는 위치에 노드를 추가하는 방법은 다음 그림과 같다.

원하는 위치에 노드 삽입 순서도

newnode라는 새로운 노드를 할당한다.

 

추가될 위치의 노드 이전의 노드에 접근해야 하므로

for (int i = 0; i < index - 1; head = head->Next, i++);

를 통해 원하는 노드에 접근한다.

 

이후 다음 노드를 nextnode에 임시로 저장한다.

 

추가될 위치의 이전의 노드(head)의 다음 노드를 newnode로 설정하고,

newnode의 다음 노드를 nextnode로 설정한다.

 

 

3. 원하는 위치의 리스트를 삭제하기

// index번째 노드 삭제
void Delete(Node_t* head, unsigned int index) {
	for (int i = 0; i < index - 1; head = head->Next, i++);

	Node_t* delnote = head->Next;

	head->Next = delnote->Next;
	free(delnote);
    return;
}

index는 원하는 위치의 값을 넣으면된다.

원하는 위치의 노드를 삭제하는 원리는 다음 그림과 같다.

리스트 삭제 순서도

삭제할 노드 이전의 노드에서 초기 작업이 필요하기 때문에

for (int i = 0; i < index - 1; head = head->Next, i++);

코드를 통해 이전의 노드까지 간다.

 

이후 삭제할 노드를 임시로 delnote에 저장한다.

 

마지막으로 삭제할 노드의 전 노드의 next 주소(head->Next)를, 삭제할 노드의 앞 노드(delnote->Next) 주소로 바꾼 뒤,

삭제할 노드를 free() 함수로 삭제한다.

 

 

4. 할당한 메모리 해제

void DeleteAll(Node_t* head) {
	Node_t* tmp = head;
	for (;head != NULL;) {
		tmp = head;
		head = head->Next;
		free(tmp);
	}
	return;
}

malloc를 사용해 노드의 메모리를 할당해줬기 때문에

프로그램 종료 전 할당한 메모리를 모두 해제해야 한다.

(컴파일러가 자동으로 해제하긴 하지만 나중에 메모리 누수를 방지하기 위해 꼭 써주자!)

 

다음은 모든 코드를 합친 코드이다.

원하는 함수를 mian에서 호출해서 사용하자.

 

주의사항 : 노드의 개수가 5개인데 7번째 노드를 삭제하거나 추가할 경우 오류가 생긴다.

-> 이런 오류를  막는 코드도 생각해보자.

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

// Single Linked list 삽입, 삭제, 추가 구현
typedef struct Node_s
{
	struct Node_s* Next;
	int Data;
} Node_t;

void Append(Node_t* head, int data) {
	Node_t* newnode = malloc(sizeof(Node_t));
	newnode->Next = NULL;
	newnode->Data = data;

	for (;head->Next != NULL; head = head->Next);

	head->Next = newnode;
	return;
}

//index번째 노드 추가
void Insert(Node_t* head, unsigned int index, int data) {
	Node_t* newnode = malloc(sizeof(Node_t));
	newnode->Data = data;

	for (int i = 0; i < index - 1; head = head->Next, i++);

	Node_t* nextnode = head->Next;

	head->Next = newnode;
	newnode->Next = nextnode;
	return;
}

// index번째 노드 삭제
void Delete(Node_t* head, unsigned int index) {
	for (int i = 0; i < index - 1; head = head->Next, i++);

	Node_t* delnote = head->Next;

	head->Next = delnote->Next;
	free(delnote);
	return;
}

// 연결된 모든 노드 삭제
void DeleteAll(Node_t* head) {
	Node_t* tmp = head;
	for (;head != NULL;) {
		tmp = head;
		head = head->Next;
		free(tmp);
	}
	return;
}


int main(void)
{
	Node_t* list = malloc(sizeof(Node_t));
	list->Next = NULL;
	list->Data = 0;

	DeleteAll(list);
	return 0;
}