created: 07/04/2019
Add a constructor to the class that takes an array of integers as a parameter. The nodes of the linked list get their values from the array. The value of the first node (at index 0) is the integer in array cell 0 and so on in order.
public LinkedList( int[] values )
Click here to go back to the main menu.
Modify the program ChainMaker
on page 10 so that it creates many more
Nodes
and links them into a list.
The traversal part of the program should work without modification.
Click here to go back to the main menu.
Add the method int search( int target )
that searches for a target value and returns the index of the node
that contains the target, or -1 if no node contains the target.
Use linear search (as described in the previous chapter) to do this. Because the list is ordered, the search traverses the list until the target is found, or a node greater than the target is found, or the end is reached.
Click here to go back to the main menu.
Add a set()
method to the class:
void set( int index, int value ) throws IndexOutOfBoundsException
The method changes the value of the node at location index
.
A node must already exist at that location.
Of course, if insertFirst()
puts a new node at the head of the list,
then indexes of all nodes after it increase by one.
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 its ownheadPtr
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.
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
.
This will be fairly tricky because to unlink a node from the chain you need access to the previous node.
Click here to go back to the main menu.
End of the Exercises