Laboratory: Implementing Lists with Linked Nodes

Read through the code of SimpleListExpt.java and SLLExpt.java.

a. Sketch the output you expect to see from SLLExpt.

b. Check your sketch experimentally.

How are linked lists typically implemented? We have three issues to consider: How we represent the nodes, how we reference nodes in the SimpleLinkedList class, and how we represent iterators.

Nodes are elements of the Node class, which is a named inner class.

 class Node
  {
    /**
     * The data stored in the node.
     */
    T data;

    /**
     * The next node in the list.  Set to null at the end of the list.
     */
    Node next;

    /**
     * Create a new node with specified data and next.
     */
    public Node(T data, Node next)
    {
      this.data = data;
      this.next = next;
    } // Node(T, Node)
  } // class Node

What fields go in the list class? We have a field, front, that contains a reference to a Node. However, the node that front references is not actually the front of the list. Instead, it's a special “dummy” node that comes before the front of the list. Why do we make that choice? It turns out that it's helpful if we want to be able to insert elements - it lets us avoid special cases. We also have a second field field may be famililar from the array-based implementation of lists: a field, mods keeps track of the number of modifications to the list and is used to ensure that iterators “fail fast”.

public class SimpleLinkedList<T>
    implements SimpleList<T>
{
  /**
   * The dummy node at the front of the list.
   */
  Node front;

  /**
   * The number of modifications to the list.  Used to determine
   * whether an iterator is valid.
   */
  long mods;

Because the iterators will need to access fields of the list, iterators are implemented as an anonymous inner class. Conceptually, iterators are between the values in the list. But it's not really possible to refer to something between two nodes. Hence, each iterator contains a field, cursor, that refers to the node that precedes the node that contains the value that will be returned by a subsequent call to next. (You will see that this approach makes the add method relatively easy to implement. However, it does not help us implement remove. We will revisit the difficulties in implementing remove in the future.

Do iterators need more than a reference to a Node? These iterators have two more fields. The field pos stores the index that value would have in an array-based implementation. (No, I don't think it's sensible to have such a field. But the list iterator interface expects us to be able to return integer indices.) And we have a mods field to help us decide whether or not the list has been changed by another iterator.

 public ListIterator<T> listIterator()
  {
    return new ListIterator<T>()
      {
        /**
         * The node that immediately precedes the value to be returned 
         * by next.
         */
        Node cursor = SimpleLinkedList.this.front;

        /**
         * The position in the list. (Included because the folks 
         * at Sun/Oracle decided that list iterators need to be 
         * able to return integer indices.)
         */
        int pos;

        /**
         * The number of modifications at the time this iterator was
         * created or last updated.
         */
        long mods = SimpleLinkedList.this.mods;

a. Sketch how you would implement the next method in the itetrator.

b. Compare your answer to the implementation given in SimpleLinkedList.java.

c. Sketch how you would implement the hasNext() method.

d. Compare your answer to the implementation given in SimpleLinkedList.java.

e. Sketch how you would implement the add(T val) method.

f. Compare your answer to the implementation given in SimpleLinkedList.java.

Here's a simple experiment to test the set method while iterating forward through a list.

    SimpleLinkedList<String> vm = new SimpleLinkedList<String>();
    SimpleListExpt.add(pen, vm, 
            new String[] { "Hey", "Where", "Did", "We", "Go?" });
    SimpleListExpt.setForwardExpt(pen, vm);

a. Suppose the set method is correctly implemented. What should the output of the experiment be?

b. Look at the current implementation of set. What do you expect the output to be?

c. Check your answer experimentally.

d. You've probably noted that set is not yet implemented. Assume that we're only going to iterate the list from front to back. Sketch how you might implement set.

e. Here's a simple strategy for implementing set, assuming that we only iterate lists forward. Since cursor refers to the node that immediately precedes the next value, it must refer to the node last returned by next. Hence, we can implement set by setting the data field of cursor.

Implement set, using your approach or this approach (or both, if they are the same).

f. Rerun the experiment to see if the approach you selected works.

You'll note that the previous method and the hasPrevious method are not implemented.

a. Add the following line to your experiments.

    SimpleListExpt.prevExpt(pen, new SimpleLinkedList<String>());

b. Read through SimpleListExpt.java to see how prevExpt exercises the previous and hasPrevious.

c. Sketch a strategy for implementing previous and hasPrevious.

d. Here's one strategy: To find the previous element, start at the front of the list and move forward until you're immediately before the cursor. You have a previous element if you're not the front of the list.

What do you think about this strategy?

e. Implement previous and hasPrevious using one those strategies.

f. Check whether the methods work by using the experiment from the beginning of this problem.

When we first implemented set, we assumed that it only had to work if we iterated the list from front to back. Now we can iterate the list in both directions.

a. Look at SimpleListExpt.setBackwardsExpt to see one way to exercise set while iterating the list from back to front.

b. What do you expect the results of the following experiment to be?

    SimpleListExpt.addToEnd(pen, vm, 
            new String[] { "Days", "When", "The", "Rain", "Came" });
    SimpleListExpt.setBackwardExpt(pen, vm);

c. Check your answer experimentally.

d. If the experiment suggests that set is no longer implemented correctly, find a way to make it work correctly. Hint: One strategy is to add a field to the iterator that refers to the last node visited.