Collections

Dynamic Data structures are those which can shrink and grow to fit changing requirements. A container is a dynamic data structure. Dynamic variables can be allocated (created) and de-allocated (destroyed) when needed. Dynamic data structures are advantageous in that the number of variables needed is always exact – no more, no less. There are three types of collections; linked lists, stacks/queues, and trees.

Linked Lists

A linked list is a chain of data structures linked together by pointers. The heap is memory not used by the stack. Static variables reside in the stack, while dynamic variables reside in the heap. As the stack grows, the heap shrinks. Pointers are used to access the variables in the heap.

 

Creating:  

Create a pointer to the heap:

Node* list_head;

Notice that list_head points to “garbage” right now.

Create a new node in the list:

list_head = new Node;

Now the pointer is pointing to a new node.

Fill in the new nodes data:

list_head->data =42;

The -> follows the pointer into the heap and changes data’s value for the node that list_head points to.

Create a second node:

list_head->next = new Node;

This adds a new node to the end of the list by changing were the first node points to.

Fill in the new nodes data and cleanly terminate the list:

list_head->next->data = 91; list_head->next->next = NULL;

Adds the value 91 to the new nodes data and then tells the new node’s pointer to point to NULL.

Deleting by moving the pointer:

Node* temp;  
temp = list_head;  
list_head = list_head->next;  
delete temp;

Creates a temporary pointer that points to the location list_head points to, then changes list_head so as it points to the node in the list.  Then deletes the first node of the list.

Inserting:

Adding a node to a linked list involves finding the correct location, and doing the work to add the node.  There are three possible positions in which to add nodes at the front, back, or some were in the middle.

          To the front:  
                    There is no work to be done as the list_head always points to the correct location empty or not.  You will need a by-reference pointer parameter.  Create a new node and fill in its data.                      Set its pointer so as it points to were list_head points too.  Update list_head so as it points to the new start of the list.  

void List::insertAtFront(const int &value)
{
       ListNode * newPtr = getNewNode (value);

       if (isEmpty())
       {
              List::listFront = List::listEnd = newPtr;
       }
       else
       {
              newPtr->nextPtr=List::listFront;
              List::listFront = newPtr;
       }
}

          To the end of the list:
                     Need to find the end of the list (NULL).  Recursion or iteration can be used to traverse to the end of the list, or you can set up a pointer at creation that always points to the end of the                     list.  Once you reach the end of the list create the new node there and fill in its data.  Terminate the new nodes next pointer to NULL.  

void List::insertAtBack (const int &value)  
{
      ListNode *newPtr = getNewNode (value);
      if ( isEmpty ()) 
     { 
          List::listFront = List::listEnd = newPtr; 
     } 
     else 
     { 
          List::listEnd->nextPtr = newPtr; 
          List::listEnd = newPtr; 
     }  
}

          To the middle:  
                 Used when order is important.  Need to go to the node that should follow the one to add.  Recursion or iteration must be used to transverse the list till the correct point in the list is                     reached.  Each time you loop compare to see if you need to add the new node before the current node.  If value is the largest then you need to add the node to the end.  To perform the                     insertion you will need to create the new node, insert the nodes data, update the next pointer to the new node, update the current pointer to the new node.

Now that you know what a linked list is lets code one up.  
List Node:

#ifndef LISTNODE_H  
#define LISTNODE_H  
class ListNode  
{ 
     friend class List;  
public: 
     ListNode(const int); 
     int getData();  
private: 
     int data; 
     ListNode *nextPtr;  
protected:  
};
#endif  

#include "ListNode.h"  
#include <iostream>  

ListNode::ListNode (const int info)  
{
     ListNode::data = info; 
     ListNode::nextPtr = NULL;  
}  
int ListNode::getData ()  
{ 
     return ListNode::data;  
}

As you can see a list node class is created purely to hold the value needed to be stored, and to point to the next node in the list.

#ifndef LIST_h  
#define LIST_h  

#include "ListNode.h"

