Welcome to Week 2 - Lesson 3!

Learning Objectives

By the end of today's class, you should know...

  • What is the best method for handling the violation of preconditions in your methods?
  • What is an iterator?
  • How does the iterator traverse the List?
  • What does it mean for the iterator to be "off end"?
  • How do you access data from the middle of the List using an iterator?
  • How do you insert and remove data from the middle of the List using an iterator?


1. Proper Handling of Preconditions

  • Recall that preconditions specify what conditions must exist for a method to be executed
  • In our List class, several access and mutator methods had preconditions.
  • For example, if the List is empty, the getFirst method cannot return a value for the data stored at the first node.
  • Thus, the precondition for getFirst is that the List not be empty
     /**
     * Returns the value stored in the first node
     * @precondition length != 0
     * @return the integer value stored at node first
     * @throws NoSuchElementException when the precondition is violated
     */

       public int getFirst() throws
NoSuchElementException{
        if (length == 0) {
            throw new
NoSuchElementException("getFirst: "
                    + "List is Empty. No data to access!");
        }
        return first.data;
    }
  • But, what should be done when the precondition is violated?
  • As we saw in Lab 1, throwing an exception is the best approach to this problem.
  • But, why?
  • Let's examine two alternate approaches.
Option 1: Alert the user to this situation, by printing an error message
  • For example, for the getFirst() method:

if (isEmpty())
    System.err.println("getFirst(): List is empty. "
            + "No first element.");

  • Thus, the method would now be written as follows:
public int getFirst()
{
    if (isEmpty()) {
        System.err.println("getFirst(): List is empty. "
            + "No first element.");
        //What is wrong with this approach???
    
    } else {
            return first.data;
        }
    }
  • If we write the method as above, the compiler should complain to us. Why?
    • If the precondition is not met, the method will not return a value.
    • There is no return statement inside the if
    • This method MUST return a value in either case (if or else).


Option 2: Return a Dummy Value

  • One approach to solve the above problem is to return a dummy value such as -1.

public int getFirst()
{
    if (isEmpty()) {
        System.err.println("getFirst(): List is empty. "
            + "No first element.");
        return -1;
        //What is wrong with this approach???
    
    } else {
            return first.data;
        }
    }
  • Why might the above approach be a poor one?
    • -1 could be a possible value contained in the List
    • There is no suitable dummy value for a list of integers


Option 3: Throw an Exception - and Catch It!

  • The best approach to handling preconditions for your methods is to use Exception Handling.
  • Recall that an exception is a problem that occurs during the execution of a program, leading to a disruption of the normal flow of the program.
  • When you throw an exception, you are passing a message to the calling method telling it that a problem has occurred.
  • The program will immediately halt, and an error message will be displayed.
  • For example, the following error message appears on the console when the precondition of getFirst() is violated, leading to the method throwing an exception.

  • When you throw an exception, it is important that you provide a detailed message notifying the user why the problem occurred.
  • For example, when throwing the exception below, we are careful to indicate why the exception was thrown, and from which method it originated.
    /**
     * Returns the value stored in the first node
     * @precondition
     * @return the integer value stored at node first
     * @throws NoSuchElementException when the precondition is violated
     */
    public int getFirst() throws NoSuchElementException{
        if (length == 0) {
            throw new NoSuchElementException("getFirst(): "
                + "List is empty. No first element!");
        }
        return first.data;
    }

  • The above error message is specific enough to allow the user to track down the source of the problem.
  • In contrast, the below error message is too general to be useful:

  • In testing your code, you will want to call your methods in violation of the preconditions to ensure that the exception is thrown correctly.
  • However, it can be annoying to have the program halt each time you test the preconditions of your methods.
  • Instead, you can place the method calls that you know will trigger an exception inside of a try-catch block.
  • The try-catch block instructs the calling method as to how to handle the error when it occurs and then move on without halting.
  • For example, we might call removeFirst() inside the below try-catch block:
    try {
      L.getFirst();
  } catch(NoSuchElementException e) {
      System.out.println(e.getMessage());
  }
  • The above will display the error message to the console, but the program will be able to continue:

  • For more information on exception handling and catch exceptions, read Appendix C in the course textbook.


2. The List Iterator

  • So far, the List class we have written has not been very functional.
  • We have only been able to insert data at the beginning and end of the List, but not in the middle.
  • We have only been able to access data at the beginning and end of the List, but not in the middle.
  • We need an iterator!


2.1. Iterators

  • An iterator is a special pointer used to traverse a container.
  • In the List class, an iterator is a special Node object that allows us to traverse the Nodes in the List.
  • The List iterator can move from one Node to the next in the List.
  • It can thus be used to access data in the middle of the List or insert and remove data in the middle of the List.
  • The List iterator will be useful not only to us as the programmers, but to the users of our List class who want to access or modify data in the middle of the List.
  • Therefore, we need to write special methods to define the behavior of the iterator.


