연결리스트(Linked List) - 단방향

1. 연결리스트와 배열의 차이점

연결리스트와 배열의 차이점에 대해 알기 전에 먼저 자료구조가 무엇인지부터 우리가 알아야 합니다. C언어나 C++같은 C언어 계열 언어를 접할 때, 빠질 수 없는게 자료구조입니다. 자료구조는 어떠한 방대한 데이터를 다룰 때 데이터를 정렬 및 저장하는 방법을 배우는 학문입니다. 정렬을 미리 해놓으면, 데이터를 꺼낼 때 많은 시간을 들이지 않고 데이터를 찾아 낼수도 있습니다. 그 중 데이터관리를 용이하게 할 수 있는 기초적인 방법이 연결리스트와 배열입니다.

배열은 데이터의 양이 정해져 있을때 즉, 데이터의 양이 변하지 않을때 사용하기 좋습니다. 배열을 사용했을 때 장점은 탐색할 때 용이합니다. 즉, 각 요소의 임의접근이 가능합니다. 단점은 아까 말했듯이 데이터의 총량이 존재합니다. 이미 선언된 요소를 실행중엔 바꿀 수가 없습니다.

그래서 데이터의 총량을 바꿀 수 있는 연결리스트가 배열과 대비됩니다. 데이터를 추가하고 싶을 때, 동적 할당으로 추가가 가능합니다. 장점은 자유롭게 데이터를 추가하거나 삭제가 가능합니다. 단점은 데이터의 임의접근이 아닌 순차접근을 해서 탐색속도가 배열에 비해 떨어집니다.

2. 연결리스트

배열은 C언어에서 많이 다뤘기 때문에 연결리스트에 대해서만 알아보겠습니다. 연결리스트는 데이터를 저장하는 노드가 존재합니다. 노드는 다른 노드의 주소값을 저장할 수 있습니다. 주소값을 저장하는 방식과 개수에 따라서 단방향 연결리스트 양방향 연결리스트 원형 연결리스트 이 3가지로 나뉩니다.

3. 단방향 연결리스트

먼저 연결리스트의 아주 기초적인 단방향 연결리스트를 알아보겠습니다. 단방향 연결리스트만 이해를 한다면 양방향과 원형 연결리스트를 이해하는데는 어려움이 없습니다. 단방향은 먼저 구조체변수의 멤버변수부터 봐야한다고 생각합니다.
위에 그림처럼 메모리에 배치가 되는것은 아니지만, 우리가 생각하기에 가장 이상적으로 생각할 수 있는 구조입니다. head노드에 첫 번째 노드의 주소값을 저장하고, 노드를 한개씩 옆으로 이어서 순차접근이 가능하게 합니다.

헤더파일

그럼 헤더파일을 먼저 보겠습니다.
LinkedList.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

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

typedef int ElementType;

typedef struct tagNode {
	ElementType Data;
	struct tagNode* NextNode;
}Node;

//함수 원형 선언
Node* SLL_CreateNode(ElementType NewData);
void SLL_DestroyNode(Node* Node);
void SLL_AppendNode(Node** Head, Node* NewNode);
void SLL_InsertAfter(Node* Current, Node* NewNode);
void SLL_InsertNewHead(Node** Head, Node* NewNode);
void SLL_RemoveNode(Node** Head, Node* Remove);
Node* SLL_GetNodeAt(Node* Head, int Location);
int SLL_GetNodeCount(Node* Head);

#endif

헤더파일에서 Nde구조체를 먼저 보겠습니다.

typedef struct tagNode {
	ElementType Data;
	struct tagNode* NextNode;
}Node;

Data를 저장하는 영역과 다음 Node의 주소값을 저장하는 영역으로 나눠져 있습니다.

다음으로 함수들을 본다면,

Node* SLL_CreateNode(ElementType NewData); ->노드를 생성하는 함수
void SLL_DestroyNode(Node* Node); ->노드를 삭제하는 함수
void SLL_AppendNode(Node** Head, Node* NewNode); ->노드를 리스트에 추가하는 함수
void SLL_InsertAfter(Node* Current, Node* NewNode); ->노드를 리스트에서 지정하는 영역에 삽입하는 함수
void SLL_InsertNewHead(Node** Head, Node* NewNode); ->노드를 헤드에 추가하는 함수
void SLL_RemoveNode(Node** Head, Node* Remove); ->노드를 리스트에서 삭제하는 함수
Node* SLL_GetNodeAt(Node* Head, int Location); ->노드의 위치를 찾는 함수
int SLL_GetNodeCount(Node* Head); ->노드의 개수를 반환하는 함수

함수 이름만으로도 어느정도 추측이 가능합니다.

소스파일

그럼 LinkedList의 소스파일을 보겠습니다.

LinkedList.c

#include "LinkedList.h"

