Chapter 101 Programming Exercises

Exercise 1

Add some methods to the LinkedList class:

public int search( int target );

Search (using linear search) for the target in the linked list. If the target is found, return the number of the node that contains it. Start numbering nodes at zero (like an array). If the target is not found, return -1. If the list is empty, return -1.

public int maximum();
public int minimum( );

Find the maximum (or minimum) element of the list. Start the provisional maximum (or minimum) the the value in the first node of the list. If the list is empty, return 0. It is up to the caller to check that the list contains some elements.

public int count( int target );
int count( );

Traverse the linked list counting the number of times the target occurs. If it does not occur, return zero. If count() has no argument, count the total number of notes. Recall that with method overloading there can be several methods with the same name. The arguments in the method call determine which one is invoked. If the list is empty, return 0.

public int getElement( int index );
void setElement( int index, int value );

Return the value in the node at index. If index does not exist, throw an IndexOutOfBoundsException.

Set the value in the node at index. If index does not exist, throw an IndexOutOfBoundsException.

public void traverse();

Modify the traverse() of the chapter so that it can nicely display long lists. Output a newline character "\n" after every 25 integers. For an even greater improvement, format each integer using DecimalFormat so the integers line up in columns.

Click here to go back to the main menu.

Exercise 2

Add a copy() method to the LinkedList class:

public LinkedList copy();

Make an copy of a LinkedList. Make a copy of the object corresponding to the LinkedList class and make new copies of all the Nodes linked to it. After it is made, the copy should be completely separate of the original list, with its own nodes chained off its headPtr variable.

For example, this fragment creates a copy:

LinkedList listA = new LinkedList();
listA.insertFirst( 4 ); listA.insertFirst( 3 ); listA.insertFirst( 2 ); listA.insertFirst( 1 );

LinkedList listB = listA.copy();  // Make a copy of listA

To verify that the new list is a complete copy of the original delete a few nodes of the original and then traverse the copy to check that it is still intact.

Click here to go back to the main menu.

Exercise 3

As presented in this chapter, only the first and last Nodes of a LinkedList can be deleted. Write a method that deletes all Nodes holding a particular value:

public int delete( int victim );

Delete all Nodes containing victim from the LinkedList. Return the number of Nodes deleted. If the list is initially empty, do nothing and return zero. If the list contains no victims return zero and don't make any changes to the list. If the first Node matches victim, change headPtr.

End of the Exercises