Linked List(링크드 리스트)

           

/* linkedlist.cpp */

#include <iostream>

using namespace std;

 

class Node

{

public:

        Node* prevNode;

        Node* nextNode;

        int nodeData;

        int nodeIndex;

 

        Node()

        {

               prevNode = NULL;

               nextNode = NULL;

               nodeData = 0;

               nodeIndex = 0;

        }

        Node(int _data)

        {

               prevNode = NULL;

               nextNode = NULL;

               nodeData = _data;

               nodeIndex = 0;

        }

};

 

class LinkedList{

private:

        int count;

        Node* first;

public:

        LinkedList()

        {

               count = 0;

               first = new Node();

        }

        void insert(int add)

        {

               Node* NewNode = new Node(add);

               if(first->nextNode == NULL) // 삽입하려는 노드가 첫번째 노드일 경우

               {

                       first->nextNode = NewNode;

                       NewNode->prevNode = first;

                       NewNode->nodeIndex = count;

               }

               else // 삽입하려는 노드가 첫번째 노드가 아닐 경우

               {

                       Node* NowNode = first;

                       while(NowNode->nextNode != NULL) // NowNode로 nextNode가 NULL일 경우까지 계속해서 search

                       {         

                              NowNode = NowNode->nextNode;

                       }

                       NowNode->nextNode = NewNode; // NowNode 다음노드에 새로 삽입하려는 노드가 들어감.

                       NewNode->prevNode = NowNode; // 새로 삽입하려는 노드의 prevNode는 NowNode를 가르켜야한다.

                       NewNode->nodeIndex = count;

               }

               count++;

        }

        void showAll()

        {

               Node* NowNode = first;

               if(NowNode->nextNode == NULL)

               {

                       cout << "데이터가 하나도 없습니다. " << endl;

                       return;

               }

               while(NowNode->nextNode != NULL)

               {

                       NowNode = NowNode->nextNode; // nownode를 이용하여 노드 데이터들을 출력!!

                       cout << NowNode->nodeData << "\t";

               }

        }

        void remove(int index)

        {

               Node* NowNode = first;

               if(NowNode->nextNode == NULL) // 노드가 없는 경우

               {

                       cout << "데이터가 하나도 없습니다." << endl;

               }

               else

               {

                       while(NowNode->nextNode != NULL)

                       {

                              NowNode = NowNode->nextNode;

                              if(NowNode->nodeIndex == index) // 삭제하려는 노드의 인덱스 찾기

                              {

                                      NowNode = NowNode->prevNode;

                                      if(NowNode->nextNode->nextNode == NULL) // 만약에 지우려는 노드가 마지막 노드일 경우

                                      {

                                             delete NowNode->nextNode; // 노드 삭제

                                             NowNode->nextNode = NULL; // NULL처리

                                      }

                                      else

                                      {

                                             NowNode->nextNode = NowNode->nextNode->nextNode; // 삭제하려는 노드를 지우고 그 사이를 다시 이어주는 과정

                                             delete NowNode->nextNode->prevNode; //

                                             NowNode->nextNode->prevNode = NowNode;

                                      }

                                      break;

                              }

                       }

                       while(NowNode->nextNode != NULL)

                       {

                              NowNode = NowNode->nextNode; // 하나가 줄었으니 밑의 노드들의 인덱스 하나씩 감소

                              NowNode->nodeIndex -= 1;

                       }

                       count--;

               }

        }

        int getCount()

        {

               return count;

        }

        ~LinkedList() // 링크드리스트 삭제

        {

               Node* NowNode = first;

               if(NowNode->nextNode == NULL)

               {

                       return;

               }

               NowNode = NowNode->nextNode;

               while(NowNode->nextNode != NULL)

               {

                       NowNode = NowNode->nextNode;

                       delete NowNode->prevNode;

               }

               delete NowNode;

        }

};

 

int main()

{

        LinkedList list;

        int op=0;

        int tempNum;

 

        cout <<"============== List Manager ============== " << endl;

        while(1)

        {

               cout << "--------------------------" << endl;

               cout << "1. Insert " << endl;

               cout << "2. Remove " << endl;

               cout << "3. Show " << endl;

               cout << "4. 현재 데이터 개수 출력" << endl;

               cout << "5. 종료" << endl;

               cin >> op;

               switch(op)

               {

               case 1:

                       cout << "\n추가할 정수 입력 : " ;

                       cin >> tempNum;

                       list.insert(tempNum);

                       break;

               case 2:

                       cout << "\n제거할 노드의 인덱스 입력(0부터) : " ;

                       cin >> tempNum;

                       if(tempNum < 0 || tempNum >= list.getCount())

                       {

                              cout << "error!!" << endl;

                              break;

                       }

                       list.remove(tempNum);

                       break;

               case 3:

                       cout << endl;

                       list.showAll();

                       cout << endl;

                       break;

               case 4:

                       cout << "현재 노드의 총 개수는 " << list.getCount() << " 개입니다." << endl;

                       break;

               case 5:

                       return 0;

               default:

                       cout << "error!! 올바른 숫자를 입력해주세요 " << endl;

                       break;

               }

        }

        return 0;

}