[자료구조] 원형 연결리스트(Circular Linked List)

원형 연결리스트(Circular Linked List)

원형 연결리스트는 이 전에 해왔던 단일 연결리스트나 이중 연결리스트에서 끝을 처음과 연결된 리스트를 말한다. 그림 상으로는 원으로 그렸지만 실제로는 선형 연결리스트의 마지막 노드의 next 포인터를 처음으로 연결 시켜주면 된다.

원형리스트(단일 연결리스트로 표현)는 모든 포인터가 다음 노드로 연결되어있다. 이러한 cycle 구조자료의 구현이 필요할 때는 원형리스트가 유용하다. 다시 마지막에서 첫번째로 이동하지 않아도 다음 노드가 첫번째 노드를 가리키기 때문이다. 

[데이터 삽입]

<소스코드>

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

//삽입     void addNode(int data) { //가장 마지막에 노드를 추가한다.           Node *newNode = new Node(data); //새로운 노드를 생성해준다.         size++; //현재 노드의 개수           if (head == NULL) { //머리노드가 아무것도 없는 상태라면             head = newNode;             newNode->next = head;//처음과 연결         }         else {             Node* cur = head;             while (cur) {                   if (cur->next == head) { //cur의 다음노드가 head라면                     cur->next = newNode; //새로운 노드를 연결해준다.                     newNode->next = head; //처음과 연결                     break;                 }                 cur = cur->next;  //다음노드로 이동             }         }       }

데이터 삽입함수의 기능은 가장 마지막 위치에 새로운 노드를 추가시키는 기능을 한다. 원형 연결리스트일 때 기존과 다른 점은 cur->next 가 head가 위치하는 지점이 마지막 지점이며, 이제는 새로운 노드를 가리키도록 하고, 또 새로운 노드는 다시 head를 가리키도록 바꿔줘야한다.

[데이터 삭제]

<소스코드>

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

