반응형
▣ 연결리스트 종류
● 단순 연결 리스트 (Simply linked list)
▷ 하나의 링크만 있고, 각각 노드의 링크는 후행 노드만을 가리키는 구조다.
- 특정 노드의 후행 노드는 쉽게 접근할 수 있지만, 특정 노드의 선행 노드에 대한 접근은 헤드 노드부터 재검색해야 하는 문제점이 있다.
- 자세한 코드 구현 방법 등 단순 연결 리스트 관련 포스트는 아래 링크를 참고하세요.
2020/09/10 - [Programming/Data Structure] - [C++] 연결리스트 Linked list 코드 구현 방법
● 이중 연결 리스트 (Double linked list)
이중 연결 리스트 관련 포스트는 아래 글을 참고하세요.
2020/09/10 - [Programming/Data Structure] - [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;
}
▷ 출력결과
728x90
반응형
'Programming > Data Structure' 카테고리의 다른 글
[C++] 힙 코드 구현 방법 heap (0) | 2020.09.22 |
---|---|
[C++] 이진트리 코드 구현 방법 binary tree (0) | 2020.09.21 |
[C++] 이중연결리스트 코드 구현 방법 Doubly linked list (0) | 2020.09.10 |
[C++] 연결리스트 Linked list 코드 구현 방법 (0) | 2020.09.10 |
[C++] 큐 Queue 구현 방법 코드 (0) | 2020.09.09 |