fork download 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. template <class Type>
  6. struct nodeType
  7. {
  8.     Type info;
  9.     nodeType<Type> *link;
  10. };
  11.  
  12. template <class Type>
  13. class linkedListIterator
  14. {
  15. public:
  16.     linkedListIterator(); //Default constructor
  17.     linkedListIterator(nodeType<Type> *p); //constructor
  18.     Type operator*(); //overload dereferencing operator * ie. *p=val
  19.     linkedListIterator<Type> operator++(); //overload the PREincrement operator
  20.     //POSTincrement would be linkedListIterator<Type> operator++(int);
  21.     bool operator==(const linkedListIterator<Type>& right) const;
  22.     //overload equality operator. second const is to make function itself const,
  23.     //because it doesn't modify the object
  24.     bool operator!=(const linkedListIterator<Type>& right) const;
  25.     //over not equal to operator. reference param must be const to prevent change.
  26.  
  27. private:
  28.     nodeType<Type> *current; //ptr points to current node in linked list
  29. };//UML on page 281
  30.  
  31. template <class Type>
  32. class linkedListType
  33. {
  34. public:
  35.     const linkedListType<Type>& operator=(const linkedListType<Type>&);
  36.     //overload the assignment operator
  37.  
  38.     void initializeList(); //initialize list into an empty state
  39.     bool isEmptyList() const; //function to determine if list is empty,
  40.                             //doesn't change list, so constant.
  41.     void print() const; //function to output data in each node
  42.     int length() const; //return number of nodes in list
  43.     void destroyList(); //delete all nodes from list, no const, because change
  44.     Type front() const; //return first element of list
  45.     Type back() const; //return last element of list
  46.     //to be derived functions-virtual =0 pure virtual, only overwritten
  47.     virtual bool search(const Type& searchItem) const = 0;// determine if item in list
  48.     virtual void insertFirst(const Type& newItem) = 0; //insert newitem at begin of list
  49.     virtual void insertLast(const Type& newItem) = 0; //insert newitem at end of list
  50.     virtual void deleteNode(const Type& deleteItem) = 0; //delete item from list
  51.  
  52.     //returntype             function make use of the linkedListIterator class?
  53.     linkedListIterator<Type> begin(); //return an iterator at beginning of linked list
  54.     linkedListIterator<Type> end(); //return iterator one element past last element of list
  55.  
  56.     linkedListType(); //default constructor
  57.     linkedListType(const linkedListType<Type>& otherList); //argument constructor
  58.     ~linkedListType(); //destructor
  59.  
  60. protected: //for use in class functions and derived classes/functions
  61.     int count; //number of list items
  62.     nodeType<Type> *first; //pointer to first node of list
  63.     nodeType<Type> *last; //pointer to last node of list
  64.  
  65. private:
  66.     void copyList(const linkedListType<Type>& otherList);
  67.     //function to make a copy of otherlist and assign to this list
  68. };
  69.  
  70. template <class Type>
  71. class unorderedLinkedList: public linkedListType<Type> //inherit public section of lLT class
  72. {
  73. public:
  74.     bool search(const Type& searchItem) const; //const on referenced item, const on function
  75.                                                 //determines if item is in the list
  76.     void insertFirst(const Type& newItem); //insert newitem at beginning of list
  77.     void insertLast(const Type& newItem); //insert newitem at end of list
  78.     void deleteNode(const Type& deleteItem); //delete deleteItem from list
  79. };
  80.  
  81. template <class Type> //default constructor
  82. linkedListIterator<Type>::linkedListIterator()
  83. {   //constructors don't need return type
  84.     current = NULL;
  85. }
  86.  
  87. template <class Type> //argument constructor
  88. linkedListIterator<Type>::linkedListIterator(nodeType<Type> *p)
  89. {
  90.     current = p; //set current to pointer argument
  91. }
  92.  
  93. template <class Type> //overload dereference operator
  94. Type linkedListIterator<Type>::operator*() //return type template
  95. {
  96.     return current->info;
  97. }
  98.  
  99. template <class Type> //overload preincrement operator
  100. linkedListIterator<Type> linkedListIterator<Type>::operator++()
  101. {
  102.     current = current->link;
  103.     return *this;
  104. }
  105.  
  106. template <class Type> //overload equality operator
  107. bool linkedListIterator<Type>::operator==(const linkedListIterator<Type>& right) const
  108. {
  109.     return (current == right.current); //compares both values
  110. }
  111.  
  112. template <class Type> //overload not equal to operator
  113. bool linkedListIterator<Type>::operator!=(const linkedListIterator<Type>& right) const
  114. {
  115.     return (current != right.current);
  116. }
  117.  
  118. template <class Type> //O(1)
  119. bool linkedListType<Type>::isEmptyList() const
  120. {
  121.     return (first == NULL); //if equal to NULL, then list empty
  122. }
  123.  
  124. template <class Type>//O(1)
  125. linkedListType<Type>::linkedListType() //Default constructor
  126. {
  127.     first = NULL;
  128.     last = NULL;
  129.     count = 0; //create empty list
  130. }
  131.  
  132. template <class Type>//O(n)
  133. void linkedListType<Type>::destroyList() //deallocates memory occupied by nodes
  134. {
  135.     nodeType<Type> *temp; //pointer to deallocate memory
  136.  
  137.     while (first != NULL) //while there are nodes, loop
  138.     {
  139.         temp = first;
  140.         first = first->link; //move first onto next node to prevent losing place and
  141.                             // ending up with dangling pointers/memory
  142.         delete temp; //deallocate memory in this node
  143.     }
  144.  
  145.     last = NULL; //initialize last to NULL, while loop already set first to NULL
  146.     count = 0; //no more nodes..
  147. }
  148.  
  149. template <class Type>//O(n)
  150. void linkedListType<Type>::initializeList() //p287, reinitialize list to empty state, delete nodes
  151. {
  152.     destroyList(); //if list has any nodes, delete them
  153. }
  154.  
  155. template <class Type>//O(n)
  156. void linkedListType<Type>::print() const
  157. {
  158.     nodeType<Type> *current; //pointer to traverse list, if you use first, list will be lost
  159.     current = first;
  160.     while (current != NULL) //while more data to print, loop
  161.     {
  162.         cout << current->info << " ";
  163.         current = current->link; //next node
  164.     }
  165. }
  166.  
  167. template <class Type>//O(1)
  168. int linkedListType<Type>::length() const //return int count number
  169. {
  170.     return count; //member var that counts amount of nodes in list
  171. }
  172.  
  173. template <class Type>//O(1)
  174. Type linkedListType<Type>::front() const //returns info in first node
  175. {
  176.     assert(first != NULL); //if list NULL, assert terminates program
  177.     return first->info; //return info of first node
  178. }
  179.  
  180. template <class Type>//O(1)
  181. Type linkedListType<Type>::back() const // returns info in last node
  182. {
  183.     assert(last != NULL); //term if NULL
  184.     return last->info;//info of last node
  185. }
  186.  
  187. //iterators begin and end, for use in for loops?
  188. template <class Type>//O(1)
  189. //Type(iterator)            memberclass::member
  190. linkedListIterator<Type> linkedListType<Type>::begin() //begin iterator
  191. {
  192.     linkedListIterator<Type> temp(first);
  193.     return temp;
  194. }
  195.  
  196. template <class Type>//O(1)
  197. //Type(iterator)            memberclass::member
  198. linkedListIterator<Type> linkedListType<Type>::end() //end iterator
  199. {
  200.     linkedListIterator<Type> temp(NULL);
  201.     return temp;
  202. }
  203.  
  204. //make deep copy of list
  205. template <class Type>//O(n)
  206. void linkedListType<Type>::copyList(const linkedListType<Type>& otherList)//const, don't want to change list
  207. {   //create ptrs to be used
  208.     nodeType<Type> *newNode; //ptr to create a node
  209.     nodeType<Type> *current; //ptr to traverse list
  210.  
  211.     if (first != NULL) //if list nonempty, then make it empty
  212.         destroyList();
  213.  
  214.     if (otherList.first == NULL) //otherList is empty
  215.     {
  216.         first = NULL;
  217.         last = NULL;
  218.         count = 0;
  219.     }
  220.     else
  221.     {
  222.         current = otherList.first; //current points to list to be copied
  223.         count = otherList.count;
  224.         //copy first node-head
  225.         first = new nodeType<Type>; //create node
  226.         first->info = current->info; //copy info
  227.         first->link = NULL; //set the link field of node to NULL
  228.         last = first; //make last point to first
  229.         current = current->link; //point current to next node
  230.  
  231.         //copy remaining list
  232.         while (current != NULL)
  233.         {
  234.             newNode = new nodeType<Type>; //create node
  235.             newNode->info = current->info; //copy info
  236.             newNode->link = NULL; //set link of newNode to NULL
  237.             last->link = newNode; //attach newnode after last
  238.             last = newNode; //make last point to actual last
  239.             current = current->link; //point current to next node
  240.         }
  241.     }
  242. }
  243.  
  244. template <class Type>//O(n)
  245. linkedListType<Type>::~linkedListType() //destructor
  246. {
  247.     destroyList();
  248. }
  249.  
  250. template<class Type>//O(n)
  251. linkedListType<Type>::linkedListType(const linkedListType<Type>& otherList) //copy constructor
  252. {
  253.     first = NULL; //must be NULL to use copyList
  254.     copyList(otherList);
  255. }
  256.  
  257. template <class Type>//O(n)
  258. const linkedListType<Type>& linkedListType<Type>::operator=(const linkedListType<Type>& otherList)
  259. //overloaded assignment operator
  260. {
  261.     if (this != &otherList) //avoid self-copy
  262.     {
  263.         copyList(otherList);
  264.     }
  265.  
  266.     return *this; //return value of this pointer
  267. }
  268.  
  269. template <class Type>//O(n)
  270. bool unorderedLinkedList<Type>::search(const Type& searchItem) const
  271. { //search for item then return true if found
  272.     nodeType<Type> *current; //create pointer to traverse list
  273.     bool found = false; //loop controll variable, if true stop
  274.     current = first; //current points to first node in list
  275.  
  276.     while (current != NULL && !found) //repeat until end of list, and found is true
  277.     //above will keep looping while found is not true, the moment found is true,
  278.     //i.e. opposite of !found, it will stop the loop.
  279.         if (current->info == searchItem) //searchItem is found
  280.             found = true;
  281.         else
  282.             current = current->link; //point current to next node, move through list
  283.     return found;
  284. }
  285.  
  286. template <class Type>//O(1)
  287. void unorderedLinkedList<Type>::insertFirst(const Type& newItem)
  288. {
  289.     nodeType<Type> *newNode; //pointer to create the new node
  290.     newNode = new nodeType<Type>; //allocate memory for and create node
  291.     newNode->info = newItem; //store new item inside new node
  292.     newNode->link = first; //insert newnode before first
  293.     first = newNode; //make first point to actual first node
  294.     count++; //increment count, size of list
  295.  
  296.     if (last == NULL)
  297.         last = newNode; //if list was empty, set last to point to newnode as last
  298. }
  299.  
  300. template <class Type>//O(1)
  301. void unorderedLinkedList<Type>::insertLast(const Type& newItem)
  302. {
  303.     nodeType<Type> *newNode; //pointer to create new node
  304.     newNode = new nodeType<Type>; //allocate new memory for node and create it
  305.     newNode->info = newItem; //store new item in the node
  306.     newNode->link = NULL; //set link of newnode to NULL, it's at end of list after all
  307.  
  308.     if (first == NULL) //if the list is empty, newNode is both first and last node
  309.     {
  310.         first = newNode;
  311.         last = newNode;
  312.         count++; //increment size/counter of list
  313.     }
  314.     else //list not empty, insert newnode after last
  315.     {
  316.         last->link = newNode; //insert newNode after last
  317.         last = newNode; //make last point to actual last node in list
  318.         count++; //increment list size count
  319.     }
  320. }
  321.  
  322. int main()
  323. {
  324.     cout << "Hello world!" << endl;
  325.     return 0;
  326. }//UML on page 285
  327.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
prog.cpp: In member function ‘bool unorderedLinkedList<Type>::search(const Type&) const’:
prog.cpp:274:15: error: ‘first’ was not declared in this scope
prog.cpp: In member function ‘void unorderedLinkedList<Type>::insertFirst(const Type&)’:
prog.cpp:292:21: error: ‘first’ was not declared in this scope
prog.cpp:294:5: error: ‘count’ was not declared in this scope
prog.cpp:296:9: error: ‘last’ was not declared in this scope
prog.cpp: In member function ‘void unorderedLinkedList<Type>::insertLast(const Type&)’:
prog.cpp:308:9: error: ‘first’ was not declared in this scope
prog.cpp:311:9: error: ‘last’ was not declared in this scope
prog.cpp:312:9: error: ‘count’ was not declared in this scope
prog.cpp:316:9: error: ‘last’ was not declared in this scope
prog.cpp:318:9: error: ‘count’ was not declared in this scope
stdout 
Standard output is empty
https://ideone.com/SN2R99
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!