Lab 7: Merge sort; a first look at linked lists

• You are welcome and encouraged to work with a partner during labs, but please remember to be checked off individually.

Task 1: Practice merge sort

Your work for this lab should go on the piece of paper that we give you. Please show your paper to a staff member before you leave the lab.

Like quicksort, merge sort uses a recursive, divide-and-conquer approach. However, whereas quicksort does all of its work during the divide stage (before making the recursive calls), merge sort instead does all of its work after a given set of recursive calls have returned, as it merges sorted subarrays.

1. Let’s trace through mergesort on the following array:

                     -----------------------------------------
                     |  7 | 39 | 20 | 11 | 16 |  5 |  9 | 28 |
                     -----------------------------------------
                                       split
                                 /               \
                 ---------------------       ---------------------
                 |    |    |    |    |       |    |    |    |    |
                 ---------------------       ---------------------
                       split                           split
                   /           \                   /           \
           -----------     -----------       -----------     -----------
           |    |    |     |    |    |       |    |    |     |    |    |
           -----------     -----------       -----------     -----------
         split               split               split               split
       /       \           /       \           /       \           /       \
    ------   ------     ------   ------     ------   ------     ------   ------
    |    |   |    |     |    |   |    |     |    |   |    |     |    |   |    |
    ------   ------     ------   ------     ------   ------     ------   ------
       \       /           \       /           \       /           \       /
         merge               merge               merge               merge
      -----------         -----------         -----------         -----------
      |    |    |         |    |    |         |    |    |         |    |    |
      -----------         -----------         -----------         -----------
                \         /                             \         /
                   merge                                   merge  
           ---------------------                   ---------------------
           |    |    |    |    |                   |    |    |    |    |
           ---------------------                   ---------------------
                     \                                       /
                     -----------------------------------------
                     |    |    |    |    |    |    |    |    |
                     -----------------------------------------
   

2. What major advantage does merge sort have over quicksort with respect to time complexity?

3. What major disadvantage does merge sort have compared to quicksort with respect to space complexity?

Task 2: 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 3: 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 2:

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 4: Show us your work

You should show the paper with your work to the teaching assistant.

Don’t worry if you didn’t finish all of the tasks. You should just show us whatever work you were able to complete during lab.

Optional Tasks

Task 5: Trace a recursive linked-list method

In lecture, we have continued to work with 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;
    ...
}

One of the methods in the StringNode class is the following recursive method called numOccur:

public static int numOccur(StringNode str, char ch) {
    if (str == null) {
        return 0;
    }

    int numInRest = numOccur(str.next, ch);
    if (str.ch == ch) {
        return 1 + numInRest;
    } else {
        return numInRest;
    }
}

It finds the number of occurrences of the character ch in the linked list to which str refers.

Considered the following linked list, which represents the string "java":

Trace the following call of the numOccur() method on this linked list:

int count = numOccur(s, 'a');

which we assume is being made from the main() method in the StringNode class.

You should begin with something like the following at the bottom of the page:

Note that we have included the stack frame for main(), and above it the stack frame for the initial call to numOccur(). (We’ve omitted the parameter ch from that stack frame, because its value ('a') doesn’t change over time.

To complete the trace, you should:

• Add stack frames as needed for each recursive call – filling in the the value of str in each of them – until you reach the base case.

• On the way back from the base case, fill in the value of numInRest in each stack frame, continuing until you get back to the main() method.

• Fill in the value of count that is assigned after the initial call to numOccur() has returned.

Task 6: Convert a recursive method to an iterative one

To begin this task:

• Create a folder named lab7.

• Download StringNode.java, and save it in the lab7 folder.

Rewrite the numOccur() method that we traced in Task 1. Remove the existing recursive implementation of the method, and replace it with one that uses iteration instead.

You should make use of the template for iteratively traversing a linked list that we considered in lecture:

StringNode trav = str;    // make trav point to the first node
while (trav != null) {
    // do something here
    trav = trav.next;
}

To test your iterative version of the method, compile the class, and try tests like this one:

> StringNode s = StringNode.convert("java");
> System.out.println( StringNode.numOccur(s, 'a') );
2

Task 7: Trace an iterative linked-list method

The StringNode class includes another 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) { // explicit return
        return null;
    }

    StringNode firstNode = new StringNode(s.charAt(0), null);
    StringNode prevNode = firstNode;
    StringNode nextNode;

    for (int i = 1; i < s.length(); i++) {
        nextNode = new StringNode(s.charAt(i), null);
        prevNode.next = nextNode;
        prevNode = nextNode;
    }

    return firstNode;
}

We used this method in our testing for Task 2.

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");

As we trace through, add the diagram to the paper that you used in Task 1.

Task 8: 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, compile the file, and try tests like this one:

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

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