[C/C++]연결리스트 - 원형연결리스트 CLL

자료구조

이번에는 원형연결리스트를 구현해볼 것입니다.

 

핵심은 head포인터가 마지막노드를 가리키고 있고, head->link가 첫번째 노드를 가리킨다는 것인데, 이것만 알면 단순연결리스트와 별다를게 없습니다.

 

원형연결리스트의 사용은 단순연결리스트보다 유동적입니다. 어떤 노드에서 탐색을 시작해도 결국엔 자기 자신으로 돌아올 수  있기 때문입니다.

 

지금 글 쓰고 있는 중에 아이패드를 놓고 왔기 때문에 오늘의 그림은 공책 위에서 그리겠습니다.

 

원형연결리스트 Circular Linked List

typedef int element;
typedef struct ListNode {
	element data;
	struct ListNode* link;
}ListNode;

노드의 형태입니다. 단순연결리스트와 동일하므로 넘어갈게요.

 

ListNode* insert_first(ListNode* head, element data) {
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->data = data;
	if (head == NULL) {
		head = node;
		node->link = head;
	}
	else {
		node->link = head->link;
		head->link = node;
	}
	return head;
}

리스트의 맨 앞에 노드를 삽입하는 함수입니다.

 

haed포인터가 마지막노드를 가리키고 있다는 것을 잊으시면 안돼요. 공백리스트인 경우 head->link 가 head 와 동일하게 되는 모양이 됩니다. 아래 그림의 노드가 삽입된 노드입니다. 원래 node포인터도 가리키고 있어야하지만 생략했어요.

 

공백리스트가 아닌 경우에는 첫번째 노드를 가리키고 있던 head->link를 삽입될 노드의 link에 붙여주고, head->link가 삽입될 노드를 가리키게 합니다.

 

head->link를 삽입될 노드의 link에 붙여준 다는 말은 head->link와 node->link가 같은 노드를 가리키도록 한다는 이야기입니다.

 

리스트의 변화가 생겼으니 head포인터를 반환해줌으로써 변경사항 저장과 같은 느낌을 줘 봅니다.

번호를 매겨서 순서를 나타내 보았는데 괜찮을 지 모르겠네요. 다음 함수는 리스트의 맨끝에 노드를 삽입하는 함수입니다.

ListNode* insert_last(ListNode* head, element data) {
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->data = data;
	if (head == NULL) {
		head = node;
		node->link = head;
	}
	else {
		node->link = head->link;
		head->link = node;
		head = node;
	}
	return head;
}

insert_first()함수와 다른 것이 코드 한 줄 밖에 없습니다. 이것은 원형연결리스트의 특징이라고 할 수 있습니다.

 

의미 상 마지막 노드를 가리키고 있던 head포인터를 삽입된 노드에게 옮겨주면 그 노드는 head포인터가 가리키고 있으므로 마지막 노드가 되기 때문입니다.

 

3번이 추가됐습니다. node포인터를 head에게 옮겨주면 그림과 같은 이미지를 생각하시면 돼요.

 

제가 자료구조를 천인국 자료구조 책으로 정리하고 있어서 책에 없는 원형연결리스트의 삭제함수는 생략하도록 하겠습니다.

 

print_list()가 있는 전체 코드를 올려드리고 마치겠습니다. 주석을 조금 달아놨는데 틀린부분 있으면 말씀해주세요.

 

#include <stdio.h>

typedef int element;
typedef struct ListNode {
	element data;
	struct ListNode* link;
}ListNode;

void print_list(ListNode* head) {
	ListNode* p;

	if (head == NULL) return 0;
	p = head->link; //p는 첫번째 노드가 되겠다. 의미상의 첫번째 노드.
	do {
		printf("%d->", p->data);
		p = p->link;
	} while (p != head);
	printf("%d->", p->data);//마지막노드는 while문안에서 안돌아감. 그래서 마지막에 뽑아줘야됨.
}

ListNode* insert_first(ListNode* head, element data) {
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->data = data;
	if (head == NULL) {
		head = node;
		node->link = head;//자기참조에 가까운 의미.
	}
	else {
		node->link = head->link;
		head->link = node;
	}
	return head;//변경사항 저장 필요.
}

ListNode* insert_last(ListNode* head, element data) {
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->data = data;
	if (head == NULL) {
		head = node;
		node->link = head;//자기참조에 가까운 의미.
	}
	else {
		node->link = head->link;
		head->link = node;
		head = node;// 마지막노드를 가리키는 head포인터를 삽입된 노드에 연결해주면 완성.
	}
	return head;//변경사항 저장 필요.
}

int main() {
	ListNode* head = NULL;

	head = insert_last(head, 20);
	head = insert_last(head, 30);
	head = insert_last(head, 40);
	head = insert_first(head, 10);

	print_list(head);

	return 0;
}

"댓글, 공감 버튼 한 번씩 누르고 가주시면 큰 힘이 됩니다"