class List  
{
public: 
     List(); 
     ~List (); 
     void insertAtFront (const int &); 
     void insertAtBack (const int &); 
     bool removeFromFront (int &); 
     bool removeFromBack (int &); 
     bool isEmpty () const; 
     void print() const;  
protected:  
private: 
     ListNode * listFront; 
     ListNode * listEnd; 
     ListNode* getNewNode (int);  
};  
#endif  

#include "List.h"  
#include <iostream>

using namespace std;

List::List ()  
{ 
     List::listFront = NULL; 
     List::listEnd = NULL;  
}

List::~List()  
{ 
     if (!isEmpty()) 
     { 
          cout<<"Destroying Nodes ...\n"; 
     } 
     ListNode * currentPtr = List::listFront, * tempPtr; 

     while (currentPtr != NULL) 
     {
          tempPtr = currentPtr; 
          cout<< tempPtr->data <<'\n'; 
          currentPtr = currentPtr->nextPtr; 
          delete tempPtr; 
     } 
     cout<<"All nodes destroyed\n\n";  
}  

void List::insertAtFront(const int &value)  
{ 
     ListNode * newPtr = getNewNode (value);  

     if (isEmpty()) 
     { 
          List::listFront = List::listEnd = newPtr; 
     } 
     else 
     { 
          newPtr->nextPtr=List::listFront; 
          List::listFront = newPtr; 
     }  
} 

void List::insertAtBack (const int &value)  
{ 
     ListNode *newPtr = getNewNode (value); 
     if ( isEmpty ()) 
     { 
          List::listFront = List::listEnd = newPtr; 
     } 
     else 
     { 
          List::listEnd->nextPtr = newPtr; 
          List::listEnd = newPtr; 
     }  
}  

bool List::removeFromFront (int &value)  
{ 
     if (isEmpty()) 
     { 
          return false; 
     } 
     else 
     { 
          ListNode * tempPtr = List::listFront; 
          if (List::listFront == List::listEnd) 
          { 
              List::listFront = List::listEnd = NULL; 
          } 
          else 
          { 
              List::listFront = List::listFront->nextPtr;           } 
          value = tempPtr->data; 
          return true; 
     }  
}  

bool List::removeFromBack (int &value)  
{ 
     if (isEmpty()) 
     { 
          return false; 
     } 
     else 
     { 
          ListNode * tempPtr = List::listEnd; 
          if ( List::listFront == List::listEnd) 
          { 
              List::listFront = List::listEnd = NULL; 
          } 
          else 
          { 
              ListNode * currentPtr = List::listFront;               while (currentPtr->nextPtr != List::listEnd )               { 
                   currentPtr = currentPtr->nextPtr; 
              } 
              List::listEnd = currentPtr; 
              currentPtr->nextPtr = NULL; 
          }     
          value = tempPtr->data; 
          delete tempPtr; 
          return true; 
     }  
} 

bool List::isEmpty() const  
{ 
     return List::listFront==NULL;  
}  

ListNode* List::getNewNode (int value)  
{ 
     ListNode * ptr = new ListNode (value); 
     return ptr;  
}  

void List::print () const  
{ 
     if (isEmpty()) 
     { 
          cout<<"The list is Empty\n\n"; 
          return; 
     } 
     ListNode * currentPtr = listFront; 
     cout<<"The list is: "; 
     while (currentPtr != NULL) 
     { 
          cout<<currentPtr->data<< ' '; 
          currentPtr = currentPtr->nextPtr; 
     }
      cout<< "\n\n";  
}

As you can see it is the List class its self that does all of the work for the list.  The only method present in the List class that has not been as of yet mentioned is the Print method, which handles printing out the value stored in the nodes of the list.  Now that you know how you would go about coding a list node and a list we can move onto Stacks and Queues.

Stacks/Queues

Stacks and queues are ideas that imply a logical set of behaviors.  They can be implemented in three ways, via a linked list, a tree, or an array.  This lab will not cover trees, and thus the Stacks and Queues will be implemented using Linked lists.

Stacks:

Stacks are dynamic collections that operate on a last in first out data structure

Behaviors:

When you use a linked list to set up a stack, the linked list will have a limited set of operations that change its state (only modified from the last node in the list).  Further more you will need to create a node class, a linked list class, and a stack class.  The Stack class you create must contain all of the necessary above behaviors.  As you might of guessed we will be using the above Node and the List classes in order to create our Stack class.

