[C++] 원형 연결 리스트 코드 구현 방법 Circular linked list

▣ 연결리스트 종류

 ●  단순 연결 리스트 (Simply linked list)

  ▷ 하나의 링크만 있고, 각각 노드의 링크는 후행 노드만을 가리키는 구조다.

•   특정 노드의 후행 노드는 쉽게 접근할 수 있지만, 특정 노드의 선행 노드에 대한 접근은 헤드 노드부터 재검색해야 하는 문제점이 있다. 
•   자세한 코드 구현 방법 등 단순 연결 리스트 관련 포스트는 아래 링크를 참고하세요.

2020/09/10 - [Programming/Data Structure] - [C++] 연결리스트 Linked list 코드 구현 방법

[C++] 연결리스트 Linked list 코드 구현 방법

 

 ●  이중 연결 리스트 (Double linked list)

이중 연결 리스트 관련 포스트는 아래 글을 참고하세요.

2020/09/10 - [Programming/Data Structure] - [C++] 이중연결리스트 코드 구현 방법 Double linked list

[C++] 이중연결리스트 코드 구현 방법 Double linked list

 

 ●  원형 연결 리스트 (Circular linked list)

  ▷ 연결 리스트를 보면, 가장 마지막 노드의 link 필드는 항상 'NULL'이다.

• 리스트의 마지막 노드의 link 필드를 활용하면서 프로그램 성능에 도움이 되도록 원형의 연결 리스트가 제안됐다.

 

▣ 원형연결리스트 코드 구현

  ▷ CirLinkList.h  (원형연결리스트 클래스를 구현한 헤더파일이다)

#pragma once
#include <iostream>
using namespace std;

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

struct HeadNode {
	Node* head;
};

class circlist {

public:

	/*리스트 생성, 헤드노드 */
	HeadNode* createList(){
		HeadNode* H;
		H = new HeadNode;
		H->head = NULL;
		return H;
	}

	/* 원형리스트의 처음에 노드 삽입*/
	void addFirstNode(HeadNode* H, int x) {
		Node* prevNode;
		Node* newNode = new Node;
		newNode->data = x;
		newNode->link = NULL;

		if (H->head == NULL) {  // 리스트가 빈 경우
			H->head = newNode;
			newNode->link = newNode;  //원형연결리스트 특징; 노드가 하나면 노드가 자기자신을 가리킴
			return;
		}

		prevNode = H->head;
		while (prevNode->link != H->head) prevNode = prevNode->link; // 다시 헤드를 향하는 마지막 노드 전까지 반복
		newNode->link = prevNode->link; //맨마지막노드가 가리키는 맨 앞 노드를 새 노드가 가리키게 함. (맨앞노드 자리 뺏기)
		prevNode->link = newNode; // 맨마지막노드가 새 노드를 가리키게(새노드가 맨첫노드가 됏으므로->원형)
		H->head = newNode; // 헤드도 맨 첫 노드로 새 노드 가리키게 하면 끝
	}

	/* 원형연결리스트 중간에 노드 삽입*/
	void addMiddleNode(HeadNode* H, int afterthisdata, int adddata) {
		Node* prevNode;
		prevNode = H->head;
		Node* newNode = new Node;

		while (prevNode->data != afterthisdata) {
			prevNode = prevNode->link;
		}
		
		newNode->data = adddata;
		newNode->link = prevNode->link;
		prevNode->link = newNode;
		return;
	}

	/* 원형연결리스트의 노드 삭제*/
	void deleteCircleNode(HeadNode* H, int deldata) {
		Node* prevNode;
		Node* delNode;

		prevNode = H->head;
		while (prevNode->link->data != deldata) {
			prevNode = prevNode->link;
		}

		if (H->head == NULL) return;  //삭제할 노드가 존재하지 않는 경우
		else {
			delNode = prevNode->link;

			if (delNode == prevNode) H->head = NULL; // 노드가 한개만 존재(삭제할 노드가 자기자신 가리키는것: 자기만있다)
			else {
				prevNode->link = delNode->link; //삭제할노드의 앞노드가 삭제할노드 다음노드를 가리키게 
				
				if (delNode == H->head) H->head = delNode->link; //첫노드 삭제해야하는 경우 헤드가 삭제할노드 다음노드를 가리키게 한다.
			}
			delete delNode;
		}
		cout << deldata << "의 데이터값을 가지는 노드가 삭제되었습니다. " << endl;
		return;
	}

	/* 연결리스트 출력*/
	void printList(HeadNode* L) {
		//노드 순서대로 리스트 출력
		Node* p;
		Node* tmp;

		p = L->head;

		if (p == NULL) { // 리스트가 빈 경우
			cout << "연결 리스트가 비어있습니다." << endl;
			return;
		}
		else {
			cout << "연결리스트 목록 = ( "; // 리스트가 안 빈 경우
			tmp = L->head;
			cout << p->data;
			p = p->link;

			while (p != tmp) {  // 헤드가 가리키는 걸 p가 가리키게 되면 출력을 멈춘다.
				cout << " --> ";
				cout << p->data;
				p = p->link;
			}
		}
		cout << " )" << endl << endl;
	}
};

 

 

  ▷ CirculistMain.cpp (원형연결리스트를 구현할 main함수를 포함한 코드다)

#include <iostream>
#include "CirLinkList.h"
using namespace std;

void main()
{
	circlist list;

	HeadNode* L;
	L = list.createList();

	cout << "1. 빈 원형 연결 리스트를 생성했습니다." << endl << endl;

	int data1, data2, data3;
	cout << "2-1. 원형 연결 리스트 첫 노드로 추가할 노드의 데이터를 정해주세요: ";
	cin >> data1;
	list.addFirstNode(L, data1);
	list.printList(L);

	cout << "2-2. 원형 연결 리스트 첫 노드로 추가할 노드의 데이터를 정해주세요: ";
	cin >> data2;
	list.addFirstNode(L, data2);
	list.printList(L);

	cout << "2-3. 원형 연결 리스트 첫 노드로 추가할 노드의 데이터를 정해주세요: ";
	cin >> data3;
	list.addFirstNode(L, data3);
	list.printList(L);
	cout << endl;

	cout << "3. 원형 연결 리스트 중간에 노드를 삽입하겠습니다. " << endl;

	cout << "3-1. 어떤 노드 뒤에 노드를 추가할건가요? : ";
	int data5, data4;
	cin >> data5;
	cout << "3-2. 그 노드 뒤에 어떤 데이터를 가진 노드를 추가할건가요? : ";
	cin >> data4;
	list.addMiddleNode(L, data5, data4);
	list.printList(L);
	cout << endl;

	cout << "4-1. 삭제하고자 하는 노드를 알려주세요 : ";
	int data6;
	cin >> data6;
	list.deleteCircleNode(L, data6);
	list.printList(L);
	cout << endl;

	cout << "4-2. 더 삭제하고 싶은 노드를 알려주세요 : ";
	int data7;
	cin >> data7;
	list.deleteCircleNode(L, data7);
	list.printList(L);
	cout << endl;

	cout << "4-3. 더 삭제하고 싶은 노드를 알려주세요 : ";
	int data8;
	cin >> data8;
	list.deleteCircleNode(L, data8);
	list.printList(L);
	cout << endl;


	cout << "피곤하니까 연산을 끝내겠습니다." << endl;

}

 

  ▷ 출력결과