[자료구조] - LinkedList의 구현 (C언어)

1. 개요

 

 공부를 많이 했다고는 하지 못하지만, 나름 자료구조라는 과목에는 학교에서든(성적은 잘 모르겠지만 ㅠㅠ) 독학에서든 노력을 했다고 생각한다. 그러나 아직도 자료구조가 뭔지 모르겠다고 느껴질 때가 많다. 이번에 구현한 LinkedList는 바로 직전에 자료구조 카테고리로 작성한 글인 Stack과는 코드스타일이 조금 다른느낌일 수 있다고 생각한다. 다른 책을 참고하였기 때문이다...... ㅠㅠ 사실 Stack은 서적을 참고했다기 보다는 거의 나의 힘으로 작성한 것이지만 LinkedList의 경우는 서적을 참고하였다. 자료구조의 책을 한 세권정도 읽었는데(그중 하나는 학교강의) 한 자료구조에 해당하는 주요 연산의 기능을 해낼수만 있다면 코드는 조금씩 다르다는 것을 알게되었다. 결국 중요한 것은 자료구조의 이해라고 생각하기에 나도 코드를 완벽하게 복사하지는 않지만, 그래도 나보다는 훨씬 저명한 분이 작성한 책이기에, 나름 따라하려는 노력은 하였다. 다음은 LinkedList에 대한 이론이다.

 

2. LinkedList 이론

 

 사실 어떤 책에서는 Stack을 소개하기 전에 LinkedList를 소개하기도 한다. LinkedList를 구현하면서 만드는 Node와 같은 개념이 중요하기도 하고, 혹은 LinkedList로도 Stack을 만들 수 있기 때문이다. 내가 하고싶은 말은 LinkedList는 모든 자료구조의 기본이라는 것이다.(지극히 개인적인 의견으로)

 

 LinkedList는 이름 그대로 무언가와 연결된(Linked) List이다. LinkedList를 소개할 때 대부분의 전문가들은 배열과 비교를 한다. 그러니 나도 배열과 비교할 것이다. 배열과 같은 경우는 선언할 때부터 크기를 정해줘야하는데, 이는 아주 큰 단점중에 하나이다. 백준 알고리즘만 봐도 사용자의 입력으로 배열의 크기를 정해야하는 경우가 허다했기 때문이다. 그렇다고 "이 사람이 얼마나 많은 수를 입력할지 모르니 10000000000을 배열의 크기로 선언하자!" 라고 판단할 수는 없는 노릇이다. 만약 사용자가 1을 입력하는 경우에는 9999999999의 공간이 남게되고, 아무리 작은 크기를 차지하는 문자의 배열이라고 해도 9999999999bit의 공간이 낭비되기 때문이다. 또 다른 경우는 10000000001의 갯수를 사용자가 입력하면, 프로그램은 오류가 발생하게 된다. 결국 사용자가 입력할 때마다 공간을 만들어 주면 좋은데, 이런 기능을 할 수 있는것이 바로 LinkedList이다.

 

-LinkedList의 구조

 

 LinkedList는 노드로 이루어져 있다. 그리고 노드는 데이터를 직접 저장하는 data 필드와 그 다음 노드를 가리키는 link 필드로 나누어져 있다. 다음은 노드의 그림이다.

---

노드 그림

---

그리고 LinkedList는이런 노드들이 각각 자신의 바로 뒤에있는 노드를 가리키는 구조로 되어있다. 그림으로 표현하면 다음과 같을 것이다.

---

리스트 그림

---

 그리고 이 노드의 맨 앞은 head라고 불리고, 맨 뒤는 tail이라고 불리는데, 맨 마지막 노든 NULL을 가리킴으로써 자신이 마지막 노드라는 것을 알려준다. 그림으로 표현하면 다음과 같을 것이다.

 

- LinkedList의 연산

 

 LinkedList의 가장 기본적인 연산은 다음과 같다.

---

• 노드의 생성/소멸
• 노드 추가
• 노드 탐색
• 노드 삭제
• 노드 삽입

---

 어떤 사람들은 노드의 생성과 추가를 합치는 사람들도 있고, 노드의 삭제와 소멸또한 합치는 사람도 있다. 그러나 나는 이번에 참고한 서적을 참고할 것이고 다시한번 말하지만, 자료구조를 구현하는 코드 방식보다는 자료구조의 깊은 이해가 가장 큰 목적이다. 다음은 이번에 Node역할을 할 구조체이다.

 

typedef struct Node {
	int data;
	struct Node *nextNode;
}Node;

 

- 노드의 생성/소멸

 

 노드의 생성과 소멸은 말 그대로 하나의 노드를 만들어주는 역할만을 한다. 다음과 같이 구현하였다.

 

Node* SLL_CreateNode(int NewData) {
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = NewData;
	newNode->nextNode = NULL;
	return newNode;
}

void SLL_DestroyNode(Node* Node) {
	free(Node);
}

 

- 노드 추가, 노드 삽입

 

  이제 생성된 노드를 추가해야한다. 가장 기본적인 방법은 마지막 노드에 노드를 추가하는 것인데, 중요한점은 이 리스트의 마지막 노드를 찾아야한다는 것이다. 이는 다음과 같이 구현할 수 있다.

 

