Guest User

linkedList.h

a guest
Jun 14th, 2011
453
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 11.36 KB | None | 0 0
  1. #ifndef H_LinkedListType
  2. #define H_LinkedListType
  3.  
  4. #include <iostream>
  5. #include <cassert>
  6.  
  7. using namespace std;
  8.  
  9. //Definition of the node
  10.  
  11. template <class Type>
  12. struct nodeType
  13. {
  14.     Type info;
  15.     nodeType<Type> *link;
  16. };
  17.  
  18. //***********************************************************
  19. // Author: D.S. Malik
  20. //
  21. // This class specifies the members to implement an iterator
  22. // to a linked list.
  23. //***********************************************************
  24.  
  25. template <class Type>
  26. class linkedListIterator
  27. {
  28. public:
  29.     linkedListIterator();
  30.       //Default constructor
  31.       //Postcondition: current = NULL;
  32.  
  33.     linkedListIterator(nodeType<Type> *ptr);
  34.       //Constructor with a parameter.
  35.       //Postcondition: current = ptr;
  36.  
  37.     Type operator*();
  38.       //Function to overload the dereferencing operator *.
  39.       //Postcondition: Returns the info contained in the node.
  40.  
  41.     linkedListIterator<Type> operator++();    
  42.       //Overload the preincrement operator.
  43.       //Postcondition: The iterator is advanced to the next node.
  44.  
  45.     bool operator==(const linkedListIterator<Type>& right) const;
  46.       //Overload the equality operator.
  47.       //Postcondition: Returns true if this iterator is equal to
  48.       //    the iterator specified by right, otherwise it returns
  49.       //    false.
  50.  
  51.     bool operator!=(const linkedListIterator<Type>& right) const;
  52.       //Overload the not equal to operator.
  53.       //Postcondition: Returns true if this iterator is not equal to
  54.       //    the iterator specified by right, otherwise it returns
  55.       //    false.
  56.  
  57. private:
  58.     nodeType<Type> *current; //pointer to point to the current
  59.                              //node in the linked list
  60. };
  61.  
  62.  
  63. template <class Type>
  64. linkedListIterator<Type>::linkedListIterator()
  65. {
  66.     current = NULL;
  67. }
  68.  
  69. template <class Type>
  70. linkedListIterator<Type>::
  71.                   linkedListIterator(nodeType<Type> *ptr)
  72. {
  73.     current = ptr;
  74. }
  75.  
  76. template <class Type>
  77. Type linkedListIterator<Type>::operator*()
  78. {
  79.     return current->info;
  80. }
  81.  
  82. template <class Type>
  83. linkedListIterator<Type> linkedListIterator<Type>::operator++()  
  84. {
  85.     current = current->link;
  86.  
  87.     return *this;
  88. }
  89.  
  90. template <class Type>
  91. bool linkedListIterator<Type>::operator==
  92.                (const linkedListIterator<Type>& right) const
  93. {
  94.     return (current == right.current);
  95. }
  96.  
  97. template <class Type>
  98. bool linkedListIterator<Type>::operator!=
  99.                  (const linkedListIterator<Type>& right) const
  100. {   return (current != right.current);
  101. }
  102.  
  103.  
  104. //***********************************************************
  105. // Author: D.S. Malik
  106. //
  107. // This class specifies the members to implement the basic
  108. // properties of a linked list. This is an abstract class.
  109. // We cannot instantiate an object of this class.
  110. //***********************************************************
  111.  
  112. template <class Type>
  113. class linkedListType
  114. {
  115. public:
  116.     const linkedListType<Type>& operator=
  117.                          (const linkedListType<Type>&);
  118.       //Overload the assignment operator.
  119.  
  120.     void initializeList();
  121.       //Initialize the list to an empty state.
  122.       //Postcondition: first = NULL, last = NULL, count = 0;
  123.  
  124.     bool isEmptyList() const;
  125.       //Function to determine whether the list is empty.
  126.       //Postcondition: Returns true if the list is empty, otherwise
  127.       //    it returns false.
  128.  
  129.     void print() const;
  130.       //Function to output the data contained in each node.
  131.       //Postcondition: none
  132.  
  133.     int length() const;
  134.       //Function to return the number of nodes in the list.
  135.       //Postcondition: The value of count is returned.
  136.  
  137.     void destroyList();
  138.       //Function to delete all the nodes from the list.
  139.       //Postcondition: first = NULL, last = NULL, count = 0;
  140.  
  141.     Type front() const;
  142.       //Function to return the first element of the list.
  143.       //Precondition: The list must exist and must not be empty.
  144.       //Postcondition: If the list is empty, the program terminates;
  145.       //    otherwise, the first element of the list is returned.
  146.  
  147.     Type back() const;
  148.       //Function to return the last element of the list.
  149.       //Precondition: The list must exist and must not be empty.
  150.       //Postcondition: If the list is empty, the program
  151.       //               terminates; otherwise, the last  
  152.       //               element of the list is returned.
  153.  
  154.     virtual bool search(const Type& searchItem) const = 0;
  155.       //Function to determine whether searchItem is in the list.
  156.       //Postcondition: Returns true if searchItem is in the list,
  157.       //    otherwise the value false is returned.
  158.  
  159.     virtual void insertFirst(const Type& newItem) = 0;
  160.       //Function to insert newItem at the beginning of the list.
  161.       //Postcondition: first points to the new list, newItem is
  162.       //    inserted at the beginning of the list, last points to
  163.       //    the last node in the list, and count is incremented by
  164.       //    1.
  165.  
  166.     virtual void insertLast(const Type& newItem) = 0;
  167.       //Function to insert newItem at the end of the list.
  168.       //Postcondition: first points to the new list, newItem is
  169.       //    inserted at the end of the list, last points to the
  170.       //    last node in the list, and count is incremented by 1.
  171.  
  172.     virtual void deleteNode(const Type& deleteItem) = 0;
  173.       //Function to delete deleteItem from the list.
  174.       //Postcondition: If found, the node containing deleteItem is
  175.       //    deleted from the list. first points to the first node,
  176.       //    last points to the last node of the updated list, and
  177.       //    count is decremented by 1.
  178.  
  179.     linkedListIterator<Type> begin();
  180.       //Function to return an iterator at the beginning of the
  181.       //linked list.
  182.       //Postcondition: Returns an iterator such that current is set
  183.       //    to first.
  184.  
  185.     linkedListIterator<Type> end();
  186.       //Function to return an iterator one element past the
  187.       //last element of the linked list.
  188.       //Postcondition: Returns an iterator such that current is set
  189.       //    to NULL.
  190.  
  191.     linkedListType();
  192.       //default constructor
  193.       //Initializes the list to an empty state.
  194.       //Postcondition: first = NULL, last = NULL, count = 0;
  195.  
  196.     linkedListType(const linkedListType<Type>& otherList);
  197.       //copy constructor
  198.  
  199.     ~linkedListType();  
  200.       //destructor
  201.       //Deletes all the nodes from the list.
  202.       //Postcondition: The list object is destroyed.
  203.  
  204. protected:
  205.     int count; //variable to store the number of list elements
  206.                  //
  207.     nodeType<Type> *first; //pointer to the first node of the list
  208.     nodeType<Type> *last;  //pointer to the last node of the list
  209.  
  210. private:
  211.     void copyList(const linkedListType<Type>& otherList);
  212.       //Function to make a copy of otherList.
  213.       //Postcondition: A copy of otherList is created and assigned
  214.       //    to this list.
  215. };
  216.  
  217. template <class Type>
  218. bool linkedListType<Type>::isEmptyList() const
  219. {
  220.     return (first == NULL);
  221. }
  222.  
  223. template <class Type>
  224. linkedListType<Type>::linkedListType() //default constructor
  225. {
  226.     first = NULL;
  227.     last = NULL;
  228.     count = 0;
  229. }
  230.  
  231. template <class Type>
  232. void linkedListType<Type>::destroyList()
  233. {
  234.     nodeType<Type> *temp;   //pointer to deallocate the memory
  235.                             //occupied by the node
  236.     while (first != NULL)   //while there are nodes in the list
  237.     {
  238.         temp = first;        //set temp to the current node
  239.         first = first->link; //advance first to the next node
  240.         delete temp;   //deallocate the memory occupied by temp
  241.     }
  242.  
  243.     last = NULL; //initialize last to NULL; first has already
  244.                  //been set to NULL by the while loop
  245.     count = 0;
  246. }
  247.  
  248. template <class Type>
  249. void linkedListType<Type>::initializeList()
  250. {
  251.     destroyList(); //if the list has any nodes, delete them
  252. }
  253.  
  254. template <class Type>
  255. void linkedListType<Type>::print() const
  256. {
  257.     nodeType<Type> *current; //pointer to traverse the list
  258.  
  259.     current = first;    //set current so that it points to
  260.                         //the first node
  261.     while (current != NULL) //while more data to print
  262.     {
  263.         cout << current->info << " ";
  264.         current = current->link;
  265.     }
  266. }//end print
  267.  
  268. template <class Type>
  269. int linkedListType<Type>::length() const
  270. {
  271.     return count;
  272. }  //end length
  273.  
  274. template <class Type>
  275. Type linkedListType<Type>::front() const
  276. {  
  277.     assert(first != NULL);
  278.  
  279.     return first->info; //return the info of the first node
  280. }//end front
  281.  
  282. template <class Type>
  283. Type linkedListType<Type>::back() const
  284. {  
  285.     assert(last != NULL);
  286.  
  287.     return last->info; //return the info of the last node  
  288. }//end back
  289.  
  290. template <class Type>
  291. linkedListIterator<Type> linkedListType<Type>::begin()
  292. {
  293.     linkedListIterator<Type> temp(first);
  294.  
  295.     return temp;
  296. }
  297.  
  298. template <class Type>
  299. linkedListIterator<Type> linkedListType<Type>::end()
  300. {
  301.     linkedListIterator<Type> temp(NULL);
  302.  
  303.     return temp;
  304. }
  305.  
  306. template <class Type>
  307. void linkedListType<Type>::copyList
  308.                    (const linkedListType<Type>& otherList)
  309. {
  310.     nodeType<Type> *newNode; //pointer to create a node
  311.     nodeType<Type> *current; //pointer to traverse the list
  312.  
  313.     if (first != NULL) //if the list is nonempty, make it empty
  314.        destroyList();
  315.  
  316.     if (otherList.first == NULL) //otherList is empty
  317.     {
  318.         first = NULL;
  319.         last = NULL;
  320.         count = 0;
  321.     }
  322.     else
  323.     {
  324.         current = otherList.first; //current points to the
  325.                                    //list to be copied
  326.         count = otherList.count;
  327.  
  328.             //copy the first node
  329.         first = new nodeType<Type>;  //create the node
  330.  
  331.         first->info = current->info; //copy the info
  332.         first->link = NULL;        //set the link field of
  333.                                    //the node to NULL
  334.         last = first;              //make last point to the
  335.                                    //first node
  336.         current = current->link;     //make current point to
  337.                                      //the next node
  338.  
  339.            //copy the remaining list
  340.         while (current != NULL)
  341.         {
  342.             newNode = new nodeType<Type>;  //create a node
  343.             newNode->info = current->info; //copy the info
  344.             newNode->link = NULL;       //set the link of
  345.                                         //newNode to NULL
  346.             last->link = newNode;  //attach newNode after last
  347.             last = newNode;        //make last point to
  348.                                    //the actual last node
  349.             current = current->link;   //make current point
  350.                                        //to the next node
  351.         }//end while
  352.     }//end else
  353. }//end copyList
  354.  
  355. template <class Type>
  356. linkedListType<Type>::~linkedListType() //destructor
  357. {
  358.    destroyList();
  359. }//end destructor
  360.  
  361. template <class Type>
  362. linkedListType<Type>::linkedListType
  363.                       (const linkedListType<Type>& otherList)
  364. {
  365.     first = NULL;
  366.     copyList(otherList);
  367. }//end copy constructor
  368.  
  369.          //overload the assignment operator
  370. template <class Type>
  371. const linkedListType<Type>& linkedListType<Type>::operator=
  372.                       (const linkedListType<Type>& otherList)
  373. {
  374.     if (this != &otherList) //avoid self-copy
  375.     {
  376.         copyList(otherList);
  377.     }//end else
  378.  
  379.      return *this;
  380. }
  381.  
  382. #endif
Advertisement
Add Comment
Please, Sign In to add comment