Without using a ListIterator, define and implement a new operation called insert
ID: 3530688 • Letter: W
Question
Without using a ListIterator, define and implement a new operation called insert_back which takes a single template Object and inserts the Object at the end of the list. A brute force version of this method would walk down the list to find the end, and therefore would run in linear time, O(n), for a list with n elements. Think carefully about the running time of this operation, T(n). Without changing the meaning of this operation or any other, modify the representation of a List and alter whatever methods are necessary to make insert_back run in constant time: O(1). HINT: Your List class will need to continually maintain a pointer to the last (tail) ListNode on the List, and all of List's methods will have to ensure that this member stays current even as the list changes. This new operation should have the signature: void List::insert_back( const Object& data ); TESTING HINT: Run the methods: insert( 3 ); insert( 2 ); insert( 1 ); Print the list. What should it look like? Run the methods: insert_back( 5 ); Print the list. What should it look like? Run the methods: remove( 5 ); Print the list. What should it look like? Run the methods: insert_back( 7 ); insert( 8 ); Print the list. What should it look like? Run the methods: remove( 3 ); remove( 2 ); remove( 1 ); Run the methods: remove( 7 ); remove( 8 ); Print the list. What should it look like? Run the methods: insert_back( 5 ); Print the list. What should it look like?Explanation / Answer
LIST.H
#ifndef LIST_H
#define LIST_H
#include <iostream>
#include "ListNode.h"
#include "ListIterator.h"
namespace cs20
{
template <class Object>
class List
{
public:
List();
List( const List& righths );
~List();
bool LisEmpty() const;
bool LisIncreasing() const;
void LmakeEmpty();
ListIterator<Object> Lzeroth() const;
ListIterator<Object> Lfirst() const;
void Listinsert( const Object& data, const ListIterator<Object> &iter );
void Listinsert( const Object& data );
void Listinsert_back( const Object& data );
ListIterator<Object> ListfindPrevious( const Object& data ) const;
void Listremove( const Object& data );
const List& operator =( const List& righths );
const List& operator <<( const List& righths );
private:
ListNode<Object> * Nhead;
ListNode<Object> * Ntail;
};
}
#endif
LIST.CPP
#ifndef LIST_CPP
#define LIST_CPP
#include "List.h"
namespace cs20
{
template <class Object> List<Object>::List()
{
Nhead = new ListNode<Object>;
Ntail->nextIsNull();
}
template <class Object>
List<Object>::List( const List<Object>& righths )
{
Nhead = new ListNode<Object>;
Ntail->nextIsNull();
*this = righths;
}
template <class Object> List<Object>::~List()
{
LmakeEmpty();
delete Nhead;
}
template <class Object> bool List<Object>::LisEmpty() const
{
return( Nhead->nextIsNull() );
}
template <class Object> void List<Object>::LmakeEmpty()
{
while (!LisEmpty())
{
Listremove( Lfirst().retrieve() );
}
Ntail = NULL;
}
template <class Object> ListIterator<Object>
List<Object>::Lzeroth() const
{
return( ListIterator<Object>( Nhead ) );
}
template <class Object> ListIterator<Object>
List<Object>::Lfirst() const
{
return( ListIterator<Object>( Nhead->getNext() ) );
}
template <class Object> void List<Object>::Listinsert(
const Object& data, const ListIterator<Object> &iter )
{
if (iter.isValid()) {
ListNode<Object>* newnode = new ListNode<Object>(
data, iter.current->getNext() );
iter.current->setNext( newnode );
}
}
template <class Object> void List<Object>::Listinsert(
const Object& data )
{
ListNode<Object>* newnode = new ListNode<Object>(
data, Nhead->getNext() );
Nhead->setNext( newnode );
}
template <class Object> void List<Object>::Listinsert_back(
const Object& data )
{
ListNode<Object>* lastNode = Nhead;
while (lastNode->getNext())
lastNode = lastNode->getNext();
lastNode->setNext( newnode );
}
template <class Object> ListIterator<Object> List<Object> ::ListfindPrevious( const Object& data ) const
{
ListNode<Object>* node = Nhead;
while( node->getNext() != NULL && node->getNext()->
getElement() != data )
{
node = node->getNext();
}
if (node->getNext() == NULL)
{
node = NULL;
}
return ListIterator<Object>( node );
}
template <class Object> bool List<Object>::LisIncreasing()
const
{
ListNode<Object>* node= Nhead;
while (node->getNext() != NULL)
{
if (node->getNext()->getElement() <= node->
getElement())
return false;
node = node->getNext();
}
return true;
}
template <class Object> void List<Object>::Listremove( const Object& data )
{
ListIterator<Object> iter = ListfindPrevious( data );
if (iter.isValid())
{
ListNode<Object>* node = ListfindPrevious( data ).current;
if (node->getNext() != NULL) {
ListNode<Object> *oldNode = node->getNext();
node->setNext( node->getNext()->getNext() ); delete oldNode;
}
}
}
template <class Object> const List<Object>& List<Object> ::operator =( const List<Object>& righths )
{
if (this != &righths)
{
LmakeEmpty();
ListIterator<Object> rightiter = righths.Lfirst( );
ListIterator<Object> myiterator = Lzeroth();
while( rightiter.isValid() )
{
Listinsert( rightiter.retrieve(), myiterator );
rightiter.advance();
myiterator.advance();
}
}
return( *this );
}
}
#endif
Menu.cpp
#include <iostream>
#include "List.h"
#include "ListNode.h"
#include "ListIterator.h"
#include "List.cpp"
#include "ListNode.cpp"
#include "ListIterator.cpp"
using namespace std;
using namespace cs20;
enum OPTION {MAKEEMPTY, REMOVE, ISEMPTY, FINDPREVIOUS, INSERT, QUIT, PRINT };
OPTION menu();
void printList( const List<int>& l );
int main(int argc, char* argv[])
{
int value;
List<int> listobj;
ListIterator<int> iter;
OPTION choice;
do {
choice = menu();
switch( choice )
{
case MAKEEMPTY:
listobj.LmakeEmpty();
break;
case ISEMPTY:
if (listobj.LisEmpty()) {
cout << "list is empty" << endl;
}
else {
cout << "list is not empty" << endl;
}
break;
case REMOVE:
cout << "Please provide int to remove: ";
cin >> value;
listobj.Listremove( value );
break;
case INSERT:
cout << "Please provide int to insert: ";
cin >> value;
listobj.Listinsert( value );
break;
case FINDPREVIOUS:
cout << "Please provide int to find: ";
cin >> value;
iter = listobj.ListfindPrevious(
value );
if (iter.isValid()) {
cout << "previous element = "
<< iter.retrieve() << endl;
}
else {
cout << "data element was not
found!" << endl;
}
break;
case PRINT:
printList( listobj );
break;
case QUIT:
break;
}
} while (choice != QUIT);
return( 0 );
}
int sample()
{
cout << "Forming Lists" << endl;
int two = 2;
List<int> l1 = List<int>();
List<int> l2 = List<int>();
l1.Listinsert( one );
l1.Listinsert( two );
cout << "print l1" << endl;
printList( l1 );
cout << "l2 = l1" << endl;
l2 = l1;
cout << "print l2" << endl;
printList( l2 );
cout << "l1.remove(one)" << endl;
l1.Listremove( one );
cout << "print l1" << endl;
printList( l1 );
cout << "print l2" << endl;
printList( l2 );
cout << "findPrevious 1 in l2" << endl;
ListIterator<int> iter = l2.ListfindPrevious( one );
if (iter.isValid())
{
cout << "--iter valid" << endl;
cout << iter.retrieve() << endl;
}
else
{
cout << "--iter not valid" << endl;
}
cout << "findPrevious 2 in l2" << endl;
iter = l2.ListfindPrevious( two );
if (iter.isValid())
{
cout << "--iter valid" << endl;
cout << iter.retrieve() << endl;
}
else {
cout << "--iter not valid" << endl;
}
cout << "findPrevious 1 in l1" << endl;
iter = l1.ListfindPrevious( one );
if (iter.isValid())
{
cout << "--iter valid" << endl;
cout << iter.retrieve() << endl;
}
else
{
cout << "--iter not valid" << endl;
}
cout << "findPrevious 2 in l1" << endl;
iter = l1.ListfindPrevious( two );
if (iter.isValid())
{
cout << "--iter valid" << endl;
cout << iter.retrieve() << endl;
}
else
{
cout << "--iter not valid" << endl;
}
cout << "print l1" << endl;
printList( l1 );
cout << "l1.remove(one)" << endl;
l1.Listremove( one );
cout << "print l1" << endl;
printList( l1 );
return( 0 );
}
void printList( const List<int>& l )
{
if (l.LisEmpty())
cout << "Empty list" << endl;
else
{
ListIterator<int> iter = l.Lfirst();
while (iter.isValid())
{
cout << iter.retrieve() << " -> ";
iter.advance();
}
cout << "NULL";
cout << endl;
}
}
OPTION menu()
{
char choice;
OPTION result;
cout << "(M)akeEmpty I(s)Empty (R)emove (I)nsert (F)indPrevious (P)rint (Q)uit: " << endl;
cin >> choice;
switch( choice )
{
case 'M':
case 'm':
result = MAKEEMPTY;
break;
case 'S':
case 's':
result = ISEMPTY;
break;
case 'R':
case 'r':
result = REMOVE;
break;
case 'I':
case 'i':
result = INSERT;
break;
case 'F':
case 'f':
result = FINDPREVIOUS;
break;
case 'Q':
case 'q':
result = QUIT;
break;
case 'P':
case 'p':
result = PRINT;
break;
}
return( result );
}
LISTNODE.cpp
#ifndef LISTNODE_CPP
#define LISTNODE_CPP
#include "ListNode.h"
namespace cs20
{
template <class Object>
ListNode<Object>::ListNode( const Object& theElement, ListNode<Object> * node )
{
element = theElement;
next = node;
}
template <class Object> bool ListNode<Object>::nextIsNull() const
{
return( next == NULL );
}
template <class Object> const Object& ListNode<Object>::getElement() const
{
return( element );
}
template <class Object> ListNode<Object>* ListNode<Object>::getNext() const
{
return( next );
}
template <class Object> void ListNode<Object>::setNext( ListNode<Object> * node )
{
next = node;
}
}
#endif
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.