LinkedList

소스참고!

1. 1. 1. #ifndef _SINGLYLINKEDLIST_
      2. #define _SINGLYLINKEDLIST_
      3.  
      4. using namespace std;
      5.  
      6. template <class T>
      7. class SinglyLinkedList;
      8.  
      9. template <class T>
      10. class ChainNode
      11. {
      12. friend class SinglyLinkedList<T>;
      13. private:
      14.     T data;
      15.     ChainNode<T>* link;
      16.    
      17. public:
      18.     /* constructor */
      19.     ChainNode() {}
      20.     ChainNode(const T& data) {this->data = data;}
      21.     ChainNode(const T& data, ChainNode<T> *link) {this->data = data; this->link = link;}
      22. };
      23.  
      24. template <class T>
      25. class SinglyLinkedList
      26. {
      27. private:
      28.     ChainNode<T> *first;
      29. public:
      30.     /* constructor */
      31.     SinglyLinkedList() { first = 0; }
      32.     /* destructor */
      33.     ~SinglyLinkedList();
      34.     /* method */
      35.     bool IsEmpty() const { return first == 0;} // 리스트가 empty인지 확인한다
      36.     int SearchofIndex(const T& theElement) const; // 리스트의 원소를 조사해 인덱스를 출력
      37.     void Delete(int theIndex); // 리스트의 index번째 원소를 제거한다.
      38.     T DeleteFront(); // 리스트의 첫 원소를 제거하고 제거되는 원소를 반환한다.
      39.     void Insert(int theIndex, const T& theElement); // 리스트의 index번째에 원소를 추가한다.
      40.     T GetElement(int theIndex); // 리스트의 index번째 원소를 가져온다.
      41.     int GetLength() const; // 리스트의 전체 길이를 가져온다.
      42.     void ShowLinkedList(); // 전체 리스트를 출력한다.
      43. };
      44.  
      45. template <class T>
      46. SinglyLinkedList<T>::~SinglyLinkedList()
      47. {
      48.     // Deleted All nodes in LinkedList
      49.     while(first != NULL) {
      50.         ChainNode<T> *next = first->link;
      51.         delete first;
      52.         first = next;
      53.     }
      54. }
      55.  
      56. template <class T>
      57. int SinglyLinkedList<T>::SearchofIndex(const T& theElement) const
      58. {
      59.     // search the chain for the Element
      60.     ChainNode<T>* currentNode = first;
      61.     int index = 0; // index of currentNode
      62.     for(int index = 0;index<GetLength();index++) {
      63.         if(currentNode->data == theElement)
      64.             return index;
      65.         currentNode = currentNode->link;
      66.     }
      67.     return -1;
      68. }
      69.  
      70. template <class T>
      71. T SinglyLinkedList<T>::DeleteFront()
      72. {
      73.     T item;
      74.     if(this->IsEmpty() == true)
      75.         item = (T)-1;
      76.     else {
      77.         cout<<"!"<<endl;
      78.         item = first->data;
      79.         ChainNode<T> * deleteNode = first;
      80.         first = first->link;
      81.         delete deleteNode;
      82.     }
      83.     return item;
      84. }
      85.  
      86. template <class T>
      87. void SinglyLinkedList<T>::Delete(int theIndex)
      88. {
      89.     // Deleted the chain of index;
      90.     ChainNode<T>* deleteNode = first;
      91.  
      92.     if(theIndex < 0)
      93.         throw "Bad insert Index";
      94.  
      95.     if(first == 0)
      96.         throw "Cannot delete from empty chain";
      97.  
      98.    
      99.     if(theIndex == 0) {
      100.         first = first->link;
      101.     }
      102.     else {
      103.         ChainNode<T>* bfDeleteNode = first;
      104.         for(int i=0; i<theIndex-1; i++) { //moving the index
      105.             bfDeleteNode = bfDeleteNode->link;
      106.         }
      107.         if(bfDeleteNode == NULL)
      108.             throw "Delete element does not exist";
      109.         deleteNode = bfDeleteNode->link;
      110.         bfDeleteNode->link = bfDeleteNode->link->link;
      111.     }
      112.     delete deleteNode;
      113. }
      114.  
      115. template <class T>
      116. void SinglyLinkedList<T>::Insert(int theIndex, const T& theElement)
      117. {
      118.     // Inserted the chain of index;
      119.     ChainNode<T> *bfInsertNode = first;
      120.  
      121.     if(theIndex < 0)
      122.         throw "Bad insert Index";
      123.  
      124.     if(theIndex == 0) { // Insert at front
      125.         first = new ChainNode<T>(theElement,first);
      126.     }
      127.     else
      128.     {
      129.         for(int i=0; i<theIndex-1; i++) { //moving the index
      130.             bfInsertNode = bfInsertNode->link;
      131.         }
      132.         bfInsertNode->link = new ChainNode<T>(theElement,bfInsertNode->link);
      133.     }
      134. }
      135.  
      136. template <class T>
      137. T SinglyLinkedList<T>::GetElement(int theIndex)
      138. {
      139.     T element;
      140.     ChainNode<T>* currentNode = first;
      141.  
      142.     if(theIndex < 0)
      143.         throw "Bad insert Index";
      144.     for(int i=0; i<theIndex; i++) { //moving the index
      145.         if(currentNode == NULL) {
      146.             cout<<"Bad insert Index"<<endl;
      147.             return (T)-1;
      148.         }
      149.         currentNode = currentNode->link;
      150.     }
      151.     element = currentNode->data;
      152.     return element;
      153. }
      154.  
      155. template <class T>
      156. int SinglyLinkedList<T>::GetLength() const
      157. {
      158.     int count = 0;
      159.     ChainNode<T>* searchNode = first;
      160.     for(int i=0; searchNode != NULL; i++) {
      161.         count ++;
      162.         searchNode = searchNode->link;
      163.     }
      164.     return count;
      165. }
      166.  
      167. template <class T>
      168. void SinglyLinkedList<T>::ShowLinkedList()
      169. {
      170.     cout<<"Current State : first ";
      171.     for(int i=0; i<GetLength();i++) {
      172.         cout<<GetElement(i)<<" ";
      173.     }
      174. }
      175.  
      176. #endif

