Test Yourself #2

Question 1.

L.next.data = "cat";

Question 2.

L.next = new Listnode("rat", L.next);

Test Yourself #3

The list begins:

and after the code looks like:

and this is correct.

Test Yourself #4

 operation linked list array remove first O(1) O(N) remove last O(N) O(1)

For linked list: To remove the first node you only have to do L = L.next so this is O(1). To remove the last node you must traverse the list from the first node to get to the next to last node to do the delete so this is O(N).

For arrays: To remove the first item you must shift all the remaining items one array location to the left to fill in the hole so this is O(N). To remove the last item there are no shifts because no items are to the right so this is O(1).

Test Yourself #5

```    // Note: this code has excessive comments to help you understand it in detail.
// returns true if val is in circular linked list L; otherwise returns false
if (L == null) return false;  // no items on list so not found
if (L.data.equals(val)) return true;  // val is in first node on list
Listnode tmp = L.next;
while (tmp != L) {  // stops from going past first node and going in circles
if (tmp.data.equals(val)) return true;  // found val at this node
tmp = tmp.next;
}
return false;  // did not find val in list
```