Albany Programming Course Supplement

Graduated Series of Examples 1

Example 1: Fill in the code to complete the program below. (Inserting and deleting at the beginning of a singly linked list.)

class procrastinationProgram
{
  public static void main(String[] jokerVariable)
  {
    procrastinatorsToDoList myList =
      new procrastinatorsToDoList();
    myList.runUserInterface();
  }
}

class itemNode
{
  private String description;
  private itemNode next;
  public itemNode(String str)
  {
    description = str;
    next = null;
  }
  public void setNext( itemNode node )
  {
    next = node;
  }
  public itemNode getNext()
  {
    return next;
  }
  public String getDescription()
  {
    return description;
  }
}

import java.util.Scanner;
class procrastinatorsToDoList
{
  private itemNode top;
  private itemNode end;

  /**
   * Inserts a node referencing the given String at the beginning of the list.
   * @param desc The String to be referenced by the inserted node.
   */
  private void addItem(String desc)
  {
    itemNode temp = new itemNode( desc );
    /*** QUESTION Q1: You write the code! *****/






    /******************************************/
  }

  /**
   * On a nonempty list, prints the description from the first node and removes
   * that node.  Prints a fixed message if the list is empty.
   */
  private void doAndRemoveTop()
  {
    if(top == null)
      System.out.println("Nothing to do.");
    else
    {
      System.out.println("Do this NOW:");
      System.out.println(top.getDescription());
      System.out.println();
      /*** QUESTION Q2: You write the code! *****/






      /*******************************************/
    }
  }

 /**
  * Prints the descriptions from the whole list in order
  * from beginning to end, plus fixed text explanations.
  */
  private void printWholeList()
  {
    itemNode finger = top;
    if(finger == null)
      System.out.println("No more tasks. You can sleep.");
    else
      System.out.println("Here is your list. Work HARD!!");
/*** This is the standard pattern for processing each element in a linked list ***/
    while(finger != null)
    {
      System.out.println(finger.getDescription());
      finger = finger.getNext();
/**********************************************************************/
    }
  }
  /**
   * Prints the description from the last list item if any.
   * If none, a fixed text explanation is printed.
   */
  private void printLast()
  {
    if(end == null)
      System.out.println("No tasks, so no last one. You can sleep!");
    else
      System.out.println(end.getDescription());
  }
  /**
   * Interacts with the user to get a description and then
   * adds it to the beginning of the list.
   */
  private void addItemFromUser()
  {
    Scanner sc = new Scanner(System.in);
    System.out.println("Describe the new task in one line:");
    addItem(sc.nextLine());
  }
  /**
   * Call this method to get the list to interact
   * with the user.  Note that the default constructor is
   * used. (The Java rules take care of properly initializing
   * a procrastinatorsToDoList object.)
   */
  public void runUserInterface()
  {
    Scanner sc = new Scanner(System.in);
    System.out.println("Procrastinator's To Do List.");
    boolean running = true;
    while( running )
    {
      System.out.println("Your wish: addTask doTask whatsLast stop ? ");
      String wish = sc.next();

      if( wish.equals("addTask") )
        addItemFromUser();
      else if( wish.equals("doTask") )
        doAndRemoveTop();
      else if( wish.equals("whatsLast") )
        printLast();
      else if( wish.equals( "stop" ) )
        running = false;
      else
        System.out.println("Computer didn't recognize your wish.");

      if(running)
        printWholeList();
    }
  }
}

Answers:

Q1:

  private void addItem(String desc)
  {
    itemNode temp = new itemNode( desc );
    //You write!!
    temp.setNext(top);
    top = temp;
    if(end == null)
      end = temp;
  }

Q2:

  private void addItem(String desc)
  {
    itemNode temp = new itemNode( desc );
    //You write!!
    temp.setNext(top);
    top = temp;
    if(end == null)
      end = temp;
  }

Example 2: To the procrastinatorsToDoList class, add a method that inserts an item at the end of the list. Specifically, fill in the blank area below:

/**
   * Inserts a node referencing the given String at the end of the list.
   * @param desc The String to be referenced by the inserted node.
   */
  private void addItemAtEnd(String desc)
  {
    itemNode temp = new itemNode( desc );
    /*** QUESTION Q3: You write the code! *****/






    /******************************************/
  }

