Lab 8: A first look at linked lists

Task 1: Work with a linked list of characters

In lecture, we’ve been considering linked lists of characters, where each node in the linked list is an instance of the following class:

public class StringNode {
    private char ch;
    private StringNode next;
    ...
}

For example, we considered the following linked list, which represents the string "dog":

Note that each node in the linked list has two fields:

• the top field (the field ch), which stores a single character

• the bottom field (the field next), which is a reference of type StringNode. These next fields link the nodes together. They either hold a reference to the next node in the linked list, or (in the case of the last node) they have a value of null to indicate that there are no subsequent nodes.

Your tasks

1. Consider the following diagram, which is a visualization of a heap memory region in which a number of StringNode objects have been created. Each node includes the values of its ch and next fields, as well its starting position in memory.

        0xc000            0xbe00            0x3004
        +--------+        +--------+        +--------+
     ch |   'a'  |     ch |   'b'  |     ch |   'c'  |
        +--------+        +--------+        +--------+
   next | 0xbe00 |   next | 0x3004 |   next | 0xbb00 |
        +--------+        +--------+        +--------+
   
        0xa004            0xff00            0xbb00
        +--------+        +--------+        +--------+
     ch |   'd'  |     ch |   'e'  |     ch |   'f'  |
        +--------+        +--------+        +--------+
   next | 0xff00 |   next |  null  |   next | 0xa004 |
        +--------+        +--------+        +--------+
   

   Important notes:

   • Instead of using arrows to represent each node’s next field, we have written the actual value of each reference (or null, in the case of no reference). We have written these reference values as hexadecimal (base 16) numbers that begin with 0x.

   • The order of the nodes in the diagram does not necessarily correspond to the order of the nodes in the linked list. This is also true when you create a linked list in your program. The nodes are not necessarily next to each other in memory. They can be located at arbitrary locations on the heap. That is why each node must maintain a reference to the next node!

2. Convert the diagram above to one that looks like the diagrams from lecture, in which:

   • the nodes are shown in a single chain stretching from the first node to the last node in the linked list

   • references are drawn using arrows

   Your new diagram should still include the memory address of the start of each node.

   Note: The node containing the letter 'a' is the first node in the linked list. To determine the order of the remaining nodes, follow the next references!

3. Suppose that we have two variables in the main method of our StringNode class:

   • one called n, which holds a reference to the node at address 0xbe00

   • one called m, which holds a reference to the node at address 0xbb00

   Add the variables n and m to the diagram you created for question 2.

4. In the rest of this task, we will determine both the address and the value of several fields from our diagram.

   To do so, we will make the following assumptions:

   • the memory address of the ch field of a StringNode is the same as the address of the StringNode itself

   • the memory address of the next field of a StringNode is 2 more than the address of the StringNode itself.

   Complete the table shown below, filling in the address and value of the field specified by each expression from the left-hand column. We have done the first two expressions for you.

   expression         address        value
   ----------         -------        -----
   m.ch               0xbb00         'f'
   m.next             0xbb02         0xa004 (reference to the 'd' node)
   m.next.next
   n.next
   n.next.ch
   n.next.next.next
   

Task 2: Understand assignments involving references

To determine the effect of an assignment statement involving references, it can help to use the following procedure:

• Identify the two boxes – i.e., the variables/fields specified by the expressions on both sides of the assignment operator.

• Determine the value in the box specified by the expression on the right-hand side.

• Copy that value into the box specified by the expression on the left-hand side.

Beginning with our diagram from Task 1:

1. Draw the diagram that results from the following assignment:

   n = m.next;
   

2. Now modify the drawing to show the result of the following:

   m.next = m.next.next
   

Task 3: Trace a recursive linked-list method

The StringNode class includes a method called copy that uses recursion to incrementally create a deep copy of a linked-list of StringNode objects.`

public static StringNode copy(StringNode str) {
    if (str == null) {
        return null;
    }

    // make a recursive call to copy the rest of the list
    StringNode copyRest = copy(str.next);

    // create and return a copy of the first node,
    // with its next field pointing to the copy of the rest
    return new StringNode(str.ch, copyRest);
}

Let’s trace through the execution of the following call of this method:

StringNode s1 = StringNode.convert("dog");
StringNode s2 = StringNode.copy(s1);

Task 4: Trace an iterative linked-list method

The StringNode class includes a method called convert that uses iteration to gradually convert a Java String object to a linked-list string:

public static StringNode convert(String s) {
    if (s.length() == 0) {
        return null;
    }

    // Create the head node
    StringNode firstNode = new StringNode(s.charAt(0), null);

    // These two variables are needed to traverse down
    // the list as each "new" node created is linked to the
    // "previous" node.        
    StringNode prevNode = firstNode;
    StringNode nextNode;

    // Loop through the remaining characters of the string,
    // create a new node for each character and,
    // link it to the previous node.
    for (int i = 1; i < s.length(); i++) {
        // Create the next node 
        nextNode = new StringNode(s.charAt(i), null);

        // Link it to the previous node
        prevNode.next = nextNode;

        // Update the previous node
        prevNode = nextNode;
    }

    // Return the first node - head of the list
    return firstNode;
}

Note that the method uses several variables of type StringNode:

• one called firstNode, which holds a reference to the node containing the first character; we need this variable so that the method can return a reference to the first node after the entire linked list has been created

• one called nextNode, which is used to hold a reference to each new node that is created (except the first node)

• one called prevNode, which starts out pointing to the first node, and which stays one node behind nextNode in the linked list

Let’s trace through the execution of the following call of this method:

StringNode s1 = StringNode.convert("node");

Task 5: Convert an iterative method to a recursive one

Now rewrite the convert() method. Remove the existing iterative implementation of the method, and replace it with one that uses recursion instead.

Your new method should be much simpler! It should take advantage of our usual recursive approach to processing strings – both Java String objects, and strings that are represented as linked lists:

• base case: if the string is empty, handle it directly

• recursive case: take care of the first character, and make a recursive call to handle the rest of the string.

To test your recursive version of the method, add statements like the following to your testDriver main method:

StringNode s = StringNode.convert("node");
System.out.println(s);

(Note: We are able to see the string when we print ou the node because our StringNode class includes a toString() method.)