`

Computing Concepts with Java Essentials
Laboratory Notebook
Chapter 16 - An Introduction to Data Structures


Your name:
Your email address:
Your student ID number:

Once this form has been customized for your institution, you can use this button to send your lab work. Be sure to read the instructions before starting your work.


Lab Objectives

To gain experience with


P1. Using Standard Linked Lists

In this exercise, you should use the LinkedList and ListIterator classes of the java.util package.

First, insert ten employee names of your choice into a list called staff. Then print the strings in the list. Next, perform "downsizing" by removing every second employee from the list. Finally, print the remaining staff.


P2. Programming Linked Lists

One very natural operation that is not already a feature of the LinkedList implementation in section 16.2 of the textbook is appending an element to the tail of a list.

Provide a new method addLast(Object obj) for the LinkedList class which will append the object obj to the end of the original list.

For example, if the list a contains Harriet, Jim and Carolyn, and obj is Harry, then the command a.addLast(obj) changes a to contain Harriet, Jim, Carolyn and Harry.

In this exercise, you must start from the program ListTest2.java and directly modify the links of the list. You may not use the list iterator.

First, implement the addLast method in an inefficient way. Find the last link in the list:

if (first != null)
{  Link last = first;
   while (last.next != null)
      last = last.next;
}

Then append a new link.

Link newLink = new Link();
newLink.data = obj;
newLink.next = null;
last.next = newLink;

However, you need to take care of the special case that the list is empty (first == null). In that case, you can simply call addFirst.

Test the addLast method by running the following test program:

public class Test
{  public static void main(String[] args)
   {  LinkedList staff = new LinkedList();
      staff.addLast("Juliet");
      staff.addFirst("Romeo");
      staff.addLast("Tom");
      staff.addFirst("Dick");
      staff.addLast("Harry");
     
      // print all elements
      LinkedList.Iterator iterator 
         = staff.listIterator(); 
      while (iterator.hasNext())
         System.out.println(iterator.next());
   }
}

Now, reimplement the addLast method in a more efficient way. Add an instance variable last to the LinkedList class:

class LinkedList
{  // . . .
   private Link first;
   private Link last;
}

Ensure that the last reference always points to the last link in the list. (That's harder to do than it sounds--see below). Now the addLast method becomes very simple:

void addLast(Object obj)
{  Link newLink = new Link();
   newLink.data = obj;
   newLink.next = null;
   if (last == null) // list is empty
      first = newLink;
   else
      last.next = newLink;
   last = newLink;
}

However, you now must make sure that all mutator methods of the LinkedList and Iterator class that happen to affect the last element update the last reference.

There are five methods that you need to consider:

Implement this improvement of the addLast method.


P3. Binary Search Trees

Consider the following Point class (which is different from java.awt.Point):

class Point implements Comparable
{  public Point(int aX, int aY)
   {  x = aX;
      y = aY;
   }
   public int getX()
   {  return x;
   }
   public int getY()
   {  return y;
   }
   public int compareTo(Object other)
   {  Point b = (Point)other;
      return x - b.x;
   }
   private int x;
   private int y;

}

Note that "less than" means simply that the x-coordinate of one node is less than that of the other node. .

In this example, we store Point objects into an object of the Tree class described in section 16.3. The nodes of this tree store objects of type Point.

Explain which nodes are visited to insert the point (70,60) in the following tree. Draw the resulting tree.


                           (50,0)
                         /       \
                   (30,20)         (120,20)
                  /      \          /    \     
              (20,40)   (60,40) (110,40)  (130,40)

The main method of the following example inserts a number of points into a tree. Add a draw function to the Tree class (which calls a drawNnode function of the Node class) that draws each node of the tree as follows:

{short description of image}

Here is a test program.

public class PointTreeTest extends JApplet
{  public void paint(Graphics g)
   {  Graphics2D g2 = (Graphics2D)g;
      Tree t = new Tree();

      t.insert(new Point(50,40));
      t.insert(new Point(30,30));
      t.insert(new Point(20,20));
      t.insert(new Point(10,10));
      t.insert(new Point(40,20));
      t.insert(new Point(70,30));
      t.insert(new Point(60,20));
      t.insert(new Point(80,20));
      t.draw(g2);
   }
}

You need to supply the drawNode and draw methods of the Node and Tree classes.


Don't forget to send your answers when you're finished.