Also, (very important) enhance the user interface so the new feature can be tested.

Answer: To be supplied..

Example 3: Add the capacity to edit the list

(Pedagogical notes: Solving the problem to implement a cursor that functions in a familiar way exposes the beginner to quite a few of the kind of detail problems that programmers solve routinely. This example might be preceded by lessons and exercises in implementing the standard mid-list insert and delete operations, however it is not sufficient to leave the topic of the singly-linked list data structure without a homework assignment whose complexity is comparable to this example.

In our course, this assignment is in a series in which first an array of Pictures is the subject, and the main objective of the preceding assignment is to learn to process a sequence of things like Pictures in order to do things like calculate their total width, the maximum of their heights, and to copy each Picture into a calculated region in a composite Picture.)

To complete this example, you will have to implement methods to insert and to delete a node from a linked list given a pointer to the node preceding the point of insertion or deletion. Also, the special case of inserting or deleting at the beginning of the list, and when the list has only one element, has to be accommodated. Since this is covered in every data structures textbook it will be omitted here (at least for now).

You need to add to the procrastinatorsToDoList class two more instance variables
(besides top and end): One to implement the cursor and the other to implement a "copy buffer''. When one description String is copied or cut, that String is kept available by having its location stored in the copy buffer instance variable so that it can be pasted one or more times into various list positions. As in familiar word processing software or text editors like emacs and nano, when a new copy or cut operation is commanded, the old String in the copy buffer is replaced by the one that was just copied or cut. To clarify further, cut and copy do the same thing with putting the description String at the cursor into the copy buffer; the difference is that the cut command also deletes it from the list.

After the initial list is built from user input, the user must be prompted as below to type one of the commands as shown:

Command: home forward copy paste cut done ?

Notice that paste and cut are the only commands that can actually change the sequence of description Strings in the list.

Whenever the sequence changes, the program must display the changed list.

There are three troublesome details ¹ and solving the problems caused by them
is part of the assignment. They might be discussed in your class. It is a good idea to discuss solution strategies with your classmates. However, if you just copy an answer figured out by somebody else, you will not become able to reproduce answers to similar problems at a future time (like an exam) when the answer is not available.

At the beginning, and until the first cut or copy command has been successfully performed, there is no description String in the copy buffer to paste. Your implementation of the paste command must detect that situation, not crash, print a friendly and informative message, and continue handling new commands.
Suppose the list has say 3 items. There are then 4 positions for the cursor! When the cursor is at the beginning of the list, the description String to be cut or copied lies just to its right. That one is the first String in the list. When a description String is pasted at the beginning, it becomes the first and all the Strings already in the list move forward one spot.
Of course, no real "moving'' is done. The values of top and some next variables are changed to implement changing the order of the Strings.)
When the cursor is between two description Strings in the list, copying and cutting apply to the String to its right. Pasting will make that String to the right of the cursor "move one spot right'' to make room for the copy pasted in!
When the cursor is at the end of the list, there is no String to cut or copy.
Your implementations of cut and copy must detect that situation, not crash, keep the original contents of the copy buffer (if any!), print a friendly and informative message, and make the program continue to handle new commands.
The paste command given when the cursor is at the end of the list causes the String in the cut buffer to be copied to the end of the list, so the previous Strings remain in place.
(Clearly, 3 is just an example of a number. The program MUST work properly for ANY number of description Strings. Also, the same String might be in the list several times because of pasting.)
The list might become empty. The program must continue to work. In that case, the user can command paste one or more times and so see one or more of the same String.

(The answer is not supplied so this problem can be assigned as a programming project.)

Example 4: Modify the program so that when the list is displayed, the position of the cursor is indicated. Make it redisplay the list both when the cursor is moved (by the forward operation) as well as, like before, the contents of the list changes.

Example 5: Implement the operation to move the cursor backward efficiently by making the list be doubly linked.

(Pedagogical note: A project to extend operations on singly linked lists to doubly linked lists is excellent practice before moving on from lists to non-linear data structures.

Terminology that might be on an exam or a job interview: Software designers call individual detailed situations in using a program separate use cases. Part of their job is to explicitly write out use cases. With the use cases written out, it is easier to design what the program should do in each case, and then check that the proposed design and eventually the code will actually do it. WEB SITE designers TOO!^{^}