2.2. The List Iterator and Its Methods

  • Let's add to our class definition to include an iterator as one fields of the list class.
    public class List {
        private class Node {
            private int data;
            private Node next;
        
            public Node(int data) {
                this.data = data;
                this.next = null;
            }
        } //end of clas Node
    
        private int length;
        private Node first;
        private Node last;
        private Node iterator;
        //rest of class List
    } //end of class List
  • We then initialized it to be NULL inside of the default constructor
    /**
     * Instantiates a new List with default values
     * @postcondition a new List object
     */
    public List() {
        length = 0;
        first = null;
        last = null;
        iterator = null;
    }
  • Notice that the iterator is just a reference to a Node. We will be moving this pointer around the List, which will allow us to access and manipulate the interior nodes.
  • We will need methods to define the behavior of the iterator (its operations).
  • These methods are as follows:
  • pointIterator: moves the iterator to the beginning of the list
  • removeIterator: removes the element currently pointed to by the iterator
  • getIterator: returns the element currently pointed at by the iterator
  • addIterator: inserts an element after the node currently pointed at by the iterator
  • advanceIterator: moves the iterator up by one node towards the last node
  • offEnd: returns whether the iterator is off the end of the list, i.e. pointing to null

2.3. Writing the pointIterator Method
  • After the List constructor is called, the iterator is defined as being "off the end of the List" (i.e. pointing to NULL).


In the above image, the iterator is considered to be "off the end" of the List.

  • As we add and remove elements in our list using methods such as addFirst or addLast, the position of the iterator should NOT change.
  • In fact, the ONLY way that the iterator should "move onto" the List (i.e. point at a Node in the List), is when a call is made to the pointIterator method.
  • The purpose of the pointIterator method is to make the iterator point to the first node of the List.
  • The user can call this method whenever he or she wishes to return the iterator to the beginning of the List or place the iterator onto the List.
  •  It is implemented as follows:
public void pointIterator()
{
    iterator = first;
}

  • We can visualize the effect of this method with the below diagram (compared to the diagram above).

2.4. Reflection:
  • How would you write the following 3 methods:
    • getIterator: returns the element currently pointed at by the iterator
    • advanceIterator: advances the iterator by one node in the List
    • offEnd: returns whether or not the iterator is off the end of the List, i.e. null
  • Which of the above 2 methods have preconditions?
    • What are the preconditions and why?


3. Adding and Removing Using the Iterator

3.1. Mutator: addIterator

  • The addIterator method adds a Node following the one currently being pointed to by the iterator.
  • It can be used to insert new Nodes at any position in the list.
  • You can visualize the addIterator operation with the following diagram:

  • When the user calls the addIterator method, a new Node is inserted AFTER the iterator.
  • We must update the new Node's next field to point to the iterator.next.
  • Then, we must update the iterator.next to point to the new node.
Another depiction of addIterator:


Singly linked list insert after.png

Image source.
  • When writing this method, there is an edge cases that we must consider:
    • The iterator is currently pointing to the last<-- Why is this an edge case?
  • There is also a precondition that the iterator must not be off the end of the list.
    <-- Why is this a precondition?
    • We can call the offEnd method to test for this precondition!
  • Here is the pseudocode for this method:
  1. If the iterator is offEnd <-- this is a precondition
    1. throw an exception
  2. If the iterator is pointing to the last node
    1. call addLast
  3. Otherwise
    1. Declare a new Node variable
    2. Update the new node's next pointer to equal the iterator's next
    3. Set the iterator's next to point to the new Node
    4. Increment the length of the List

3.2. Drawing addIterator Precondition:
  • The below situation would cause a violation of the precondition:



3.3. Drawing addIterator Edge Case:
  • On a sheet of paper, draw an image like the one below, and update the pointers to represent the steps of addIterator in the edge case.

3.4. Drawing addIterator General Case:
  • On a sheet of paper, draw an image like the one below, and update the pointers to represent the steps of addIterator in the general case.


3.5. Group Activity: Drawing removeIterator

  • Let's take a moment to draw the removeIterator operation.
  • This is probably the most challenging method you will need to write for the list data structure.
  • I strongly recommend only implementing this method with your doubly-linked list ONLY, as it will be MUCH easier!
  • Drawing this operation will help you when it comes time for you to write the code for removeIterator in your lab.



Important Note:
  • The methods we have discussed are for a singly-linked List class (like Lab 1).
  • You will need to update addIterator and removeIterator for Lab 2, where you are writing a doubly-linked List.



Wrap Up
  • Answer the review questions on Canvas for today's lesson


Upcoming Assignments
  • Study for your Quiz
  • Lab 2 due next Monday at midnight


~Have a Great Day!~