자료 구조 - 링크드 리스트(Linked List)

링크드 리스트는 고정적인 길이인 배열과 다르게 가변적인 성격을 가진 데이터의 집합입니다.

리스트 내의 각 요소는 노드로 이루어져 있으며, 노드는 데이터를 보관하는 필드와 다음 노드의 주소의 포인터가 들어가 있습니다. 데이터와 포인터로 이루어진 노드를 이으면 링크드 리스트가 됩니다.

링크드 리스트의 구조

링크드 리스트에서 제일 앞의 노드를 헤드(Head) 제일 마지막 노드를 테일(Tail)이라고 합니다.

위의 구조를 코드로 나타내면 아래와 같습니다.

typedef struct tagNode {
	int data; // 데이터 필드
	struct tagNode* NextNode; // 다음 노드에 대한 포인터
} Node;
Node MyNode;

 

노드의 생성과 소멸

---

Node* SLL_creatNode(int newData) {
	//c언어는 자동 메모리와 자유 메모리가 있음
	// 자동 메모리 = {} 벗어나면 사라지는 메모리
	// 자유 메모리 = 자유롭게 메모리 할당 가능 => 자바에서는 가비지 컬렉터가 알아서 정리 해주지만 c언어에서는 관리 해주어야함
	Node* newNode = (Node*)malloc(sizeof(Node)); //malloc => 자유 메모리에 newNode 포인터 저장

	newNode->data = newData;
	newNode->NextNode = NULL;

	return newNode;
}

위의 코드는 노드의 생성에 대한 코드입니다.

malloc() 함수는 자유 저장소에 sizeof(Node)의 크기만큼 할당한 후 newNode에 그 메모리 주소를 저장합니다.

c언어는 자바와 다르게 가비지콜렉터가 없으므로 메모리의 생성과 소멸을 관리해줘야 합니다.

 

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

노드의 소멸은 간단합니다.

free() 함수는 매개변수로 주소를 알려주기만 하면 해당하는 메모리를 소멸해줍니다.

 

노드의 추가와 삭제

---

노드의 추가는 링크드 리스트에 있는 테일 노드 뒤에 새로운 노드를 연결하는 것을 의미합니다.

테일 노드에 있는 다음 노드에 대한 포인터를 새로운 노드로 할당하게 되면 끝이 나게 됩니다.

다만, 링크드 리스트에서는 테일 노드에 대한 포인터에 접근하려면 헤드 노드부터 차례대로 이동하여 테일을 찾아야 합니다. 링크드 리스트에서 테일 노드가 의미하는 것은 다음 노드에 대한 포인터가 NULL이라는 점입니다.

void SLL_appendNode(Node** head, Node* newNode) {
	if ((*head) == NULL) { //헤드가 널이면
		*head = newNode; //새로 생성한 노드가 헤드노드
	}
	else { //헤드가 널이 아니면
		Node* tail = (*head); //헤드노드 대입
		while (tail->NextNode != NULL) { //헤드노드의 nextNode가 널이 아닐 때까지
			tail = tail->NextNode; //tail은 다음노드를 가르킴 =>널이 나올때까지 찾아간다
		}
		tail->NextNode = newNode; //널이 나왔을 때 그 자리에 새로 생성한 노드를 연결
	}
}

 

노드의 삭제는 삭제하고자 하는 노드를 찾은 후, 해당 노드의 이전 노드에 있는 포인터에 해당 노드의 다음 노드를 연결해주고 해당 노드를 소멸시킵니다.

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

 

링크드 리스트의 탐색과 삽입

---

링크드 리스트의 탐색은 갖고 있는 단점 중 하나입니다. 링크드 리스트의 각각의 노드마다 주소가 정해져 있는 게 아니고 이전 노드가 자신의 주소를 갖고 있기 때문에 원하는 노드에 찾아가려면 헤드부터 차근차근 찾아가야 합니다. 매우 비효율적이죠.

Node* SLL_getNodeAt(Node* head, int location) { //파라미터로 링크드 리스트와 인덱션 번호 전달
	Node* current = head; //location이 0이면 head 출력

	while (current != NULL && (--location) >= 0) { //널이 아닐때 까지와 인덱션 번호가 마이너스 이동하며 마이너스가 되면 스탑
		current = current->NextNode;
	}

	return current;
}

이렇게 찾은 원하는 노드 뒤에 새로운 노드를 삽입할 수 있습니다.

void SLL_insertAfter(Node* current, Node* newNode) {
	newNode->NextNode = current->NextNode;
	current->NextNode = newNode;
}

앞에도 삽입할 수 있습니다.

void SLL_insertBefore(Node** head, Node* current, Node* newNode) {

	if ((*head) == NULL) {
		printf("비어있는 노드 입니다.");
		return;
	}
	else if ((*head) == current) {
		newNode->NextNode = (*head);
		*head = newNode;
	}
	else {
		Node* prev = NULL;
		Node* now = *head;
		while (now->NextNode != NULL) {
			prev = now;
			now = now->NextNode;

			if (now == current) {
				break;
			}
		}
		newNode->NextNode = now;
		prev->NextNode = newNode;
	}
}

 

다음 포스팅 같은 링크드 리스트지만, 이전 노드의 주소까지 담고 있는 더블 링크드 리스트에 대해 알아보도록 하겠습니다.