void deleteNode(int N) {//매개변수-삭제하려는 노드순서번호           if (N <= 0 || N > size || size == 0) {             printf("해당노드가 없습니다.\n");             return;         }           Node* cur = head;         Node* pre = NULL;         if (N == 1) { //head 노드를 지운다면             while(cur) {                 pre = cur;                 cur = cur->next;  //다음노드로 이동                 if (pre->next == head)break;             }             head = head->next;             pre->next = head->next; //이전 포인터는 head의 다음 노드를 가리킨다.             delete cur;         }         else {             for (int i = 1; i < N; i++) {                 pre = cur;                 cur = cur->next;  //다음노드로 이동             }               if (N == size) pre->next = head;//마지막 노드를 지울 때 이전노드의 다음 노드는 head가 된다.             else pre->next = cur->next; //삭제될 노드를 제외하고 포인터를 연결해준다.               delete cur;  //n번째 노드삭제         }           size--; //삭제하기 때문에 노드 개수를 줄여준다.         if (size == 0)head = NULL;                   return;     }

삭제의 함수는 N번째 노드를 지우는 기능을 한다. 이 역시도 첫 번째 노드를 지우는 경우, 마지막 노드를 지우는 경우, 가운데 노드를 지우는 경우로 나눠서 구현을 하였다. 

특히 첫 번째 노드를 지우는 경우는 이전 마지막 노드(pre)의 next포인터가 head->next를 가리켜야 하기 때문에 마지막 노드를 찾기위해 탐색을 해야한다. 하지만 위에 예제는 단일포인터를 사용했기 때문에 번거롭게 된거고, 이중 연결리스트를 사용한다면 좀 더 구현이 간단하고 빠르다.

내가 구현한 수정 함수는 기존의 단일 연결리스트의 구현과 다를 것이 없기 때문에 건너뛴다.

[데이터 출력]

<소스코드>

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

//출력     void printList(int cycle) {           if (size == 0) {             printf("빈 리스트\n");             return;         }           Node* cur = head;         while (cycle--) { //원하는 바퀴수만큼 돌 수 있다.               for (int i = 1; i <= size; i++) { //사이즈만큼                 printf("%d ", cur->data);                 cur = cur->next;  //다음노드로 이동             }             printf("\n");         }         printf("\n");         return;     }

출력도 크게 달라지지 않지만 원형 리스트이기 때문에 매개변수 N 숫자로 반복 출력이 가능하다. 

본 구현은 head라는 첫번째 노드의 기준으로 다음 노드에 접근한다. 1 circle을 판단하는 기준은 노드의 개수(size)이며 head기준 1바퀴를 출력할 수 있다.

[예제]

<전체소스코드>

	#include <cstdio>
	#include <iostream>
	using namespace std;
	class Node {
	public:
	int data;
	Node *next;
	Node() {}
	Node(int data) : data(data) { //노드를 생성할 때 매개변수 값을 data변수에 값을 대입시켜준다.
	this->next = NULL; // next포인터를 초기화 시켜준다.
	}
	~Node() {}
	};
	class CircularLinkedList {
	public:
	Node *head;
	int size = 0;
	CircularLinkedList() {
	head = NULL;
	}
	//삽입
	void addNode(int data) { //가장 마지막에 노드를 추가한다.
	Node *newNode = new Node(data); //새로운 노드를 생성해준다.
	size++; //현재 노드의 개수
	if (head == NULL) { //머리노드가 아무것도 없는 상태라면
	head = newNode;
	newNode->next = head;//처음과 연결
	}
	else {
	Node* cur = head;
	while (cur) {
	if (cur->next == head) { //cur의 다음노드가 head라면
	cur->next = newNode; //새로운 노드를 연결해준다.
	newNode->next = head; //처음과 연결
	break;
	}
	cur = cur->next; //다음노드로 이동
	}
	}
	}
	//출력
	void printList(int cycle) {
	if (size == 0) {
	printf("빈 리스트\n");
	return;
	}
	Node* cur = head;
	while (cycle--) { //원하는 바퀴수만큼 돌 수 있다.
	for (int i = 1; i <= size; i++) { //사이즈만큼
	printf("%d ", cur->data);
	cur = cur->next; //다음노드로 이동
	}
	printf("\n");
	}
	printf("\n");
	return;
	}
	//수정
	void changeNode(int N, int data) { //매개변수-변경하려는 노드순서번호/데이터
	if (N <= 0 || N > size || size == 0) {
	printf("해당노드가 없습니다.\n");
	return;
	}
	Node* cur = head;
	for (int i = 1; i < N; i++) cur = cur->next; //다음노드로 이동
	cur->data = data;
	return;
	}
	//삭제
	void deleteNode(int N) {//매개변수-삭제하려는 노드순서번호
	if (N <= 0 || N > size || size == 0) {
	printf("해당노드가 없습니다.\n");
	return;
	}
	Node* cur = head;
	Node* pre = NULL;
	if (N == 1) { //head 노드를 지운다면
	while(cur) {
	pre = cur;
	cur = cur->next; //다음노드로 이동
	if (pre->next == head)break;
	}
	head = head->next;
	pre->next = head->next; //이전 포인터는 head의 다음 노드를 가리킨다.
	delete cur;
	}
	else {
	for (int i = 1; i < N; i++) {
	pre = cur;
	cur = cur->next; //다음노드로 이동
	}
	if (N == size) pre->next = head;//마지막 노드를 지울 때 이전노드의 다음 노드는 head가 된다.
	else pre->next = cur->next; //삭제될 노드를 제외하고 포인터를 연결해준다.
	delete cur; //n번째 노드삭제
	}
	size--; //삭제하기 때문에 노드 개수를 줄여준다.
	if (size == 0)head = NULL;
	return;
	}
	};
	int main() {
	CircularLinkedList list;
	//삽입
	printf("[삽입]\n");
	list.printList(1);
	for (int i = 1; i <= 10; i++)list.addNode(i);
	list.printList(2); //두바퀴출력
	//수정
	printf("[수정]\n");
	list.changeNode(3, 123);
	list.changeNode(5, 63343);
	list.changeNode(10, 239);
	list.printList(3); //세바퀴출력
	//삭제
	printf("[삭제]\n");
	list.deleteNode(1); //head노드 지우기
	list.printList(1); //출력
	list.deleteNode(9); //마지막 노드 지우기
	list.printList(1); //출력
	list.deleteNode(3); //중간 지우기
	list.printList(5); //5바퀴 출력
	}

view rawCircularLinkedList_Test.cpp hosted with ❤ by GitHub

<출력화면>

출처 : http://meylady.tistory.com