1. #include <iostream>
2. #include <string>
3. #include "SinglyLinkedList.h"
4.  
5. using namespace std;
6.  
7. int main()
8. {
9.     SinglyLinkedList<int> chain;    // a chain list object
10.  
11.     while(1)
12.     {
13.         cerr << "Chain > " << endl;
14.         char command[256];
15.         cin >> command;
16.        
17.         if(strcmp(command, "quit") == 0)
18.             break;  // stop the program
19.  
20.        
21.         if(strcmp (command, "insert") == 0)
22.         {   // insert command
23.             int theIndex;
24.             cin >> theIndex;
25.  
26.             int item;
27.             cin >> item;
28.             chain.Insert(theIndex,item);
29.         }
30.         else if(strcmp (command, "delfront") == 0)
31.         {   // delete front command
32.             int item = chain.DeleteFront();
33.             if(item != -1)
34.                 cout << "\tOutput : " << item;
35.             else
36.                 cout << "No deletion due to empty list";
37.             cout << endl;
38.         }
39.         else if(strcmp (command, "del") == 0)
40.         {
41.             int theIndex;
42.             cin >> theIndex;
43.             chain.Delete(theIndex);
44.         }
45.         else if(strcmp(command,"getElement") == 0)
46.         {
47.             int theIndex;
48.             if(chain.IsEmpty() == 1 )
49.                 cout<<"Empty list"<<endl;
50.             else {
51.                 cin >> theIndex;
52.                 if(chain.GetElement(theIndex) != -1)
53.                     cout <<theIndex<<" Element data : "<<chain.GetElement(theIndex)<<endl;
54.             }
55.         }
56.         else if(strcmp(command,"search") == 0)
57.         {
58.             int item;
59.             cin >> item;
60.             if(chain.IsEmpty() == 1 )
61.                 cout<<"Empty list"<<endl;
62.             else {
63.                 if(chain.SearchofIndex(item) == -1)
64.                     cout<<"Not searched data of list"<<endl;
65.                 else
66.                     cout <<item<<" Index : "<<chain.SearchofIndex(item)<<endl;
67.             }
68.         }
69.         else if(strcmp(command, "menu") == 0)
70.         {
71.             cout<<"insert : insert"<<endl;
72.             cout<<"deletefront : delfront"<<endl;
73.             cout<<"delete : del"<<endl;
74.             cout<<"getElement : getElement"<<endl;
75.             cout<<"search : search"<<endl;
76.         }
77.         // show the current list
78.         chain.ShowLinkedList();
79.         cout << endl;
80.     }
81.     return 1;
82. }