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
Fig. 8.1 Note: This memory map depicts the program after executing through line 5. The debugger breakpoint is on line 6.¶
Fig. 8.2 Note: This memory map depicts the program after executing through line 8. The debugger breakpoint is on line 9.¶
Fig. 8.3 Note: This memory map depicts the program after executing through line 11. The debugger breakpoint is on line 12.¶
Fig. 8.4 Note: This memory map depicts the program after executing through line 12. The debugger breakpoint is on line 13.¶
Fig. 8.5 Note: This memory map depicts the program after executing through line 13. The debugger breakpoint is on line 14.¶
Fig. 8.6 Note: This memory map depicts the program after executing through line 17. The debugger breakpoint is on line 18.¶
Fig. 8.7 Note: This memory map depicts the program after executing through line 18. The debugger breakpoint is on line 19.¶
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