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 atindex
. Ifindex
does not exist, throw anIndexOutOfBoundsException
.
Set the value in the node atindex
. Ifindex
does not exist, throw anIndexOutOfBoundsException
.
public void traverse();
Modify thetraverse()
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 usingDecimalFormat
so the integers line up in columns.
Click here to go back to the main menu.
Add a copy()
method to the LinkedList
class:
public LinkedList copy();
Make an copy of aLinkedList
. Make a copy of the object corresponding to theLinkedList
class and make new copies of all theNode
s linked to it. After it is made, the copy should be completely separate of the original list, with its own nodes chained off itsheadPtr
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.
As presented in this chapter, only the first and last Node
s of a LinkedList
can be deleted.
Write a method that deletes all Node
s holding a particular value:
public int delete( int victim );
Delete allNode
s containingvictim
from theLinkedList
. Return the number ofNode
s deleted. If the list is initially empty, do nothing and return zero. If the list contains novictim
s return zero and don't make any changes to the list. If the firstNode
matchesvictim
, changeheadPtr
.
End of the Exercises