Return to Data Structures homepage
Return to ACC Homepage COSC 2415 - Data Structures and
ITSE 2445 Data Structures
Bob Comer, Professor of Computer Studies
Program 4 - Linked-list Processing
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). Your assignment is to 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 items in this List have been output to out // on a single line with spaces between them int find( ElementType value); // // Find the first occurrence of a value in this List // Preconditions: None // Postconditions: The return value is the index of the first List item // that matches value. The first list item has index 0, // the second has index 2, etc. void reverse( ); // // Reverse the order of the elements in this List // Preconditions: None // Postconditions: The order of the elements in this List is 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 can use the driver program from Program 2 as a starting point. In the header file, You will need to change the typedef statement for ElementType to string.
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>
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( );
/* Construct a List object
Precondition: none.
Postcondition: An empty List object has been constructed.
*/
List( const List &source );
/* Construct a copy of a List object.
Precondition: None.
Postcondition: A copy of origList has been constructed.
*/
~List( );
/* Destroys a List object.
Precondition: None.
Postcondition: Any memory allocated to the List object has been freed.
*/
const List & operator=( const List &rightSide );
/* Assign a copy of a List object to the current object.
Precondition: none
Postcondition: A copy of rightside has been assigned to this
object. A constant reference to this list is returned.
bool List::empty( );
/* Check if this List is empty
Precondition: none
Postcondition: The return value is true if this List object is empty;
otherwise the return value is false.
void insert( ElementType dataVal, int index );
/* Insert a value into this List at a given index
Precondition: there is room in the array (the current size is less than
the capacity); and the index is valid (the first position is index 0,
the second position is index 1, etc.
Postcondition: dataval has been inserted into the list at the position
determined by index (provided there is room and index is a legal
position).
*/
void erase( int index );
/* Remove the value from this List at a given index.
Precondition: The list is not empty and index is valid
(index greater than or equal to 0 and less than the size.
Postcondition: the element at position index has been
removed (provided index is a legal position).
*/
void display( ostream &out );
// student writes this function
int find( ElementType value);
// student writes this function
void reverse( );
// student writes this function
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 )
{ }
// Copy constructor
List::List( const List &source )
{
length = source.length;
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 )
{
// check for self-assignment
if ( this == &rightSide )
return *this;
// free all nodes in the list on left-hand side
this->~List( );
// now copy nodes from list on right-hand side
// into list on left-hand side
NodePointer rightPtr, lastPtr;
length = rightSide.length;
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 ) { }
// students write this as a member function
// void List::reverse( ) { }
// reverses this List - student writes this function
Return to Data Structures homepage
Return to ACC Homepage