Stacks Dynamic Implementation:

Push Steps

Step 1. Within the Push method create a new node.  

Step 2. Add the new node to the front of the list.

Pop Steps

Step 1. Within the Pop method capture the value of the top node.  

Step 2. Within the Pop method change top so as it points to the next node on the Stack and then delete the top node.  

Step 3. Return the value you captured in step 1.  

For the Is_Full method you would simply return a Boolean stating if the max size for the Stack has been reached (true if it has, false if it has not) (again this is only used if you set up a max size for the stack).  For the Is_Empty method again you also return a Boolean if the Stack is empty (true if it is, false if it is not).  Every time you initialize a stack it must be initialized so as list_head points to NULL.  Now that you know how the Stack should behave lets look at an example of a Stack class.

#ifndef STACK_H  
#define STACK_H  

#include "List.h"  
#include <iostream>  

using namespace std; 

class Stack  
{  
public: 
     void push (const int &); 
     bool pop (int &); 
     bool isStackEmpty() const; 
     void printStack() const;  
private: 
     List s;  
protected:  
};  
#endif

#include "Stack.h"  

void Stack::push (const int &d)  
{ 
     s.insertAtFront(d);  
}  

bool Stack::pop (int &d)  
{ 
     return s.removeFromFront(d);  
}

bool Stack::isStackEmpty() const  
{
      return s.isEmpty();  
}

void Stack::printStack() const  
{ 
     s.print();  
}

 

As you can see in order to set up a stack you will need to #include List.h in the Stack class.  By doing so you can use the List class as the framework for your stack.  As you can see in order to turn a list into a stack you need to restrict the allowed modifications capable of being performed on the list.  This means that the application should only be allowed to add and remove nodes from either the front or the end of the list (If you inserted the nodes at the front of the list remove them their also.  The same goes for the end of the list).  As you can see the print method in the List class still handles all of the printing for the list/stack.

 

Queues:

Queues are dynamic collections that operate on a first in first out data structure.

 

Behaviors:  

Queue Dynamic Implementation

Queue as a linked list:  

Engueue:

Step 1. Create a new node with data

Step 2. Add the new node to the end.

Step 3. Update pointers as needed

Dequeue:

Step 1. Capture the first value (to return)

Step 2. Remove first node move head to next.

Step 3. Return value capture in step 1.

For the Is_Full method you would simply return a Boolean stating if the max size for the Queue has been reached (true if it has, false if it has not) (again this is only for if you set up a max size for the queue).  For the Is_Empty method simply return a Boolean if the Queue is empty (true if it is, false if it is not).  Every time you initialize a queue it must be initialized so as head and tail point to NULL.  Now that you know how a Queue should behave lets look at an example Queue class.

#ifndef QUEUE_H  
#define QUEUE_H  

#include "List.h"  

class Queue  
{  
public: 
     void enqueue (const int &); 
     bool dequeue (int &); 
     bool isQueueEmpty () const; 
     void printQueue() const;  
private: 
     List s;  
protected:  
};  
#endif

#include "Queue.h"  

void Queue::enqueue (const int &d)  
{ 
     s.insertAtBack(d);  
}  

bool Queue::dequeue (int &d)  
{ 
     return s.removeFromFront(d);  
}  

bool Queue::isQueueEmpty () const  
{ 
     return s.isEmpty();  
}

void Queue::printQueue () const  
{ 
     s.print();  
}

As you can see in order to set up a queue you will need to #include the List class in the Queue class.  By doing so you can use the List class as the framework for your queue.  As you can see in order to turn a list into a queue you need to restrict the allowed modifications capable of being performed on the list.  This means that the application should only be allowed to add nodes to one end and remove them from the other end (For example if you added nodes to the front you would remove them from the rear).  As you can see the print method in the List class still handles all of the printing for the list/queue.

Templates

