Java Data Structure

Programming Project #2

Using the List, Stack and Queue code discussed in class, complete the assigned programming problem.

You need only do twoof the following three projects.

If I don't specifically mention O( n ), then you are free to implement the operation as quickly or as slowly as you like. However, if I do mention O( n ), then I would like you to try to get your code running with a certain speed in mind. It should be doable...

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

Complete the following exercises using the [url removed, login to view] class presented in class.

•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 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( Type data );

TESTING HINT: Run the methods: insert( new Integer( 3 ) ); insert( new Integer( 2 ) ); insert( new Integer( 1 ) );

Print the list. What should it look like?

Run the methods: insert_back( new Integer( 5 ) );

Print the list. What should it look like?

Run the methods: remove( new Integer( 5 ) );

Print the list. What should it look like?

Run the methods: insert_back( new Integer( 7 ) ); insert( new Integer( 8 ) );

Print the list. What should it look like?

Run the methods: remove( new Integer( 3 ) ); remove( new Integer( 2 ) ); remove( new Integer( 1 ) );

Run the methods: remove( new Integer( 7 ) ); remove( new Integer( 8 ) );

Print the list. What should it look like?

Run the methods: insert_back( new Integer( 5 ) );

Print the list. What should it look like?

•Create a new method on a List that determines the list does not have certain values. For example, for a list containing head-( ) (10) (8) (0) (-1), lacks( 12 ) should return true. However, it would return false when working on a list containing head- ( ) (100) (90) (10) (100) (12).

This new operation should have the signature: bool List::lacks( Type data );

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( new Integer( 3 ) ); insert( new Integer( 2 ) ); insert( new Integer( 1 ) );

Print the list. What should it look like?

Call: lacks( 12 ); What should it return?

Call: lacks( 1 ); 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: lacks( 3 ); What should it return?

Call: lacks( 1 ); What should it return?

Print the list. What should it look like?

Project 2b:Working With Stacks (COMPLETE EITHER 2B OR 2C)

Complete the following exercises using the [url removed, login to view] class presented in class.

•Create a new method on a Stack that determines whether the stack is in decreasing order from the top of the stack to its end. For example, for a stack containing top-(10) (18) (120) (150), isInIncreasingOrder( ) should return true. However, it would return false when working on a stack containing top-(100) (90) (10) (100).

This new operation should have the signature: bool Stack::isInIncreasingOrder( );

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 Stack befo

Java

Project ID: #1233146

About the project