Project 2A: Working With Singly-Linked Lists (REQUIRED) Complete the following e

Question

Project 2A:Working With Singly-Linked Lists (REQUIRED)

Complete the following exercises using the cs20::List class presented in class.

1. Without using a ListIterator, define and implement a new operation calledinsert_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<Object>::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?

2. Create a new method on a List that determines whether the list contains items all in increasing order. Recall that you can compare values against one another using > operator. For example, for a list containing head-() (11) (8) (15) (3), isIncreasing() should return false. However, it would return true when working on a list containing head- () (7) (9) (15). When an empty list or a list with one element, it should return true.

This new operation should have the signature:

bool List<Object>::isIncreasing() const;

Because it has been marked const, this method is saying that it is read-only. When your implementation runs, you won't be able to actually change any data members of the List passed to your method. Create a test driver program that exercises each of these exercises to satisfy yourself that your implementation is correct. For example, you should print the List before and after invoking the operation.

TESTING HINT:

Run the methods: insert( 3 ); insert( 2 ); insert( 1 ); Print the list. What should it look like?
Call: isIncreasing(); What should it return?
Print the list. What should it look like?
Run the methods: remove( 3 ); remove( 2 ); Print the list. What should it look like?
Call: isIncreasing(); What should it return? Print the list. What should it look like?
Run the methods: remove( 1 );
Run the methods: insert( 7 ); insert( 9 ); insert( 11 ); Print the list. What should it look like?
Call: isIncreasing(); What should it return?
Print the list. What should it look like?

Explanation / Answer

1)

For first part I have written the code for the same:

template <class Object>
void List<Object>::insert_back( const Object& data ) {
ListNode<Object>* newnode = new ListNode<Object>( data, tail_of_list->getNext() );
if( tail_of_list != NULL )
{
tail_of_list->setNext( newnode );
}
tail_of_list = newnode;
if( head->getNext() == NULL )
{
head->setNext(newnode);
}
}

2)

working code for second part:

template <class Object>
bool List<Object>::isIncreasing() const
{
Listtemp_node<Object>* temp_node= head;
while (temp_node->getNext() != NULL)
{
if (temp_node->getNext()->getElement() <= temp_node->getElement())
return false;
temp_node = temp_node->getNext();
}
return true;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.