8.8. Additional Practice Exercises

8.8.1. Code Tracing with Node

Consider the following Java program:

For each line in CODE BLOCKS 1–3:

  • Carefully trace through the code and draw a diagram of the linked structure after that line executes.

  • Each Node object should be drawn as a box containing its item (e.g., Mario, Luigi) and next fields.

  • Write null whenever a next reference is null.

  • Reference variables (player1, player2, player3) must be drawn pointing to the correct node.

  • When next points to another node, draw an arrow showing the connection.

  • Redraw the entire diagram after each line (do not just update the old one). This will help you track changes clearly.

  • Number each step in your notes. There are 7 lines total in CODE BLOCKS 1–3, so you should produce 7 separate diagrams.

  • Take note of temporary nodes that are created but not assigned to a variable (e.g., Peach in CODE BLOCK 2). Even if unreachable, you can annotate them as created.

  • Pay attention to next references that link existing nodes (e.g., when player1.setNext(new Node("Bowser"))) — this will modify the chain.

 4// CODE BLOCK 1
 5Node player1 = new Node("Mario");
 6player1.setItem("Luigi");
 7
 8// CODE BLOCK
 9new Node("Peach", player1);
10
11// CODE BLOCK 3
12Node player2 = new Node("Yoshi");
13player2.setNext(player1);
14player1.setNext(new Node("Bowser"));
15player2.getNext().getNext().setNext(new Node("DonkeyKong"));
16
17// CODE BLOCK 4
18Node player3 = player2.getNext().getNext();
19player3.getNext().setNext(new Node("Toad"));
20
21// CODE BLOCK 5
22System.out.println(player3.getNext().getNext().getNext());
23System.out.println(player2.getItem());
24System.out.println(player1.getNext().getNext().getItem());
25System.out.println(player3.getNext().getNext().getItem());
26
27// CODE BLOCK 6
28player1.setNext(new Node("Wario"));
29
30// CODE BLOCK 7
31System.out.println(player1.getNext().getNext());
Solution
code visualization

Fig. 8.1 Note: This memory map depicts the program after executing through line 5. The debugger breakpoint is on line 6.

code visualization

Fig. 8.2 Note: This memory map depicts the program after executing through line 8. The debugger breakpoint is on line 9.

code visualization

Fig. 8.3 Note: This memory map depicts the program after executing through line 11. The debugger breakpoint is on line 12.

code visualization

Fig. 8.4 Note: This memory map depicts the program after executing through line 12. The debugger breakpoint is on line 13.

code visualization

Fig. 8.5 Note: This memory map depicts the program after executing through line 13. The debugger breakpoint is on line 14.

code visualization

Fig. 8.6 Note: This memory map depicts the program after executing through line 17. The debugger breakpoint is on line 18.

code visualization

Fig. 8.7 Note: This memory map depicts the program after executing through line 18. The debugger breakpoint is on line 19.

code visualization

Fig. 8.8 Note: This memory map depicts the program after executing through line 27. The debugger breakpoint is on line 28.

Part A — Line-by-line trace

We trace CODE BLOCKS 1–6 of the program step by step. Each step corresponds to one line of code executed. We draw the linked structure with reference variables and arrows.

  • Each Node is drawn as: [item | next].

  • null (or mull) means no next node.

  • Reference variables (e.g., player1, player2) point to their nodes.

  • Temporary nodes (like Peach) are noted but may become unreachable.

Step 1 (CODE BLOCK 1, Line 1)

Node player1 = new Node("Mario");

Creates a new Node (node1) with item = "Mario" and next = null. player1 references this node.

Diagram:

player1 → [ “Mario” | null ]

Step 2 (CODE BLOCK 1, Line 2)

player1.setItem("Luigi");

Updates node1’s item field to "Luigi". Structure unchanged.

Diagram:

player1 → [ “Luigi” | null ]

Step 3 (CODE BLOCK 2, Line 1)

new Node("Peach", player1);

Creates nodeP with item = "Peach", next = player1. But no variable stores nodeP → it becomes unreachable.

Diagram:

Unreferenced: [ “Peach” | → player1 ] player1 → [ “Luigi” | null ]

Step 4 (CODE BLOCK 3, Line 1)

Node player2 = new Node("Yoshi");

Creates node2 with item = "Yoshi", next = null. player2 references node2.

Diagram:

player2 → [ “Yoshi” | null ] player1 → [ “Luigi” | null ]

Step 5 (CODE BLOCK 3, Line 2)

player2.setNext(player1);

Sets node2.next = player1.

Diagram:

player2 → [ “Yoshi” | → player1 ] player1 → [ “Luigi” | null ]

Step 6 (CODE BLOCK 3, Line 3)

player1.setNext(new Node("Bowser"));

Creates nodeB with item = "Bowser". Sets node1.next = nodeB.

Diagram:

player2 → [ “Yoshi” | → player1 ] player1 → [ “Luigi” | → nodeB ] nodeB → [ “Bowser” | null ]

Step 7 (CODE BLOCK 3, Line 4)

player2.getNext().getNext().setNext(new Node("DonkeyKong"));

Chain evaluation:

  • player2.getNext() → player1 node (Luigi).

  • .getNext() → nodeB (Bowser).

  • .setNext(new Node("DonkeyKong")) adds nodeDK.

Diagram:

player2 → [ “Yoshi” | → player1 ] player1 → [ “Luigi” | → nodeB ] nodeB → [ “Bowser” | → nodeDK ] nodeDK → [ “DonkeyKong” | null ]

Final state after CODE BLOCK 3:

Yoshi → Luigi → Bowser → DonkeyKong → null