Section 18

Radix sort

1. Trace radix sort on the following input array. Before starting, determine the values of m and k. ¹

   7

   39

   20

   11

   16

   5

2. For the following sorting dilemmas, determine what our values for m and k could be if we were using radix sort. ²

   1. one hundred United States telephone numbers (of the form 555-123-4567)
   2. fifty scattered dollar bills (possible denominations: $1, $5, $10, $20, $50, $100)
   3. one billion 32-bit integers

Linked lists

Recall from today’s lecture that a linked list is a recursive data structure with the following definition:

A linked list is either an empty list or one node chained to a linked list.

Linked lists are useful because each node in the list can hold arbitrary data, and can be grown and altered without the need for copying or shifting values (as in an array). Thus linked lists have the desirable qualities of dynamic resizability, the ability to store one or more values, and ease of deletion or alteration. In Java, we usually define a class for a linked list node (e.g., StringNode from lecture). In such a class, a forward reference to the next node is included (e.g., the StringNode class’ next field).

In our client programs we must remember to keep a reference to the first node in the linked list, since that node will give us access to the rest through recursive application of dereferences.

The head of a linked list containing one or more nodes is the first node in the list.

The client code often names the reference to the first node in the list head, following from the definition above.

The tail of a linked list is the “rest” of the linked list; the “rest” could be another node or the empty list.

Use the following simplified StringNode class when answering these questions.

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

Now consider the following diagram, a visualization of the Java virtual machine’s heap space, in which instances of the class StringNode have been created. Each node has been drawn with the value of their ch and next fields, and their starting positions in memory.

0xc000               0xbe00               0x30cb
*------*--------*    *------*--------*    *------*--------*
|  'a' | 0xbe00 |    |  'b' | 0x30cb |    |  'c' | 0xbb00 |
*------*--------*    *------*--------*    *------*--------*
 ch     next

0xa004               0xff00               0xbb00
*------*--------*    *------*--------*    *------*--------*
|  'd' | 0xff00 |    |  'e' |   null |    |  'f' | 0xa004 |
*------*--------*    *------*--------*    *------*--------*

Assume that there is a reference to the node at 0xc000 somewhere, such that the entire linked list does not get garbage collected by the Java virtual machine.

3. Instead of using arrows to represent each node’s next field, we have decided to write the actual values of each reference (or null, in the case of no reference). Convert our diagram to a diagram that looks like the lecture slides’ diagrams, where each node has an arrow pointing to the destination of the reference. If a node has a null in its next field, omit the arrow. ³

Suppose you have a reference to the node at address 0xbe00 contained in a variable called n, and a reference to the node at address 0xbb00 in a variable called m.

4. Add the variables n and m to the new diagram you created in the previous task. ⁴
5. If we assume that the variables are defined inside of a method, where should the memory space for those variables be shown? How would we change our diagram to reflect this? ⁵
6. What is the value of n.next? ⁶
7. What is the value of n.next.ch? ⁷
8. What is the value of n.next.next.next? ⁸
9. What is the value of the Boolean expression n.next.next == m? ⁹

For the following questions, draw a new diagram if the specified assignment changes anything. Assume each change is independent (i.e., for each question, refer to the original diagram).

10. How would the diagram change after the assignment n = m.next is executed? ¹⁰
11. How would the diagram change after the assignment m.next = m.next.next is executed? ¹¹
12. How would the diagram change after the assignment n = null is executed? ¹²

For the following questions, your answers will be a memory location. Denote this by using the 0x prefix for your answer.

We will use the convention from the lecture notes that defines a ch field as being two bytes “wide” and being stored first in a StringNode object.

13. What is the memory location of the first byte of the 'e' in the node containing it? What does this memory location also represent? ¹³

14. In the node containing 'b', provide the memory location of that node’s next field. ¹⁴

Last updated on July 24, 2025.