Now that you know what the code for the linked lists, Stacks, and Queues should look like it is time to move on to templates.  As you may have noticed above, all of the above procedures for the Dynamic Data Types take in only integers.  However what would you do if you wanted to work with floats, doubles, or longs?  The answer is that as the code stands now you would have to change every instance of int to the data type you want the Dynamic Data Types to work with.  The problem with this is that it is not only time consuming but it is also error prone.  How ever there is a way to change the code so as we can pass in what ever variable type we wish and still have the application perform properly, which is know as making a template.  To templatize the application you would the majority of instances were you keyed in the key word int you would simply need to change it to the key word you choose to use when setting up the template. 

template <class d>

For example if you set up the template like the above example you would replace all instances of int were you took the integer in as an argument with d.  For example with the list node class when you templatize (make it a template) the header file it will look like the bellow code.  As you can see below it proved necessary to take the code from the CPP files and place it in the Header files.  This is because if you do not do so you will get the link error link2001 when you build the application.  Also as you will notice between the non-templatized and the templatized version very little changed.  As you can see the key word int changed to the key word you choose when setting up the template.  Also every were you created an instance of the classes in the header files you needed to type in <Keyword> beside the data type (for ex: ListNode<NODETYPE>).  Lastly when you expanded upon a class procedure you needed to type in ClassName<Keyword>::Procedurename ()

 

#ifndef LISTNODE_H  
#define LISTNODE_H  
template < class NODETYPE > class List;  
template <class NODETYPE>  
class ListNode  
{ 
     friend class List<NODETYPE>;  
public: 
     ListNode( const NODETYPE & ); 
     NODETYPE getData() const;  
private: 
     NODETYPE data; 
     ListNode<NODETYPE> *nextPtr;  
};  

template<class NODETYPE>  
ListNode< NODETYPE >::ListNode (const NODETYPE &info)  
{ 
     data = info; 
     nextPtr = NULL;  
}

template <class NODETYPE>  
NODETYPE ListNode<NODETYPE>::getData () const  
{ 
     return data;  
}  
#endif

 

#ifndef LIST_H
#define LIST_H

#include "ListNode.h"

template <class NODETYPE>  
class List  
{  
public: 
     List (); |
     ~List (); 
     void insertAtFront (const NODETYPE &); 
     void insertAtBack (const NODETYPE &); 
     bool removeFromFront (NODETYPE &); 
     bool removeFromBack (NODETYPE &); 
     bool isEmpty () const; 
     void print() const;  
private: 
     ListNode< NODETYPE > *listFront; 
     ListNode< NODETYPE > *listEnd;  

     ListNode< NODETYPE > *getNewNode (const NODETYPE &);  
};  

template <class NODETYPE>  
List< NODETYPE >::List ()  
{ 
     listFront = NULL; 
     listEnd = NULL;  
}  

template <class NODETYPE>  
List< NODETYPE >::~List()  
{ 
     if (!isEmpty()) 
     { 
          cout<<"Destroying Nodes ...\n"; 
     } 
     ListNode< NODETYPE > *currentPtr = listFront, *tempPtr;  

     while ( currentPtr != NULL ) 
     { 
          tempPtr = currentPtr; 
          cout<< tempPtr->data <<'\n'; 
          currentPtr = currentPtr->nextPtr; 
          delete tempPtr; 
     }  

     cout<<"All nodes destroyed\n\n";  
}  

template <class NODETYPE>  
void List< NODETYPE >::insertAtFront(const NODETYPE &value)  
{ 
     ListNode< NODETYPE > *newPtr = getNewNode (value); 
     if (isEmpty()) 
     { 
          listFront = listEnd = newPtr; 
     } 
     else 
     { 
          newPtr->nextPtr = listFront; 
          listFront = newPtr; 
     }  
}  

template <class NODETYPE>  
void List<NODETYPE>::insertAtBack (const NODETYPE &value)  
{ 
     ListNode<NODETYPE> *newPtr = getNewNode (value); 
     if ( isEmpty ()) 
     { 
          listFront = listEnd = newPtr; 
     } 
     else 
     { 
          listEnd->nextPtr = newPtr; 
          listEnd = newPtr; 
     }  
}  

