Advertisement
Guest User

linked list in c++

a guest
Oct 23rd, 2019
240
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.73 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <memory>
  4.  
  5. using namespace std;  
  6.  
  7. /* Link list node */
  8. class Node
  9. {
  10. public:
  11.     int key;  
  12.     Node* next;  
  13. };  
  14.  
  15. class NodeUtils
  16. {
  17. public:
  18.     void push(Node** head_ref, int new_key)  
  19.     {  
  20.         /* allocate node */
  21.         Node* new_node = new Node();
  22.  
  23.         /* put in the key */
  24.         new_node->key = new_key;  
  25.  
  26.         /* link the old list off the new node */
  27.         new_node->next = (*head_ref);  
  28.  
  29.         /* move the head to point to the new node */
  30.         (*head_ref) = new_node;  
  31.     }  
  32.  
  33.     void listall(Node* head)  
  34.     {  
  35.         Node* current = head;
  36.  
  37.         while(current != nullptr) {
  38.             cout << current->key;
  39.             current = current->next;
  40.             if(current) cout << ", ";
  41.         }
  42.         cout << endl;
  43.     }
  44.  
  45.     /* searches for the value x in linked list */
  46.     bool search(Node* head, int x)  
  47.     {  
  48.         Node* current = head;
  49.         while(current != nullptr) {  
  50.             if (current->key == x)  
  51.                 return true;  
  52.             current = current->next;  
  53.         }  
  54.         return false;  
  55.     }
  56.  
  57.     unsigned    count(Node* head)
  58.     {
  59.         Node* current = head;
  60.         unsigned count = 0;
  61.        
  62.         while(current != nullptr) {
  63.             current = current->next;
  64.             count++;
  65.         }
  66.  
  67.         return count;
  68.     }
  69.  
  70.     void
  71.     sortasc(Node* head)
  72.     {
  73.         Node* temphead = head;
  74.         int tempkey;
  75.         unsigned counter = count(head);
  76.  
  77.         for(unsigned n = 0; n < counter; n++) {
  78.             while(temphead->next) {
  79.                 if(temphead->key > temphead->next->key) {      
  80.                     tempkey = temphead->key;
  81.  
  82.                     temphead->key = temphead->next->key;
  83.                     temphead->next->key = tempkey;
  84.                 }
  85.                 temphead = temphead->next;
  86.             }
  87.             temphead = head;
  88.         }
  89.     }
  90.  
  91.     void sortdsc(Node* head)
  92.     {
  93.         Node* temphead = head;
  94.         int tempkey;
  95.         unsigned counter = count(head);
  96.  
  97.         for(unsigned n = 0; n < counter; n++) {
  98.             while(temphead->next) {
  99.                 if(temphead->key < temphead->next->key) {      
  100.                     tempkey = temphead->key;
  101.  
  102.                     temphead->key = temphead->next->key;
  103.                     temphead->next->key = tempkey;
  104.                 }
  105.                 temphead = temphead->next;
  106.             }
  107.             temphead = head;
  108.         }
  109.     }
  110. };
  111.  
  112. int
  113. main(int argc, char** argv)  
  114. {  
  115.     /* Start with the empty list */
  116.     unique_ptr<NodeUtils> utl = make_unique<NodeUtils>();
  117.     Node* head = nullptr;  
  118.  
  119.     utl->push(&head, 10);  
  120.     utl->push(&head, 30);  
  121.     utl->push(&head, 11);  
  122.     utl->push(&head, 21);  
  123.     utl->push(&head, 14);  
  124.  
  125.     utl->search(head, 21)? cout << "Node found" << endl :
  126.         cout << "Node not found" << endl;
  127.  
  128.     utl->listall(head);
  129.     cout << "number of elements: " << utl->count(head) << endl;
  130.     utl->sortasc(head);
  131.  
  132.     cout << "Sorted ascending:" << endl;
  133.     utl->listall(head);
  134.     utl->sortdsc(head);
  135.  
  136.     cout << "Sorted descending:" << endl;
  137.     utl->sortdsc(head);
  138.     utl->listall(head);
  139.  
  140.     return EXIT_SUCCESS;  
  141. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement