created: 07/04/2019

# Chapter 131 Programming Exercises

## Exercise 1 — Array to List

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 )`
```

## Exercise 2 — More Nodes

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.

## Exercise 3 — Search

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.

## Exercise 4 — set()

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.

## Exercise 5 — copy()

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 `Node`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 own `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.

## Exercise 6 — delete()

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 all `Node`s containing `victim` from the `LinkedList`. Return the number of `Node`s deleted. If the list is initially empty, do nothing and return zero. If the list contains no `victim`s return zero and don't make any changes to the list. If the first `Node` matches `victim`, change `headPtr`.

This will be fairly tricky because to unlink a node from the chain you need access to the previous node.