void SLL_AppendNode(Node **head, Node *newNode) {
	
	if (*head) {
		Node *tail = *head;
		while (tail->nextNode)
			tail = tail->nextNode;
		tail->nextNode = newNode;
	}
	else 
		*head = newNode;
	return head;
}

 

 그 다음은 지정된 노드 뒤에 새로운 노드를 추가하는 문장이다. 그림으로 표현하자면 다음과 같을 것이다.

 

---

노드 추가 그림

---

 

 중요한점은 link를 조작할 때, 서로의 연결이 끊기지 않아야한다는 것이다.

 

void SLL_InsertAfter(Node *Current, Node *NewNode) {
	NewNode->nextNode = Current->nextNode;
	Current->nextNode = NewNode;
}

 

- 노드 탐색

 

 다음은 노드의 탐색이다. 사실 노드를 탐색한다는 사실이 바로 LinkedList의 단점이다. 연산이 많아지기 때문인데, 일단 이것은 다음에 이야기하도록 하자. 하나의 값을 받아 그 값이 마치 배열의 인덱스처럼 동작하여 값에 해당하는 노드를 반환해주는 코드이다. 첫 노드 즉, 헤드노드는 0번째이고, 그다음 노드는 1번째이다. 다음은 소스 코드이다.

 

Node* SLL_GetNodeAt(Node *head, int location) {
	Node *find;
	find = head;
	while (find && (--location) >= 0)
		find = find->nextNode;
	return find;
}

 

 이 코드는 거의 노드 추가 코드와 같이 쓰인다. 이것은 예제에서 설명할 것이다.

 

- 노드 삭제

 

 노드의 삭제는 노드의 소멸과는 다르다. 삭제는 LinkedList에서 제외한다는 의미이고 소멸은 그냥 메모리 자체를 저세상으로 보내버린다는 뜻이다. 제거하려는 노드의 주소와 head노드의 주소를 보내주면 알아서 link의 연결을 끊어주는 역할을 해야한다. 그림으로 표현하면 다음과 같을것이다.

---

노드 삭제 그림

---

 중요한점은 head노드자체가 삭제의 대상이 될 수 있다는 것과, link를 조작하는 과정이다. 다음은 소스 코드이다.

 

void SLL_RemoveNode(Node **head, Node *remove) {
	Node *find = *head;
	if (find == remove)
		*head = remove->nextNode;
	else {
		while (find && find->nextNode != remove)
			find = find->nextNode;
		if(find)
			find->nextNode = remove->nextNode;
	}
}

 

-LinkedList의 길이 반환

 

 LinkedList의 길이를 반환하는 함수는 기본적인 연산은 아니지만, 매우 유용한 연산이다. 기본적인 연산이 아니어도 유용할 것 같은 연산은 연습삼아 한 번 함수로 작성해보는 것도 자료구조를 공부하는데 큰 도움이 되는 것 같다. 결국 자신의 힘으로 한 자료구조의 연산을 만든다는 것은 그만큼 자료구조를 잘 이해하고 있다는 뜻이기 때문이다. 다음은 소스코드이다.

 

int SLL_GetNodeCount(Node *Head) {
	int count = 0;
	Node *buff = Head;
	while (buff) {
		count++;
		buff = buff->nextNode;
	}
	return count;
}

 

- LinkedList 사용 예제

 

 다음은 내가 지금까지 소개한 코드들을 사용한 LinkedList의 사용예제이다. 이 main함수는 책을 참고하지 않고, 내가 직접 작성하였다. 결국 자료구조를 이해하기 위해 작성한 코드이기 때문에 독자들도 내 함수를 따라하지 말고 스스로 함수를 만들어보기를 바란다.

 

#include "linkList.h"

int main(void) {
	Node *list = NULL;

	for (int i = 0; i < 5; i++) {
		Node *newNode = SLL_CreateNode(i);
		SLL_AppendNode(&list, newNode);
	}

	int size = SLL_GetNodeCount(list);
	
	for (int i = 0; i < size; i++) {
		Node *buff = SLL_GetNodeAt(list, i);
		printf("List[%d] : %d\n", i, buff->data);
	}

	Node *buff = SLL_CreateNode(2000);
	SLL_InsertAfter(SLL_GetNodeAt(list, 2), buff);
	printf("\ninsert 2000 after index 2\n\n");
	
	size = SLL_GetNodeCount(list);

	for (int i = 0; i < size; i++) {
		Node *buff = SLL_GetNodeAt(list, i);
		printf("List[%d] : %d\n", i, buff->data);
	}

	for (int i = 0; i < size; i++) {
		Node *del = SLL_GetNodeAt(list, 0);
		SLL_RemoveNode(&list, del);
		SLL_DestroyNode(del);
	}

	printf("\n리스트가 전부 제거되었습니다.");

	return 0;
}

 

3.결어

 

 아쉽게 C++버전은 만들지 못했다...... 시간이 없어서라는 말을 하고싶진 않지만...... 그래도 정말 열심히는 했다...... 지금 창문 밖은 해가 뜨고있다...... 다음에는 C++버전의 LinkedList와 Doubly Linked List에 대한 글을 올렸으면 좋겠다.