daily pastebin goal
5%
SHARE
TWEET

Untitled

a guest Jan 12th, 2018 45 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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
Top