Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

Untitled

a guest Jan 12th, 2018 46 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. #ifndef LINKED_LIST_CS197
  2. #define LINKED_LIST_CS197
  3.  
  4. #include <cassert>
  5. #include <string>
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #include <iostream> //cin, cout, <, >
  9. #include <stdarg.h>
  10.  
  11. using namespace std;
  12.  
  13. template<typename T>
  14. class LinkedList {
  15. private:
  16.   class iterator {
  17.     void operator++() const {
  18.       // Does nothing right now
  19.     }
  20.  
  21.     // Need to add data structures internal to the iterator here
  22.   };
  23.  
  24.   // This class is basically complete. You shouldn't need to modify it.
  25.   class Node {
  26.   public:
  27.     Node() { next = NULL; prev = NULL; }
  28.     ~Node() {}
  29.   public :
  30.     Node *next;
  31.     Node *prev;
  32.     T data;
  33.   };
  34.  
  35.   // Add internal strcutures for the list here
  36.  
  37. public:
  38.   LinkedList();
  39.   ~LinkedList();
  40.    /* -References to the first and last
  41.    */
  42.   Node *first;
  43.   Node *last;
  44.   Node* curr;
  45.   int sizeCounter;
  46.   // methods -- note that the return values are of type T. Don't return a Node!
  47.   void append(T item);
  48.   T get(int idx);
  49.   void insert(int idx, T item);
  50.   void map(T (*pf)(T item));
  51.   T remove(int index);
  52.   int size();
  53.   void unshift(T item);
  54.   void displayForward();
  55.  
  56.   // Iterator methods - not very interesting right now
  57.  
  58.   // These need to return new iterators to the beginning, and AFTER the
  59.   // end of, the sequence, respectively.
  60.   const iterator begin() {
  61.     return NULL;
  62.   }
  63.  
  64.   const iterator end() {
  65.     return NULL;
  66.   }
  67. };
  68.  
  69. // This returns a new, empty Linked List.
  70. template <typename T>
  71. LinkedList<T>::LinkedList() {
  72.     this->curr = new Node();
  73.     this->sizeCounter = 0;
  74.     first = this->curr;
  75. }
  76.  
  77. // Deletes the Linked List. It's not your job to call delete on the
  78. // T item directly because you don't know what it is, but you are still responsible
  79. // for any internal data strcutures you may have allocated.
  80. template <typename T>
  81. LinkedList<T>::~LinkedList() {
  82. }
  83.  
  84. // Adds an item to the end of the sequence (after the tail).
  85. // If the list is empty, then the appended item becomes the head AND the tail.
  86. template <typename T>
  87. void LinkedList<T>::append(T item) {
  88.  
  89.     Node* temp = new Node();
  90.  
  91.     if(sizeCounter == 0)
  92.     {
  93.         this->curr->data = item;
  94.         this->curr->next = new Node(); // create a new next node, i dont think this is necessary but w/e works man
  95.         this->curr = this->curr->next;
  96.         first = this->curr;
  97.         ++sizeCounter;
  98.     }
  99.     else
  100.     {
  101.    // cout<<"|"<<item;
  102.     while(this->curr->next != NULL)
  103.         this->curr = this->curr->next;
  104.  
  105.  
  106.     temp = this->curr; //temp to copy current node to so that it can be ref to by prev in the next node
  107.    
  108.     this->curr->next = new Node(); // create a new next node, i dont think this is necessary but w/e works man    
  109.  
  110.     this->curr = this->curr->next;  //increment to the next empty node
  111.  
  112.     //TO make sure this is not the first node so we don't create a prev ref for it
  113.     this->curr->prev = new Node(); //set prev node ref
  114.     this->curr->prev = temp;
  115.     this->curr->data = item; //set the data item
  116. //       cout<<"->"<<this->curr->data<<" ";;
  117. //   cout<<"Prev was:"<<this->curr->prev->data<<"|";
  118.    
  119.     ++sizeCounter;
  120.     }
  121. }
  122.  
  123. // Returns the item at position idx (0 returns the head).
  124. // You should perform a range check before servicing the request.
  125. template <typename T>
  126. T LinkedList<T>::get(int idx) {
  127.  
  128.     assert(idx >= 0 && idx < sizeCounter);
  129.  
  130.     this->curr = first;
  131.  
  132.     for(int i = 0; i<idx; i++)
  133.         this->curr = this->curr->next;
  134.  
  135.         return this->curr->data;
  136. }
  137.  
  138. // Inserts an item at position idx. If idx is off the end of the sequence,
  139. // it should just append to the end of the sequence. A negative index number
  140. // results in an unshift.
  141. template <typename T>
  142. void LinkedList<T>::insert(int idx, T item) {
  143.     this->curr = first;
  144.     if(idx >= 0 && idx < sizeCounter)
  145.     {
  146.         for(int i = 0; i<idx; i++)
  147.             this->curr = this->curr->next;
  148.         this->curr->data = item;
  149.     }
  150.     else if(idx < 0){unshift(item);}
  151.     else if(idx >= sizeCounter){append(item);}
  152. }
  153.  
  154. // Executes the provided function pointer over all
  155. // elements in the sequence. Each item should be modified in place.
  156. template <typename T>
  157. void LinkedList<T>::map(T (*pf)(T item)) {
  158.     this->curr = first;
  159.     this->curr->data = (*pf)(this->curr->data);
  160.     while(this->curr->next != NULL)
  161.     {
  162.         this->curr = this->curr->next;
  163.         this->curr->data = (*pf)(this->curr->data);
  164.     }
  165.  
  166. }
  167.  
  168. // Removes the item at position 'index'. The removed item should be
  169. // returned.  
  170. // A range check should be performed before servicing the request,
  171. // therefore this method always returns a value.
  172. template <typename T>
  173. T LinkedList<T>::remove(int index) {
  174.    T removedItem;
  175.     assert(index >= 0 && index < sizeCounter);
  176.     this->curr = first;
  177.     for(int i = 0; i<index; i++)
  178.        this->curr = this->curr->next;
  179.  
  180.     removedItem = this->curr->data;
  181.     if(this->curr->prev != NULL)
  182.     {
  183.         Node* temp = this->curr->next;
  184.         this->curr = this->curr->prev;
  185.         this->curr->next = temp;
  186.     }
  187.         else
  188.             this->curr = this->curr->next;
  189.     --sizeCounter;
  190.             return removedItem;
  191. }
  192.  
  193. // Returns the number of items in the sequence. This should
  194. // complete in constant time.
  195. template <typename T>
  196. int LinkedList<T>::size() {
  197.     return sizeCounter;
  198. }
  199.  
  200. // Behaves like append, but inserts the item at the front of the sequence.
  201. // Therefore the unshifted item becomes the new head of the sequence.
  202. template <typename T>
  203. void LinkedList<T>::unshift(T item) {
  204.     Node* temp = new Node();
  205.     this->curr = first;
  206.     this->curr->prev = new Node();
  207.     this->curr = this->curr->prev;
  208.     this->curr->data = item;
  209.     this->curr->next = first;
  210.  
  211.     temp = this->curr;
  212.     first->prev = temp;
  213.     first = temp;
  214.     sizeCounter++;
  215. }
  216. /*  Editional method to display all items of linked list
  217.  */
  218. template <typename T>
  219. void LinkedList<T>::displayForward() {
  220.     cout<<"List (first-->last): ";
  221.     this->curr = first;
  222.  
  223.     while(this->curr != NULL)
  224.     {
  225.         cout<<" "<<this->curr->data;
  226.         this->curr = this->curr->next;
  227.     }
  228.     cout<<endl;
  229. }
  230. #endif
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