[자료구조] 원형 연결리스트

 

원형 연결리스트는 말 그대로 원형으로 구조가 되어있는 연결리스트이다.

 

 

예를 들자면 이러한 구조가 될 것 같다.

 

계속 끝없이 순환 하는 연결리스트이다.ss

 

 

앞에서 만들었던 연결리스트의 마지막 노드가 맨 앞의 노드를 가리키면

뱀이 꼬리를 물 듯 원형의 모양이 자연스레 나오게 된다.

 

나름 원형 리스트를 새로 짜본다고

만들어 본거지만 뭔가 찜찜함은 여전하다..

 

Node.h

#pragma once   class Node { public:       Node();     ~Node();   private:       friend class CNodeManager;       Node *Next;     int nSaveData;   };

Node.cpp

#include <iostream>     #include "Node.h"   Node::Node() {     std::cout<<"Node 생성자"<<std::endl;     this->Next = NULL;     nSaveData = 0;   }   Node::~Node() {     std::cout<<"Node 소멸자"<<std::endl; }

NodeManger.h

#pragma once   #include "Node.h"   enum eMenu {     eInsert = 1,     eDelete,     ePrint,     eExit, };   class CNodeManager { public:     CNodeManager();     ~CNodeManager();       int Start();     void PrintNode();      private:       friend class Node;       Node *Tail;       int GetData();     void InsertNode();     void DeleteNode();     void AllDelete();   };

NodeManager.cpp

#include <iostream>   #include "NodeManger.h"   CNodeManager::CNodeManager() {     std::cout<<"NodeManager 생성자"<<std::endl;       //this->Head = NULL;     this->Tail = NULL;     //this->TailBefore = NULL;   }   CNodeManager::~CNodeManager() {     std::cout<<"NodeManager 소멸자"<<std::endl; }   int CNodeManager::Start() {     int nChoiceMenu = 0;       while(true)     {         std::cout<<"1. 추가 2. 삭제 3.출력 4.종료"<<std::endl;         std::cin>>nChoiceMenu;         switch (nChoiceMenu)         {         case eInsert:             this->InsertNode();             break;         case eDelete:             this->DeleteNode();             break;         case ePrint:             this->PrintNode();             break;         case eExit:             this->AllDelete();             return eExit;         default:             std::cout<<"잘못 선택하셨습니다."<<std::endl;             break;         }     } }     int CNodeManager::GetData() {     int nGetNum = 0;       std::cout<<"저장할 정수를 입력해 주세요"<<std::endl;     std::cin>>nGetNum;       return nGetNum; }     void CNodeManager::InsertNode() {     // tail->next == Head       Node *NewNode = new Node;     NewNode->nSaveData = this->GetData();     if( NULL == this->Tail )     {//노드가 하나도 없을시         this->Tail = NewNode;                         NewNode->Next = NewNode;         //노드가 하나 생성시에는 새 노드의 다음은 자기 자신이다.     }     else     {             NewNode->Next = this->Tail->Next;             //새 노드가 현재의 머리부분을 가리키게..         this->Tail->Next = NewNode;         //Tail의 다음은 새 노드를 가리키게.     }     }       void CNodeManager::DeleteNode() {     if( NULL == this->Tail )     {         std::cout<<"삭제할 노드가 존재하지 않습니다."<<std::endl;     }     else     {         //Node *TailBefore= NULL;        //Tail 이전을 가리킬 포인터         Node *I_Node = this->Tail->Next;    //처음부분을 가리킴           if( I_Node == this->Tail )         {//처음부분이 Tail과 같을 경우 (노드가 1개만 있을때)             std::cout<<I_Node->nSaveData<<"삭제 시도...";             delete I_Node;             std::cout<<"삭제 성공"<<std::endl;             Tail = NULL;         }         else         {             Node *Temp_Node = I_Node->Next;    //처음부분의 다음 노드             std::cout<<I_Node->nSaveData<<"삭제 시도...";             delete I_Node;             std::cout<<"삭제 성공"<<std::endl;             this->Tail->Next = Temp_Node;                 //끝부분의 다음이 처음부분의 다음 노드를 가리킴         }     } }   void CNodeManager::AllDelete() {     while( NULL != this->Tail )     {         this->DeleteNode();     } }   void CNodeManager::PrintNode() {     if( NULL == this->Tail )     {         std::cout<<"노드가 존재 하지 않습니다."<<std::endl;     }     else     {         int nGetCycle = 0;         int nCycle = 0;           Node *I_Node = this->Tail->Next;        //맨 처음을 가리기게함           std::cout<<"몇회 출력 하시겠습니까?"<<std::endl;         std::cin>>nGetCycle;           while(true)         {             if( nGetCycle <= nCycle )             {                 break;             }             else if( this->Tail == I_Node )             {                 std::cout<<"데이터 : "<<I_Node->nSaveData<<std::endl;                 I_Node = I_Node->Next;                 nCycle++;             }             else             {                 std::cout<<"데이터 : "<<I_Node->nSaveData<<std::endl;                 I_Node = I_Node->Next;             }         }     } }

main.cpp

#include <iostream>   #include "NodeManger.h"   int main() {     CNodeManager NodeManager;       NodeManager.Start();       return 0; }

 

 

출력 결과

 

원형으로 이루어진 리스트라서

Next로 무한히 나아가기 때문에 이점에 유의해야 한다.