COSC 2415 - Data Structures and
ITSE 2445 Data Structures
Bob Comer, Professor of Computer Studies

Be sure to read through Chapter 6 of the textbook before starting this assignment.

Below I am providing a portion of the pointer-based linked list class described in Section 6.5 of your textbook (beginning on page 295). Add the following member functions to your class:

void display( ostream & out ) const;
// Display the contents of this List
// Precondition:  ostream out is open
// Postcondition: the elements of this List have been output to out
//                on a single line with spaces between them

void reverse( );
//
// Reverse the order of the elements in this List
// Preconditions:  None
// Postconditions: The elements in this list have been reversed

Hint: You may want to use a temporary linked list in your reverse function. Be sure to free any unused nodes.

Write a driver program to test your function for a linked list of strings. You will need to change the typedef statement for ElementType to string in the header file.

Your project should be divided into separate files - a class definition file, a class implementation file, and the client (driver) program.

 
// List.h

#ifndef LINKEDLIST
#define LINKEDLIST

#include <iostream>
#include <cstdlib>
using namespace std;

typedef int ElementType;

class List
{
private:
   class Node
   {
   public:
      ElementType data;
      Node * next;
      
      Node( )
      : data( ElementType( ) ), next( NULL )
      { }
              
      Node( ElementType initData )
      : data( initData ), next( NULL )
      { }
   }; // end of Node class
           
   typedef Node * NodePointer;
           
public:
   List( );
   // Default constructor
              
   List( const List &source );
   // Copy constructor
              
   ~List( );
   // Destructor
              
   const List & operator=( const List &rightSide );
   // Overloaded assignment operator
              
   bool List::empty( );
   // Check if this List is empty
              
   void insert( ElementType dataVal, int index );
   // Insert a value into this List at a given index
              
   void erase( int index );
   // Remoev a value from this List at a given index.
              
   void display( ostream &out );
   // have them write this as a non-member function

   void reverse( );
   // reverses this List - students write this
              
   private:
   NodePointer first;
   int length;
}; // end of List class
           
#endif

// List.cpp

#include <iostream>
#include <cstdlib>
#include <cassert>
using namespace std;
#include "List.h"
           
// Default constructor
List::List( )
: first( NULL ), length( 0 ) 
{ }           // better: init to ElementType( )
           
// Copy constructor
List::List( const List &source )
{
   first = NULL;
   if ( source.length == 0 )
      return;
   
   List::NodePointer srcPtr, lastPtr;
   
   // copy first node
   first = new Node( source.first->data );
   lastPtr = first;
   
   // copy rest of nodes
   srcPtr = source.first->next;
   while ( srcPtr != 0 )
   {
      lastPtr->next = new Node( srcPtr->data );
      srcPtr = srcPtr->next;
      lastPtr = lastPtr->next;
   }
}
         
// Destructor
inline List::~List( )
{
   List::NodePointer prev=first,
                     ptr;
                     
   while ( prev != NULL )
   {
      ptr = prev->next;
      delete prev;
      prev = ptr;
   }  
}
              
// Overloaded assignment operator
const List & List::operator=( const List &rightSide )
{
   length = rightSide.length;
   first = NULL;
   if ( length == 0 )
      return *this;
      
      if ( this != &rightSide )
      {
         this->~List( );
         List::NodePointer rightPtr, lastPtr;
         first = new Node( rightSide.first->data ); 
         lastPtr = first;
         rightPtr = rightSide.first->next;
         while ( rightPtr != NULL )
         {
            lastPtr->next = new Node( rightPtr->data );
            rightPtr = rightPtr->next;
            lastPtr = lastPtr->next;
         }
      }
      return *this;
}
              
// Check if this List is empty
bool List::empty( )
{
   return length == 0;
}
              
// Insert a value into this List at a given index
void List::insert( ElementType dataVal, int index )
{
   assert( index >= 0 && index <= length );
   
   length++;
   List::NodePointer newPtr = new Node( dataVal ),
                     predPtr = first;
   if ( index == 0 )
   {
      newPtr->next = first;
      first = newPtr;
   }
   else
   {
      for ( int i = 1; i < index; i++ )
         predPtr = predPtr->next;
      newPtr->next = predPtr->next;
      predPtr->next = newPtr;
   }
}
              
// Remove a value from this List at a given index.
void List::erase( int index )
{
   assert( index >= 0 && index < length );
   
   length--;
   List::NodePointer ptr,
                     predPtr = first;
   if ( index == 0 )
   {
      ptr = first;
      first = ptr->next;
      delete ptr;
   }
   else
   {
      for ( int i = 1; i < index; i++ )
         predPtr = predPtr->next;
      ptr = predPtr->next;
      predPtr->next = ptr->next;
      delete ptr;
   }
}

void List::display( ostream &out );
// have them write this as a member function

            
// void List::reverse( );
// reverses this List - students write this
          

Return to Data Structures homepage 

Return to ACC Homepage

URL: http://www.austincc.edu/comer/dsf06/
Copyright: 2007 by the Austin Community College
Department of Computer Studies. All rights reserved.
Comments to: Bob Comer
Last updated: October 27, 2007

Austin Community College is an equal opportunity educator and employer.