Linked Lists - Building Java Programs: A Back to Basics Approach - page 973

16. list 1 list 4 1 2

list2 2 3 4 list2 3

17. list 1 2 3 4 list 4 2

list2 3 1

Section 16.2: A Linked List Class
18. What are the two ways to change the contents of a linked list?

19. An element can be inserted at or removed from the beginning, middle, or end of a linked list. Which of the three loca-
tions is the most computationally expensive, and why? How does this compare against the result for an array list?

20. When you add or remove the element found at index i of a list, you must create a temporary current node refer-
ence and advance it through the list. At which index's node should the loop stop, relative to i ?

21. In an array list, it is possible to overrun the capacity of the array, at which point the list must be resized to fit. Is
resizing necessary on a linked list? What limits the number of elements that a linked list can have?

For each of the next three problems, you'll see pictures of long chains of linked nodes before and after changes.
(The . . . in the middle of the chain signifies an indeterminate large number of nodes.) Write the code that will
produce the given result by modifying links between the nodes shown and/or creating new nodes as needed. You
will need to write loops to advance to the end of the list in order to reach the node(s) to modify.

22.

... ...

list 7 16 list 42 42

(change all nodes to store the value 42)

23.

... ...

list 7 3 list 7 42

(change the last node to store the value 42)

24.

... ...

list 7 3 list 7 3 42

(add a node at the end that stores the value 42)

25. Write methods called min and max that return the smallest and largest values in the linked list respectively. For
example, if a variable called list stores [11,

7, 3, 42, 0, 14], the call of list.min() should return -7 and the call
of list.max() should return 42 . If the list is empty, throw an IllegalStateException .

Section 16.3: A Complex List Operation
26. What are the four cases examined in the addSorted method?

27. What is the “inchworm approach”? What advantages does this approach have over other approaches for examining a
linked list?

28. Write methods called sum and average that return the sum of all values in the list and the average value as a real num-
ber, respectively. For example, if a variable called list stores [11, 7, 3, 42, 0, 14] , the call of list.sum()
should return 63 and the call of list.average() should return 10.5 . If the list is empty, sum should return 0 and
average should return 0.0 .