[자료구조] 양방향 연결리스트(doubly Linked list 이중 연결 링크드 리스트)

 

양방향 연결리스트 혹은 이중 연결 링크드 리스트 라고 불리는 이 자료구조는

 

이름 그대로 양방향성을 띄는 구조이다.

 

한가지 방향성을 가진 모습이 이러 하였다면..

 

양방향 연결리스트는 이렇게 양방향성을 가지고 있다.

 

이렇게 양방향성을 가지면서 한방향성보다 더욱 편리하게 이용할 수 있다.

 

 

 

Node.h

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

Node.cpp

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

NodeManager.h

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

NodeManager.cpp

#include <iostream>   #include "NodeManager.h"   CNodeManager::CNodeManager() {     std::cout<<"CNodeManager 생성자"<<std::endl;       this->Head = NULL;     this->Tail = NULL;   }   CNodeManager::~CNodeManager() {     std::cout<<"CNodeManager 소멸자"<<std::endl; }     int CNodeManager::Start() {     int nMenu = 0;       while (true)     {         std::cout<<"1. 삽입, 2. 삭제, 3.출력, 4 종료"<<std::endl;         std::cin>>nMenu;           switch (nMenu)         {         case eInsert:             this->InsertNode();             break;         case eDel:             this->DeleteNode();             break;         case ePrint:             this->PrintNode();             break;         case eExit:             this->AllDelete();             return eExit;         default:             std::cout<<"잘못 입력하셨습니다."<<std::endl;             break;         }     } }   void CNodeManager::InsertNode() {     int nGetNum = 0;       std::cout<<"저장할 정수를 입력해 주세요"<<std::endl;     std::cin>>nGetNum;       Node *NewNode = new Node;       NewNode->nSaveData = nGetNum;       if( NULL == this->Head )     {//노드가 하나도 없을시         this->Head = NewNode;         this->Tail = NewNode;     }     else     {         this->Head->Prev = NewNode;    //Head의 이전에 추가         NewNode->Next = this->Head;    //새 노드가 맨 앞의 노드와 연결         this->Head = Head->Prev;    //Head를 다시 맨 앞으로.     } }   void CNodeManager::DeleteNode() {     if( NULL == this->Head )     {         std::cout<<"노드가 존재하지 않습니다."<<std::endl;     }     else     {         Node *TempNode = this->Head->Next;        //head의 다음 노드(두번째 노드 주소 복사)           if( this->Head == this->Tail )         {             std::cout<<this->Head->nSaveData<<" 삭제...";             delete Head;             std::cout<<"삭제 완료"<<std::endl;             this->Head = NULL;             this->Tail = NULL;         }         else         {             std::cout<<this->Head->nSaveData<<" 삭제...";             delete Head;             std::cout<<"삭제 완료"<<std::endl;             this->Head = TempNode;            //Head 위치 재 정렬                 this->Head->Prev = NULL;         }     } }   void CNodeManager::PrintNode() {     if( NULL == this->Head )     { //Head가 NULL일떄 == Node가 존재 하지 않을때         std::cout<<"노드가 존재하지 않습니다."<<std::endl;     }     else     {         Node *TempNode = this->Head;           std::cout<<"Head->Tail방향"<<std::endl;         while (true)         {             if( NULL == TempNode )             {                 std::cout<<"출력 끝"<<std::endl;                 break;             }             else             {                 std::cout<<"데이터 값 : "<<TempNode->nSaveData<<std::endl;                 TempNode = TempNode->Next;             }         }           TempNode = this->Tail;           std::cout<<"Tail->Head방향"<<std::endl;         while (true)         {             if( NULL == TempNode )             {                 std::cout<<"출력 끝"<<std::endl;                 break;             }             else             {                 std::cout<<"데이터 값 : "<<TempNode->nSaveData<<std::endl;                 TempNode = TempNode->Prev;             }         }       } }   void CNodeManager::AllDelete() {     while( NULL != this->Head )     {         this->DeleteNode();     } }

main.cpp

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

 

출력결과