toString methodAs mentioned in lecture, finish the bare implementation of
the StringNode‘s toString method iteratively. The starting code
is included below.
public String toString() { String str = ""; // what should go here? return str; }
StringNode classDownload the StringNode class
and open it in VSCode. For the following questions,
assume that there is a variable head referring to the head of a string
formed by StringNode objects, representing the word "hello".
Using the StringNode constructor, come up with an initialization
of a StringNode variable head that constructs the linked list
mentioned above. 1
Draw a diagram of the linked list, representing references between nodes as arrows. 2
Draw a trace of the print method from the StringNode class,
which has been reproduced below.
public static void print(StringNode str) { if (str == null) { System.out.println(); return; } System.out.print(str.ch); print(str.next); }
Draw a diagram of the print stack frames as they are on the stack
when the base case is reached, being sure to represent references
as arrows. 3
Write a static, recursive method numOccurrences that, when given
a reference to the head of a StringNode linked list and a char
targetChar, counts the number of occurrences of the target character
in the linked list. 4
Now convert this method to an iterative one. After writing your iterative version, enumerate the advantages and disadvantages of both approaches. 5
StringNode list from a StringThe convert method in the StringNode class takes a String
and converts it into a StringNode object.
This method has been reproduced below:
public static StringNode convert(String s) { if (s == null || s.length == 0) // base case return null; else{ rest = convert(s.substring(1)); str = new StringNode(s.charAt(0), rest); return str; } }
Trace the action of this method when it is called on the string "dogs"
Convert this recursive method to an iterative one. We must be careful to keep the characters in order in the linked list. How can we design our iterative solution such that it will link the list in the right order and return a reference to the first node in the list? 7
Compare the recursive and iterative solutions. Discuss the efficiency and elegance of both approaches. 8
There are several ways to do this. Probably the simplest is the following:
StringNode node1 = new StringNode('o', null); StringNode node2 = new StringNode('l', node1); StringNode node3 = new StringNode('l', node2); StringNode node4 = new StringNode('e', node3); StringNode node5 = new StringNode('h', node4);
Going the other way (creating the node containing 'h' first
and continuing towards the end of the word) is probably not
a good idea, since after creating the nodes for 'h' and
'e', you’d have to set the 'h' node’s next reference to
the 'e' node.
We also saw an equivalent approach to the one included
above using nested calls to the StringNode constructor:
StringNode head = new StringNode('h', new StringNode('e', new StringNode('l', new StringNode('l', new StringNode('o', null) ) ) ) );
Bizarre parentheses aside, this approach just calls the
constructors repeatedly, using the return value of each constructor,
which is the memory location of the newly constructed object,
in the constructor call of the previous node. This sets up each
node’s next reference the same way as the first approach, except
the first approach relied on local variables to keep the new memory
locations. ↩
Here’s the diagram:
+---+
head | | |
+-|-+
+=====+
|
v
+-----+ +-----+ +-----+ +-----+ +-----+
| 'h' | | 'e' | | 'l' | | 'l' | | 'o' |
| | | | | | | | | |
+-----+ +-----+ +-----+ +-----+ +-----+
| =======>| =======>| =======>| =======>| |
+-----+ +-----+ +-----+ +-----+ +-----+
Here’s the trace. Note that the the arrows representing the references
do not point to a particular field in a StringNode object; if an arrow
head touches an object, it represents a reference to the starting
address of the object.
+-----+ +-----+ +-----+ +-----+ +-----+
| 'h' | | 'e' | | 'l' | | 'l' | | 'o' |
| | | | | | | | | |
+-----+ +-----+ +-----+ +-----+ +-----+
| =======>| =======>| =======>| =======>| |
+-----+ +-----+ +-----+ +-----+ +-----+
^ ^ ^ ^ ^
| | | | |
| +=====+ +==+ | +==+
+==========+ | | | |
+-|-+ | | | |
print(str | | | ) | | | |
+---+ | | | |
+-|-+ | | |
print(str | | | ) | | |
+---+ | | |
+-|-+ | |
print(str | | | ) | |
+---+ | |
+-|-+ |
print(str | | | ) |
+---+ |
+-|-+
print(str | | | )
+---+
+------+
print(str | null | )
+------+
Here’s the method developed in class:
public static int numOccurrences(StringNode n, char targetChar) { if (n == null) return 0; if (n.ch == targetChar) return 1 + numOccurrences(n.next, targetChar); else return 0 + numOccurrences(n.next, targetChar); }
Here’s the iterative version we came up with:
public static int numOccurrences(StringNode head, char targetChar) { if (head == null) return 0; int count = 0; StringNode trav = head; while (trav != null) { if (trav.ch == targetChar) count++; trav = trav.next; } return count; }
Here’s a trace:
convert("dogs") calls convert("ogs")
convert ("ogs") calls convert("gs")
convert("gs") calls convert("s")
convert ("s") calls convert("")
convert ("") hits the base case and returns null
convert("s") returns a new StringNode with 's' as the .ch value and null as the .next value
convert("gs") returns a new StringNode with 'g' as the .ch value and a reference to the node containing 's' as the .next value
convert("ogs") returns a new StringNode with 'o' as the .ch value and a reference to the node containing 'g' as the .next value
convert("dogs") returns a new StringNode with 'd' as the .ch value and a reference to the node containing 'o' as the .next value
Note that the first call to convert is the one that returns last, and it
returns a reference to the head of the list. ↩
Here’s one approach:
public static StringNode convert(String s){ if (s == null || s.length == 0) return null; StringNode firstNode = new StringNode(str.charAt(0), null); StringNode prevNode = firstNode; StringNode nextNode; for (int i = 0; i < s.length(); i++) { nextNode = new StringNode(s.charAt(i), null); prevNode.next = nextNode; prevNode = nextNode; } return firstNode; }
The recursive solution wins out here, due to its simplicity. The iterative
version is more difficult to read and debug, due to lots of variable
reassignments. We also need to keep track of the very beginning of the
linked list in the iterative solution, which forces us to do some special
processing at the beginning. The recursive solution has the property that,
when any given recursive call returns, it returns the head of a completely
formed linked list. This behavior allows the first call to convert to be the
one that returns the head of the entire list. (We use the call stack to our
advantage in the recursive version.) ↩
Last updated on July 25, 2025.