SHARE
TWEET

Untitled

a guest Jun 27th, 2017 96 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <list>
  3. using namespace std;
  4. typedef int element_type;
  5. typedef element_type& reference;
  6. typedef const element_type& const_reference;
  7.  
  8. class linkedlist{
  9. public:
  10.     linkedlist();   //done
  11.     explicit linkedlist(unsigned int n);
  12.     ~linkedlist(); 
  13.     bool empty() const; //done
  14.     void clear();   //done
  15.     reference back();   //done
  16.     const_reference back() const;   //done
  17.     reference front();  //done
  18.     const_reference front() const;  //done
  19.     linkedlist& operator=(const linkedlist& l);
  20.     void pop_back ();   //done
  21.     void pop_front ();  //done
  22.     void push_back ( const element_type& x );   //done
  23.     void push_front ( const element_type& x );  //done
  24.     void sort ();   //did not finish
  25.     void check() const; //done
  26.     void rcheck() const;    //done
  27.     void print();
  28.    
  29.    
  30.    
  31.  
  32. private:
  33.     struct Node{
  34.     element_type data;
  35.     Node* next;
  36.     Node* prev;
  37.     };
  38.     Node* head;
  39.     Node* tail;
  40.     Node* current;
  41.     element_type list_size;
  42.  
  43. };
  44.  
  45. linkedlist::linkedlist()    //default constructor
  46. {
  47.     head = new Node;
  48.     tail = new Node;
  49.     head->next = tail;
  50.     head->prev = NULL;
  51.     tail->next = NULL;
  52.     tail->prev = head;
  53.     current = head;
  54.     list_size = 0;
  55. }
  56.  
  57. linkedlist::linkedlist(unsigned int n)  //explicit constructor
  58. {
  59.     element_type size = n;
  60.     head = new Node;
  61.     tail = new Node;
  62.     current = head;
  63.     head->prev = NULL;
  64.     tail->next = NULL;
  65.  
  66.     for(int i = 0; i < size; i++)
  67.     {
  68.         current->next = new Node;
  69.         Node * temp = current;
  70.         current = current->next;
  71.         current->prev = temp;
  72.         current->data = i;
  73.     }
  74.     current->next = tail;
  75.     tail->prev = current;
  76.     list_size = n;
  77. }
  78.  
  79. linkedlist::~linkedlist()   //ask about this
  80. {
  81.     /*clear();
  82.     delete head;
  83.     delete tail;
  84.     */
  85. }
  86.  
  87. bool linkedlist:: empty() const     // works
  88. {
  89.     if( head->next == tail )
  90.     {
  91.         return true;
  92.     }
  93.     else
  94.     {
  95.         return false;
  96.     }
  97. }
  98.  
  99. void linkedlist::push_front ( const element_type& x )   //works
  100. {
  101.     if(list_size == 0)
  102.     {
  103.     head->next = new Node;
  104.     current = head->next;
  105.     current->next = tail;
  106.     current->prev = head;
  107.     tail->prev = current;
  108.     current->data = x;
  109.     list_size++;
  110.     }
  111.     else
  112.     {
  113.         current = head->next;
  114.         head->next = new Node;
  115.         current->prev = head->next;
  116.         head->next->prev = head;
  117.         head->next->next = current;
  118.         current = head->next;
  119.         current->data = x;
  120.         list_size++;
  121.     }
  122.        
  123.  
  124. }
  125.  
  126. void linkedlist:: push_back (const element_type& x) //works
  127. {
  128.     if(list_size == 0)
  129.     {
  130.         tail->prev = new Node;
  131.         current = tail->prev;
  132.         current->next = tail;
  133.         current->prev = head;
  134.         head->next = current;
  135.         current->data = x;
  136.         list_size++;
  137.     }
  138.     else
  139.     {
  140.         current = tail->prev;
  141.         tail->prev = new Node;
  142.         current->next = tail->prev;
  143.         tail->prev->prev = current;
  144.         current = tail->prev;
  145.         current->next = tail;
  146.         current->data = x;
  147.         list_size++;
  148.     }
  149. }
  150.  
  151. reference linkedlist:: front()  //works
  152. {
  153.     return head->next->data;
  154. }
  155.  
  156. const_reference linkedlist:: front() const  //works
  157. {
  158.     return head->next->data;
  159. }
  160.  
  161. reference linkedlist:: back()   //works
  162. {
  163.     return tail->prev->data;
  164. }
  165.  
  166. const_reference linkedlist:: back() const   //works
  167. {
  168.     return tail->prev->data;
  169. }
  170.  
  171. void linkedlist:: pop_front()   //works
  172. {
  173.     current = head->next;
  174.     head->next = current->next;
  175.     current->next->prev = head;
  176.     current->next = NULL;
  177.     current->prev = NULL;
  178.     delete current;
  179.     list_size--;
  180. }
  181.  
  182. void linkedlist:: pop_back()    //works
  183. {
  184.     current = tail->prev;
  185.     current->prev->next = tail;
  186.     tail->prev = current->prev;
  187.     current->next = NULL;
  188.     current->prev = NULL;
  189.     delete current;
  190.     list_size--;
  191. }
  192.  
  193. void linkedlist:: clear()   //works
  194. {
  195.     Node * tmp;
  196.     Node * traverse = head->next;
  197.  
  198.     while(traverse != NULL)
  199.     {
  200.         tmp = traverse;
  201.         traverse = traverse->next;
  202.         delete tmp;
  203.     }
  204.     current = head;
  205.     head->next = tail;
  206.     tail->prev = head;
  207.     list_size = 0;
  208.  
  209. }
  210.  
  211. void linkedlist::check() const  //works
  212. {
  213.     Node *temp_current;
  214.     temp_current = head->next;
  215.  
  216.     for(int i = 0; i < list_size; i++)
  217.     {
  218.         cout<< temp_current->data << '\n';
  219.         temp_current = temp_current->next;
  220.     }
  221.     if(list_size > 0)
  222.     {
  223.     cout<< "List size: " << list_size << '\n';
  224.     cout<< "Front element: " << front() << '\n';
  225.     cout<< "Back element: " << back() << '\n';
  226.     cout<< "Front element minus 1: " << front()-1 << '\n';
  227.     cout<< "Back element minus 1: " << back()-1 << '\n';
  228.     cout<< "Empty?: " << empty() << '\n';
  229.     }
  230.     else
  231.     {
  232.         cout<< "List size: " << list_size << '\n';
  233.         cout<< "Empty?: " << empty() << '\n';
  234.     }
  235. }
  236.  
  237. void linkedlist::rcheck() const //works
  238. {
  239.     Node *temp_current;
  240.     temp_current = tail->prev;
  241.  
  242.     for(int i = list_size; i > 0; i--)
  243.     {
  244.         cout<< temp_current->data << '\n';
  245.         temp_current = temp_current->prev;
  246.     }
  247. }
  248.  
  249. linkedlist& linkedlist::operator=(const linkedlist& l)
  250. {
  251.    
  252.     if(this ==&l)
  253.     {
  254.         return *this;
  255.     }
  256.  
  257.     clear();
  258.     Node* tmp = l.head;
  259.     Node* temp;
  260.     current = head;
  261.     while(tmp!= l.tail)
  262.     {
  263.         current->next = new Node;
  264.         temp = current;
  265.         current = current->next;
  266.         current->prev = temp;
  267.         tmp = tmp->next;
  268.         current->data = tmp->data;
  269.     }
  270.     list_size = l.list_size;
  271.     current->next = tail;
  272.     tail->prev = current;
  273.     return *this;
  274. }
  275.  
  276. void linkedlist::sort()
  277. {
  278.     //start iterating at head
  279.     Node* current = head->next;
  280.     //iterate until last node in list
  281.     while (current->next != NULL) {
  282.         //set smallest as current
  283.         Node* smallest = current;
  284.         //iterator starts at the next
  285.         Node* iterator = current->next;
  286.         //iterate through rest of list finding smallest node
  287.         while (iterator->next != NULL) {
  288.            
  289.             if (iterator->data < smallest->data)
  290.                 smallest = iterator;
  291.             iterator = iterator->next;
  292.         }
  293.         //if current isn't smallest swith em
  294.        
  295.  
  296.         if (current != smallest) {
  297.             //current->prev is null then its head, swith with smallest
  298.             if (current->prev == NULL) {
  299.                 head = smallest;
  300.             }
  301.             //get temp vars to use for current from smallest
  302.             Node *s_next = smallest->next;
  303.             Node *s_prev = smallest->prev;
  304.            
  305.            
  306.             Node *c_next = current->next;
  307.             Node *c_prev = current->prev;
  308.            
  309.             //set smallest links to currents;
  310.            
  311.            
  312.             smallest->next = c_next;
  313.             if (smallest->next != NULL)
  314.                 smallest->next->prev = smallest;
  315.             smallest->prev = c_prev;
  316.             if (smallest->prev != NULL)
  317.                 smallest->prev->next = smallest;
  318.                
  319.             //set currents links to saved smallests
  320.            
  321.             current->next = s_next;
  322.             if (current->next != NULL)
  323.                 current->next->prev = current;
  324.             current->prev = s_prev;
  325.             if (current->prev != NULL)
  326.                 current->prev->next = current;
  327.         }  
  328.                
  329.         //go to next in list
  330.         current = smallest->next;
  331.     }
  332. }
  333.  
  334. void linkedlist::print()
  335. {
  336.     Node* it = head;
  337.     while (it != NULL){
  338.         cout << it->data << " ";
  339.         it = it->next;
  340.     }
  341.     cout << endl;
  342. }
  343.  
  344.  
  345. int main()
  346. {
  347.     linkedlist *L1 = new linkedlist();
  348.     L1->push_back(4);
  349.     L1->push_back(5);
  350.     L1->push_back(2);
  351.     L1->push_back(3);
  352.     L1->print();
  353.     L1->sort();
  354.     L1->print();
  355.     L1->clear();
  356. /*linkedlist L3;
  357. L3.push_front(5);
  358. L3.push_front(6);
  359. L3.push_front(2);
  360. L3.push_front(10);
  361. L3.push_front(99);
  362. L3.push_front(40);
  363. L3.push_front(1);
  364. L3.push_front(8);
  365. L3.push_front(1000);
  366. L3.sort();
  367. */
  368.  
  369.    
  370.    
  371.    
  372.    
  373.  
  374.    
  375.    
  376.    
  377.  
  378.    
  379.  
  380. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top