[알고리즘/자료구조] 링크드 리스트(linked list)

링크드 리스트는 '노드를 연결해서 만드는 리스트'를 의미하고, 노드는 데이터와 다른 노드를 가리키는 포인터로 이루어져 있습니다.

 

C언어에서 링크드 리스트를 표현하면 다음과 같이 표현할 수 있습니다.

#include<stdio.h>

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

int main() {
	struct Node MyNode;
	return 0;
}

 

typedef로 짧은 이름을 부여할 수도 있습니다.

#include<stdio.h>

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

int main() {
	Node MyNode;
	return 0;
}

 

링크드 리스트의 주요 연산은 다음과 같습니다.

- 노드 생성/소멸(create/destroy)

Node* createNode(int newData) {
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = newData;
	newNode->nextNode = NULL;

	return newNode;
}

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

 

- 노드 추가(append): 링크드리스트의 꼬리 노드 뒤에 새로운 노드를 생성 후 연결하는 것을 의미합니다.

void appendNode(Node** Head, Node* NewNode) {
	if ((*Head) == NULL) {
		*Head = NewNode;
	}
	else {
		Node* Tail = (*Head);
		while (Tail->nextNode != NULL) {
			Tail = Tail->nextNode;
		}

		Tail->nextNode = NewNode;
	}
}

int main() {
	Node* List = NULL;
	Node* NewNode = NULL;

	NewNode = createNode(117);
	appendNode(&List, NewNode);

	NewNode = createNode(119);
	appendNode(&List, NewNode);
	return 0;
}

 

- 노드 탐색: 탐색 연산은 인덱스를 이용해 접근할 수 없고, 차근차근 노드의 수를 세어가야합니다. (링크드 리스트의 엄청난 단점입니다. 아이템에 인덱스를 이용해 바로 접근할 수 없다니...!!)

Node* getNodeAt(Node* Head, int location) {
	Node* Current = Head;
	while (Current != NULL && (--location) >= 0) {
		Current = Current->nextNode;
	}
	return Current;
}

int main() {
	Node* List = NULL;
	Node* MyNode = NULL;

	appendNode(&List, createNode(117));
	appendNode(&List, createNode(119));

	MyNode = getNodeAt(List, 1);
	printf("%d\n", MyNode->data);
	return 0;
}

 

- 노드 삭제: 노드 삭제 연산은 링크드 리스트 내에 있는 임의의 노드를 제거하는 연산입니다. 삭제하고자 하는 노드를 찾은 후, 해당 노드의 다음 노드를 이전 노드의 NextNode 포인터에서 제거하면 됩니다.

void 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;
		}
	}
}

int main() {
	Node* List = NULL;
	Node* MyNode = NULL;

	appendNode(&List, createNode(117));
	appendNode(&List, createNode(119));
	appendNode(&List, createNode(212));

	MyNode = getNodeAt(List, 1);
	printf("%d\n", MyNode->data);

	removeNode(&List, MyNode); // 두 번째 노드 제거

	destroyNode(MyNode); // 링크드 리스트에서 제거한 노드를 메모리에서 완전히 소멸시킴;
	return 0;
}

 

- 노드 삽입

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

 

- 노드 개수 세기: 링크드 리스트 내에 존재하는 노드의 수를 세어 반환함.

int getNodeCount(Node* Head) {
	int Count = 0;
	Node* Current = Head;

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

	return Count;
}