//노드 생성
Node* SLL_CreateNode(ElementType NewData) {
	Node* NewNode = (Node*)malloc(sizeof(Node));

	NewNode->Data = NewData; //데이터를 저장한다.
	NewNode->NextNode = NULL; //다음 노드에 대한 포인터는 NULL로 초기화한다.

	return NewNode; //노드의 주소를 반환한다.
}

//노드 소멸
void SLL_DestroyNode(Node* Node) {
	free(Node);
}

//노드 추가
void SLL_AppendNode(Node** Head, Node* NewNode) {
	//헤드 노드가 null이라면 새로운 노드가 Head가 된다.
	if ((*Head) == NULL) {
		*Head = NewNode;
	}
	else {
		//테일을 찾아 NewNode를 연결한다.
		Node* Tail = (*Head);
		while (Tail->NextNode != NULL) {

			Tail = Tail->NextNode;
		}

		Tail->NextNode = NewNode;
	}
}

//노드 삽입
void SLL_InsertAfter(Node* Current, Node* NewNode) {
	NewNode->NextNode = Current->NextNode;
	Current->NextNode = NewNode;
}

void SLL_InsertNewHead(Node** Head, Node* NewHead) {
	if (Head == NULL) {
		(*Head) = NewHead;
	}
	else {
		NewHead->NextNode = (*Head);
		(*Head) = NewHead;
	}
}

//노드 제거
void SLL_RemoveNode(Node** Head, Node* Remove) {
	if (*Head == Remove) {
		*Head = Remove->NextNode;
	}
	else {
		Node* Current = *Head;
		while (Current != NULL && Current->NextNode != Remove) {
			Current = Current->NextNode;
		}
		if (Current != NULL) {
			Current->NextNode = Remove->NextNode;
		}
	}
}

//노드 탐색
Node* SLL_GetNodeAt(Node* Head, int Location) {
	Node* Current = Head;

	while (Current != NULL && (--Location) >= 0) {
		Current = Current->NextNode;
	}

	return Current;
}

//노드 개수 세기
int SLL_GetNodeCount(Node* Head) {
	int Count = 0;
	Node* Current = Head;

	while (Current != NULL) {
		Current = Current->NextNode;
		Count++;
	}

	return Count;
}

헤더파일만 보고도 소스파일을 직접 만들 줄 알아야 합니다. 한번 씩 만들어 보시는걸 추천드립니다.

실행 예시

LinkedListMain.c

#include "LinkedList.h"

int main() {
	int i = 0;
	int Count = 0;
	Node* List = NULL;
	Node* Current = NULL;
	Node* NewNode = NULL;

	//노드 5개 추가
	for (i = 0; i < 5; i++) {
		NewNode = SLL_CreateNode(i);
		SLL_AppendNode(&List, NewNode);
	}

	NewNode = SLL_CreateNode(-1);
	SLL_InsertNewHead(&List, NewNode);

	NewNode = SLL_CreateNode(-2);
	SLL_InsertNewHead(&List, NewNode);

	//리스트 출력
	Count = SLL_GetNodeCount(List);
	for (i = 0; i < Count; i++) {
		Current = SLL_GetNodeAt(List, i);
		printf("List[%d] : %d\n", i, Current->Data);
	}

	//리스트의 세 번째 노드 뒤에 새 노드 삽입
	printf("\mInserting 3000 After [2]...\n\n");

	Current = SLL_GetNodeAt(List, 2);
	NewNode = SLL_CreateNode(3000);

	SLL_InsertAfter(Current, NewNode);

	//리스트 출력
	Count = SLL_GetNodeCount(List);
	for (i = 0; i < Count; i++) {
		Current = SLL_GetNodeAt(List, i);
		printf("List[%d] : %d\n", i, Current->Data);
	}

	//모든 노드를 메모리에서 제거
	printf("\nDestroying List...\n");

	for (i = 0; i < Count; i++) {
		Current = SLL_GetNodeAt(List, 0);

		if (Current != NULL) {
			SLL_RemoveNode(&List, Current);
			SLL_DestroyNode(Current);
		}
	}

	return 0;
}

결과

List[0] : -2
List[1] : -1
List[2] : 0
List[3] : 1
List[4] : 2
List[5] : 3
List[6] : 4
mInserting 3000 After [2]...

List[0] : -2
List[1] : -1
List[2] : 0
List[3] : 3000
List[4] : 1
List[5] : 2
List[6] : 3
List[7] : 4

Destroying List...

소스파일 해석은 코드 해석 부분이기 때문에 넘어가겠습니다. 중요한 것은 함수가 어떤 기능을 하는지만 안다면 함수를 사용하는데 아무런 문제가 없다는 것입니다. main파일과 헤더파일만 있어도 결과를 정확하게 예측 가능한것처럼 말입니다.