template <class NODETYPE>  
bool List<NODETYPE>::removeFromFront (NODETYPE &value)  
{ 
     if (isEmpty()) 
     { 
          return false; 
     } 
     else 
     { 
          ListNode<NODETYPE> *tempPtr = List<NODETYPE>::listFront; 
          if (listFront == listEnd) 
          { 
              listFront = listEnd = NULL; 
          } 
          else 
          { 
              listFront = listFront->nextPtr; 
          } 
          value = tempPtr->data; 
          delete tempPtr; 
          return true; 
     }  
}  

template <class NODETYPE>  
bool List<NODETYPE>::removeFromBack (NODETYPE &value)  
{ 
     if (isEmpty()) 
     { 
          return false; 
     } 
     else 
     { 
          ListNode<NODETYPE> *tempPtr = listEnd; 
          if ( listFront == listEnd)
                       { 
              List<NODETYPE>::listFront = List<NODETYPE>::listEnd = NULL; 
          } 
          else 
          { 
              ListNode<NODETYPE> *currentPtr = listFront;  

              while (currentPtr->nextPtr != listEnd ) 
              { 
                   currentPtr = currentPtr->nextPtr;
              } 
              listEnd = currentPtr; 
              currentPtr->nextPtr = NULL; 
          }     
          value = tempPtr->data; 
          delete tempPtr; 
          return true; 
     }  
}  

template <class NODETYPE>  
bool List<NODETYPE>::isEmpty() const  
{ 
     return listFront==NULL;  
}  

template <class NODETYPE>  
ListNode<NODETYPE>* List<NODETYPE>::getNewNode (const NODETYPE &value)  
{ 
     ListNode<NODETYPE> *ptr = new ListNode<NODETYPE>(value); 
     return ptr;  
}  

template <class NODETYPE>  
void List<NODETYPE>::print () const  
{ 
     if (isEmpty()) 
     { 
          cout<<"The list is Empty\n\n"; 
          return; 
     } 
     ListNode<NODETYPE> *currentPtr = listFront; 
     cout<<"The list is: "; 
     while (currentPtr != NULL) 
     { 
          cout<<currentPtr->data<< ' '; 
          currentPtr = currentPtr->nextPtr; 
     } 
     cout<< "\n\n";  
}  
#endif

 

#ifndef STACK_H  
#define STACK_H  

#include "List.h"
#include <iostream>  

using namespace std;
template<class STACKTYPE>  
class Stack  
{  
public: 
     void push (const STACKTYPE &); 
     bool pop (STACKTYPE &); 
     bool isStackEmpty() const; 
     void printStack() const;  
private: 
     List<STACKTYPE> s;  
protected:  
};

template<class STACKTYPE>  
void Stack<STACKTYPE>::push (const STACKTYPE &d)  
{ 
     s.insertAtFront(d);  
}

template<class STACKTYPE>  
bool Stack<STACKTYPE>::pop (STACKTYPE &d)  
{ 
     return s.removeFromFront(d);  
}  

template<class STACKTYPE>  
bool Stack<STACKTYPE>::isStackEmpty() const  
{ 
     return s.isEmpty();  
}  

template<class STACKTYPE>  
void Stack<STACKTYPE>::printStack() const  
{ 
     s.print();  
}  
#endif

 

#ifndef QUEUE_H  
#define QUEUE_H  

#include "List.h"  
template <class QUEUETYPE>  
class Queue  
{  
public: 
     void enqueue (const QUEUETYPE &); 
     bool dequeue (QUEUETYPE &); 
     bool isQueueEmpty () const; 
     void printQueue() const;  
private: 
     List<QUEUETYPE> s;  
protected:  
};  

template <class QUEUETYPE>  
void Queue<QUEUETYPE>::enqueue (const QUEUETYPE &d)  
{ 
     s.insertAtBack(d);  
}

template <class QUEUETYPE>  
bool Queue<QUEUETYPE>::dequeue (QUEUETYPE &d)  
{ 
     return s.removeFromFront(d);  
}

template <class QUEUETYPE>  
bool Queue<QUEUETYPE>::isQueueEmpty () const  
{ 
     return s.isEmpty();  
}

template <class QUEUETYPE>  
void Queue<QUEUETYPE>::printQueue () const  
{ 
     s.print();  
}  
#endif

 

Now that you know how the code for the classes should look (templatized/non-templatized) the bellow example shows how the templatized version of Main.cpp should look. 

 

