8.10. Additional Practice Exercises

Text version of Problem 1

Construct makeChain so that it returns with a reference to the first of three new nodes containing "A", "B", and "C", in that order. Create each node with the one-argument constructor and connect the nodes using setNext. The final node's next reference value must be null.

Write the letters of the correct blocks in order and give each block an indentation level. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

Node head = new Node("A");

Block B

public static Node makeChain() {

Block C

head.getNext().setNext(new Node("C"));

Block D

return head;

Block E

head.setNext(new Node("C"));

Block F

head.setNext(new Node("B"));

Block G

Sample solution for Problem 1

Block order: B, A, F, C, D, G.

Indentation levels: 0, 1, 1, 1, 1, 0.

public static Node makeChain() {
    Node head = new Node("A");
    head.setNext(new Node("B"));
    head.getNext().setNext(new Node("C"));
    return head;
}

getNext retrieves the reference value for the second node, so calling setNext on that node adds the third node after it. Calling head.setNext again replaces the first node's successor: the chain reachable from head would contain only A and C. The one-argument constructor initializes each new node's next reference value to null.

Text version of Problem 2

Construct markSecond. Assume head refers to a node with a successor, and the successor's item is a non-null String. Append "!" to that item's value through a local reference named alias, then return with the updated reference value obtained through head. Preserve every node and link; do not allocate a replacement node.

Write the letters of the correct blocks in order and give each block an indentation level. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

Node alias = new Node(head.getNext().getItem());

Block B

return head.getNext().getItem();

Block C

Node alias = head.getNext();

Block D

public static String markSecond(Node head) {

Block E

String original = alias.getItem();

Block F

alias.setItem(original + "!");

Block G

Sample solution for Problem 2

Block order: D, C, E, F, B, G.

Indentation levels: 0, 1, 1, 1, 1, 0.

public static String markSecond(Node head) {
    Node alias = head.getNext();
    String original = alias.getItem();
    alias.setItem(original + "!");
    return head.getNext().getItem();
}

Assigning the result of head.getNext() copies a reference value. Both alias and the first node's next field then refer to the same node. getItem reads its item, and setItem replaces that item's reference value. It does not modify the original String object. The distractor creates a separate node, so the original successor's item would remain unchanged.

Text version of Problem 3

Construct prepend to allocate one new node containing item and return with a reference to it as the new head. Its successor must be the original head. The input head may be null. Preserve all existing nodes, items, and links.

Write the letters of the correct blocks in order and give each block an indentation level. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

public static Node prepend(Node head, String item) {

Block B

added.setNext(head);

Block C

head.setNext(added);

Block D

return added;

Block E

Node added = new Node(item);

Block F

Sample solution for Problem 3

Block order: A, E, B, D, F.

Indentation levels: 0, 1, 1, 1, 0.

public static Node prepend(Node head, String item) {
    Node added = new Node(item);
    added.setNext(head);
    return added;
}

The new node stores a copy of the original head's reference value through setNext. This works even when that value is null. Returning with the reference value stored in added lets the caller store the new head; assigning a method parameter would not update the caller's variable. The distractor changes an existing link and throws NullPointerException for an empty chain.

Text version of Problem 4

Construct insertAfter to insert one new node containing item immediately after previous. Assume previous is non-null; its next reference value may be null. Preserve every existing node and item, and keep the original successor after the inserted node.

Write the letters of the correct blocks in order and give each block an indentation level. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

added.setNext(previous.getNext());

Block B

Node added = new Node(item);

Block C

added.setNext(previous);

Block D

public static void insertAfter(Node previous, String item) {

Block E

previous.setNext(added);

Block F

Sample solution for Problem 4

Block order: D, B, A, E, F.

Indentation levels: 0, 1, 1, 1, 0.

public static void insertAfter(Node previous, String item) {
    Node added = new Node(item);
    added.setNext(previous.getNext());
    previous.setNext(added);
}

Read the original successor with getNext and store its reference value in the new node before replacing the link from previous. Reversing those two updates makes the new node its own successor. The distractor instead links back to previous, forming a two-node cycle after attachment and losing the original suffix from that chain.

Text version of Problem 5

Construct removeAfter to remove the node immediately after previous from a chain and return with a reference to the removed node. Assume previous and its successor are non-null. The removed node may be the final node. Preserve all item values and all links except previous's next link; leave the removed node's own link unchanged.

Write the letters of the correct blocks in order and give each block an indentation level. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

public static Node removeAfter(Node previous) {

Block B

Node successor = removed.getNext();

Block C

previous.setNext(null);

Block D

previous.setNext(successor);

Block E

Node removed = previous.getNext();

Block F

return removed;

Block G

Sample solution for Problem 5

Block order: A, E, B, D, F, G.

Indentation levels: 0, 1, 1, 1, 1, 0.

public static Node removeAfter(Node previous) {
    Node removed = previous.getNext();
    Node successor = removed.getNext();
    previous.setNext(successor);
    return removed;
}

removed preserves a reference to the node being bypassed. successor stores that node's next reference value, which may be null. Setting the predecessor's link to this value preserves the remaining suffix. The distractor works only when removing the final node; otherwise it disconnects the suffix from previous. Removing a node from a chain does not destroy the object.

Text version of Problem 6

Construct printItems to print each item's value on its own line, from the first node through the final node. Print nothing for an empty chain. Assume a finite, acyclic chain; head may be null. Preserve the value of head and every node's item and link.

Write the letters of the correct blocks in order and give each block an indentation level. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

current.setNext(current.getNext());

Block B

Block C

while (current != null) {

Block D

while (current.hasNext()) {

Block E

Node current = head;

Block F

current = current.getNext();

Block G

System.out.println(current.getItem());

Block H

public static void printItems(Node head) {

Block I

Sample solution for Problem 6

Block order: H, E, C, G, F, B, I.

Indentation levels: 0, 1, 1, 2, 2, 1, 0.

public static void printItems(Node head) {
    Node current = head;
    while (current != null) {
        System.out.println(current.getItem());
        current = current.getNext();
    }
}

The loop processes the node currently referenced by current before advancing. Testing current != null includes the final node and safely handles an empty chain. hasNext tests for a successor, so it is the wrong condition when every node must be processed. Assigning current.getNext() to the local variable advances traversal without changing any links. The setter distractor leaves current unchanged, so the loop repeats indefinitely for a nonempty chain.

Text version of Problem 7

Construct countNodes to return with the number of nodes reachable from head. Return with zero for an empty chain. Assume a finite, acyclic chain with at most Integer.MAX_VALUE nodes. Preserve the value of head and every node's item and link.

Write the letters of the correct blocks in order and give each block an indentation level. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

int count = 0;
Node current = head;

Block B

return count;

Block C

Block D

while (current != null) {

Block E

int count = 1;
Node current = head;

Block F

count++;
current = current.getNext();

Block G

public static int countNodes(Node head) {

Block H

Sample solution for Problem 7

Block order: G, A, D, F, C, B, H.

Indentation levels: 0, 1, 1, 2, 1, 1, 0.

public static int countNodes(Node head) {
    int count = 0;
    Node current = head;
    while (current != null) {
        count++;
        current = current.getNext();
    }
    return count;
}

Initially no nodes have been visited, so count starts at zero. Each iteration counts one node and advances to its successor. When current becomes null, every reachable node has been counted. The paired distractor incorrectly counts a node before visiting one. The two initializations share a block because either could be written first without changing the result.

Text version of Problem 8

Construct append to allocate one new node containing item and append it to a finite, acyclic chain. Return with the original head reference for a nonempty chain, or the new node for an empty chain. Preserve existing items and links except for the original final node's next link.

The empty-chain case is grouped into one block. Preserve its internal indentation while setting the indentation of the whole block.

Write the letters of the correct blocks in order and give each block an indentation level. Leave incorrect blocks unused and preserve relative indentation within each block.

Block A

}
current.setNext(added);

Block B

return added;

Block C

public static Node append(Node head, String item) {

Block D

Node current = head;
while (current.getNext() != null) {

Block E

Node current = head;
while (current != null) {

Block F

return head;

Block G

Node added = new Node(item);
if (head == null) {
    return added;
}

Block H

current = current.getNext();

Block I

Sample solution for Problem 8

Block order: C, G, D, H, A, F, I.

Indentation levels: 0, 1, 1, 2, 1, 1, 0.

public static Node append(Node head, String item) {
    Node added = new Node(item);
    if (head == null) {
        return added;
    }
    Node current = head;
    while (current.getNext() != null) {
        current = current.getNext();
    }
    current.setNext(added);
    return head;
}

Handle an empty chain before dereferencing a node. For a nonempty chain, stop at the node whose next reference value is null and attach the new node there. Testing current != null instead advances past that node and causes NullPointerException at setNext. Return with the original head reference so that the caller can still reach the entire chain; returning with the reference value stored in added would expose only the new final node.

8.10. Additional Practice Exercises¶

8.10.1. Code Tracing¶

8.10.2. Parsons Problems¶