#include <iostream>  
#include "List.h"  
#include "Stack.h"  
#include "Queue.h"  

using namespace std;  
template <class T>  
void testList (List<T> &listObject, const char *type)  
{ 
     cout<<"Testing a list of "<<type<< " values\n"; 

     int choice;

     T value;

     do 
     { 
          instructions (); 
          cout<<"? "; 
          cin>>choice; 
          switch (choice) 
          { 
          case 1: 
              cout<<"Enter an integer: "; 
              cin>>value; 
              listObject.insertAtFront(value); 
              listObject.print(); 
              break; 
          case 2: 
              cout<<"Enter an integer: "; 
              cin>>value; 
              listObject.insertAtBack(value); 
              listObject.print(); 
              break; 
          case 3: 
              if (listObject.removeFromFront (value)) 
              { 
                   cout<<value<<" remove from list\n"; 
              } 
              listObject.print(); 
              break; 
          case 4: 
              if (listObject.removeFromBack (value))               { 
                   cout<<value<<" removd from list\n";               } 
              listObject.print(); 
              break;
          } 
     }while (choice != 5); 
     cout<<"End list test\n\n";  
}  
void instructions ()  
{ 
     cout<<"Enter one of the following:\n" 
          <<"  1 to insert at the beginning of list:\n" 
          <<"  2 to insert at the end of list\n" 
          <<"  3 to delete from beginning of list\n" 
          <<"  4 to delete form end of list\n" 
          <<"  5 to end list processing\n";  
}  

void main ()  
{ 
     List<int> integerList; 
     testList(integerList, "integer");   

     List<double> doubleList; 
     testList(doubleList, "double");  

     Stack<int> intStack; 
     int popInterger, i; 
     cout<<"processing an integer Stack"<<endl; 
     for (i = 0; i < 4; i++) 
     { 
          intStack.push(i); 
          intStack.printStack(); 
     } 
     while( !intStack.isStackEmpty()) 
     { 
          intStack.pop(popInterger); 
          cout<< popInterger<<" poped from stack"<<endl; 
          intStack.printStack(); 
     }  

     Stack<double> doubleStack; 
     double popDouble, val = 1.1; 
     cout<<"processing an double Stack"<<endl; 
     for (i = 0; i < 4; i++) 
     { 
          doubleStack.push(val); 
          doubleStack.printStack(); 
          val++; 
     } 
     while( !intStack.isStackEmpty()) 
     { 
          doubleStack.pop(popDouble); 
          cout<< popInterger<<" poped from stack"<<endl; 
          intStack.printStack(); 
     }  

     Queue <int> intQueue; 
     int dequeueInteger; 
     cout<<"processing an integer Queue"<<endl; 
     for (i = 0; i < 4; i++) 
     { 
          intQueue.enqueue(i); 
          intQueue.printQueue(); 
     } 
     while (!intQueue.isQueueEmpty()) 
     { 
          intQueue.dequeue(dequeueInteger); 
          cout<<dequeueInteger<<" dequeued"<<endl; 
          intQueue.printQueue(); 
     }  

     Queue <double> doubleQueue; 
     val = 1.1; 
     double dequeueDouble; 
     cout<<"processing a double Queue"<<endl; 
     for(i = 0; i <4; i++) 
     { 
          doubleQueue.enqueue(val); 
          doubleQueue.printQueue(); 
          val++; 
     } 
     while (!doubleQueue.isQueueEmpty()) 
     { 
          doubleQueue.dequeue(dequeueDouble); 
          cout<<dequeueDouble<<" dequed"<<endl; 
     }  
}  

 

As you can see above we created two procedures along with the Main section of the application.  The testList procedure is used to handle all the List class calls and to hand the user input when responding to the menu.  The instructions procedure is used to handle printing out the applications menu.  Also as you notice in the above code example when ever you create an instance of one of the classes that you coded you need to type in DataType <int> VarName so as when you create an instance of the class it will know the data type that it will be dealing with.  In order to convert the above Main section to non-templatized you simply remove all of the <datatype> from when you created an instance of the classes.  Lastly you will also need to remove template <class T> from over the testList procedure and the <T> from the argument list.