1. Dynamic data structures

Computers are frequently used to store and manipulate lists of data. There are many ways to represent a list in a computer. The choice of how best to represent a list is based on how the list will be manipulated. Will items be added at the top of the list, at the bottom, or somewhere in the middle? Will the items in the list be in some particular order such as alphabetical? Which will be more common: searching for an item in the list, or inserting a new item in the list? There are many more such questions to consider when deciding on how to implement a list. For the most part these are questions for an advanced text on data structures. In this chapter, we describe some basic ways of representing lists.

One way to represent a list is with an array. The single most important difference between arrays, and the list implementations we will describe in this chapter, is that the capacity of an array cannot change. If you need to change the size of a list implemented as an array, you will need to create a new array, larger or smaller, and then copy the items from the old array to the new, resized array. Because of their ability to be easily resized, the data structures we describe in this chapter are called dynamic data structures .

A second important characteristic of the data structures used to implement lists in this chapter, is that they contain, as a member, a reference variable of the same type as the class itself. For this reason, these data structures are frequently called self-referential or recursive data structures .

Self-referential structures

The simplest type of self-referential list structure is a sequence of elements. Each element contains some data, and a reference, often called a pointer, to the next element in the list. We can do that in Java as shown in the following example which will allow us to create an arbitrarily long list of integer values.

class IntListElement{
   IntListElement(int value){data = value;}
   IntListElement next; //self-referential
   int data;
}

This declaration of IntListElement has two fields. The field data stores the data member for this element. The reference variable next is called a link . Each element is linked to a succeeding element by way of the member next . For convenience, we also include a constructor that fills in the data field. A list, implemented with this structure, can be conveniently displayed pictorially with links shown as arrows. In the following figure the field data contains the value 2. The field next is pointing to some other, unspecified element.

 

If there is no succeeding element because we are at the end of the list, the field next will contain the special value null . We can create two elements with the following:

IntListElement first = new IntListElement(1);
IntListElement second = new IntListElement(2);

The next field defaults to null . Pictorially, the result of this code is the following:

 

To make these two elements into a list, with first as the first element in the list, we link them together.

first.next = second;

The picture now looks like this.

 

The links allow us to retrieve data from successive elements, beginning with the first element. Thus

first.next.data

has the value 2 .

Common programming error

A common mistake is to attempt to access a field or method for an object using a reference value that is null . This generates a NullPointerException . For example, given the short list created above, attempting to reference first.next.next.data would generate a NullPointerException . The expression first.next.next refers to the reference value stored in the field next of the second element in the list. This field is null , so first.next.next.data is asking for the field data of the null value.

In some cases it is acceptable to let the program abort with the exception. In other cases it may be appropriate to use the mechanism for handling exceptions, to catch the exception and take some corrective action. Yet another approach is to test for a null reference before accessing any fields. Better still is to design the program so that such null references can never occur.

A linked list implementation of a stack

We have already discussed arrays which are a type of container. That is, an array contains a sequence of values of the same type. Another very common container used in computers is a stack . A stack, like an array, stores a sequence of similar objects. The difference between stacks and arrays lies in how you put values into the container. In an array, you create the container with a fixed size and then store and retrieve values at any index in the array. A stack is like a stack of plates. You can add a plate to the top of the stack, you can look at the plate on the top of the stack, and you can remove a plate from the top of the stack. You cannot look at, add, or remove plates from the middle.

A stack class for storing integers should have the following methods:

class IntStack {
  int top() { ... };
  void push(int value) { ... };
  int pop() { ... }
  boolean empty() { ... }
}

The method top() returns the value of the integer on the top of the stack without changing the contents of the stack. If the stack is empty, it returns a 0. The method push() pushes an integer value onto the top of the stack, increasing the number of integers contained in the stack. The method pop() returns the same thing as top() but it also removes the top value from the stack, reducing the number of integers contained in the stack by one. If the stack is empty, pop() returns 0 and the stack is unchanged. The method empty() returns true if the stack is empty and false otherwise. The following figure shows the integers 1, 2, 3 being pushed onto a stack and then popped back off.

 

There are many ways to implement the operations of the class IntStack . An important aspect of Java, and other object oriented languages, is the language syntax that allows you to hide and change the implementation without affecting other parts of a program that use the class. Here we will implement the class IntStack using the IntListElement class introduced above.

//IntStack.java - a stack implemented with a list
class IntStack
{
  int top()
  {
    if(top != null)
      return top.data;
    else
      return 0;
  }

  void push(int value)
  {
     if(top == null){
       top = new IntListElement(value);
     }
     else {
        IntListElement temp= new IntListElement(value);
       temp.next = top;
       top = temp;
     }
  }

  int pop()
  {  
    int result = top();;
    if(top != null)
      top = top.next;
    return result;
  }
  boolean empty(){ return top == null; }
  private IntListElement top = null;
}

Dissection of IntStack (implemented with IntListElement)

The private instance variable top is a reference to the IntListElement at the top of the stack. If the stack is empty, top equals null and the result of top() is 0 . Otherwise, the result of top() is the data field for the element referred to by top . Notice that Java allows a variable and a method to have the same name.

We must check for the special case of pushing onto an empty list, in which case we simply set top to be a new element. If the stack is not empty, we create a new element, set its link to point to the current top of the stack and then move top to point to the new element. In both cases, we then store the new value into the data field of the new top element. The figure below shows the sequence of inserting an element into a non-empty stack. In the figure, 1 and 2 have been previously pushed onto the stack and we are now executing, push(3) .

 

We reuse the method top() to find the value that should be returned from pop() . By reusing our code in this way, we reduce the chances of making a mistake. If the stack is not already empty, we move top to point to the next element in the list, thus removing what was the top element from the stack. It is important that we save the result before moving top , otherwise we wouldn't be able to find the value to return.

The method empty() is straightforward, returning true if the stack is empty. The only instance variable is the pointer to the top element. Notice the absence of any specification of how big the stack will be.

A singly linked list

A stack is a specialized list. It only permits insertion and removal of elements from one end of the list, called the top. In this section we will look at a more general list class that implements a singly linked list. This class will allow for insertion, removal and examination of elements at any point in the list. We could just use the IntListElement class in each program that used lists. This would require us to repeatedly recode the error prone operations of connecting and disconnecting links. Instead, we will create a class that does this for us.

With our stack, we always knew where an insertion or removal was going to take place, namely at the top. With a general linked list, we will need some way to specify where the insertion or removal should be performed. We will do this by having a variable called current , that refers to an arbitrary element in the list. We will then be able to move current from one element to the next. Here is a specification of our class, without any method bodies.

class IntList {

  void insert(int value)
  /* Insert after the element referred to by current
   * and move current to the new element.
   * If current does not refer to any element,
   * then insert at the head and move current to the
   * new element.
   */

  int next()
  /* Advance current to the next element and return
   * that element. If there is no next element or the
   * list is empty, throw an exception. If current
   * does not refer to any element on entry to this
   * method, then the first element in the list is
   * returned and current is set to the first element.
   */

  int current()
  /* Return the current element. If the list is empty
   * or there is no current element, throw an
   * exception. Initially current does not refer to
   * any element.
   */

  void remove()
  /* Remove the current element advancing current to
   * the next element. If there is no next element,
   * which happens when removing the last element,
   * set current to not refer to any element. This
   * is equivalent to moveToHead().
   * If current is does not refer to any element on
   * entry, remove() does nothing.
   */

  void moveToHead()
  /* Set current to not refer to any element, which is
   * interpreted to mean before the first element.
   * A subsequent call to next() will return the
   * first element.
   */

  boolean hasNext()
  /* Returns true if current is not the last element in
   * the list. This is intended to be used in
   * conjunction with next() to loop through a
   * list, examining each element.
   * Note that this is not telling us if the list is
   * empty, but rather whether a subsequent call to
   * next() will succeed without causing an
   * exception.
   */
}

Before looking at an implementation of this class, let's look at some code that uses the class.

//IntListTest.java
class IntListTest{
  public static void main(String[] args)
  {
    IntList list = new IntList();
    // insert the integers 1 through 10 in the list
    for(int i=1; i<=10; ++i)
      list.insert(i);
    // print the list
    list.moveToHead();
    while(list.hasNext())
      System.out.println(list.next());

    // try an insertion and a deletion
    list.moveToHead();
    list.next(); // current is 1
    list.next();  // current is 2
    list.insert(25); // insert 25 between 2 and 3
    list.next(); // current is 3
    list.remove(); // remove 3

    // print the list again
    list.moveToHead();
    while(list.hasNext())
      System.out.println(list.next());
  }
}

The output of this code fragment will be to print 1 through 10 then print 1 through 10 with 3 replaced by 25. We use next() both to retrieve a particular element and to advance current . If we aren't concerned about the current element we can simply ignore the value returned by next() . Notice that the IntListTest code sample does not use IntListElement . The code is independent of how IntList is implemented. It could be implemented with an array (see excercise See Write a class that implements the same methods as IntList, but represent the list as an array of integers. Add a constructor that allows the programmer to specify the maximum size of the list. Use this to set the size of the internal array. ), with a list built out of IntListElement s as we will do below, or it could be implemented using some other class.

Due to the length of IntList , we will present only the dissection, not the complete listing.

Dissection of IntList

There are three instance variables. The variable head will always refer to the first element in the list or be null if the list is empty. The variable current can refer to any element in the list. If current is null , then it is assumed to be pointing before the first element. In this way, insert() always inserts after current . The variable previous always points to the element before current . It is needed to simplify removal of elements. If current is pointing to the first element then previous will be null .

As you can see, inserting in a list is much more complicated than pushing onto a stack. The variable previous is always set to current because current will move forward to the new element. There are three cases, current is pointing to some element in the list, current is not pointing to any element but the list is not empty, and the list is empty. The last case is easy, point head and current at the new element. The middle case causes a new element to be inserted before the current first element. The following figure shows an example of the middle case. The top portion shows the list if we took the initial list of ten elements created by the first loop in IntListTest and then did list.moveToHead() . The bottom shows the result of subsequently executing listInsert(99) .

The remaining case is the general case when an element is inserted after an existing element. The following figure shows the insertion of 25 between 2 and 3 as done by IntListTest . The comments //step 1 etc. in the code above correspond to the similar labels on the arrows in the figure below.

 

If current is null then the "next" element is the first element in the list. If current is null at the return statement, a NullPointerException will be thrown automatically. A better solution is to test for this situation and throw a NoSuchElementException . See excercise See Modify the method next() in class IntList to throw a NoSuchElementException if there is no next element. The syntax for throwing the exception is .

Simply return the value of the field data for the element pointed to by current . If current is null this will throw a NullPointerException automatically. As with next() , a better solution would be to throw a NoSuchElementException .

There are four cases for removal: the list is empty, no element is selected, the first element is selected, and some element other than the first is selected. Only the last two actually remove an element. Removing the first element is special because we also need to adjust head to point to whatever follows what was the first element. Removing an element other than the first element uses previous to link the element prior to the removed element to the element that followed the removed element.

These two short methods complete our implementation of IntList . There are two cases for hasNext() . If current is null then the next element is the first element if there is one. We therefore test to see if the list is empty. If current is not null , then the next element is whatever comes after current . In this case we test that the next field of current is not null .

More operations on lists

In the previous section, we described a class IntList that supported arbitrary insertion and removal. We implemented only the minimal set of operations. There are many more common operations on lists and it would be wise to implement them once in our list class so that we can use those operations in other programs. Here is a list of typical operations. For completeness we include the ones already implemented.

Linear List Operations
  • Create an empty list.
  • Insert after the current position.
  • Insert before the current position.
  • Insert at position n in the list. Zero means insert before the first element.
  • Remove the element at the current position.
  • Find an element in the list.
  • Append the elements of one list onto the elements of another list.
  • Count the elements in a list.
  • Retrieve the current element.
  • Move the current position forward.
  • Move the current position backward.
  • Move to the head of the list.
  • Move to the end of the list.
  • Print a list.
Implementing toString() for IntList

Some list operations are easier to implement than others. A simple, but useful one is printing a list. We did this in our examples. By creating a method to print the list, our programming task becomes simpler. The preferred approach in Java is to create a method toString() which returns a String representation that can then be printed. Here is a simple implementation of toString() .

  //excerpt from IntList.java
  public String toString()
  {
    IntListElement cursor = head;
    StringBuffer result = new StringBuffer();
    while(cursor != null){
      result.append(cursor.data + "\n");
      cursor = cursor.next;
    }
    //Convert the final StringBuffer to a String using
    //method toString() from class StringBuffer.
    return result.toString();
  }

The class String is implicitly derived from the class Object , as are all classes except the class Object itself. Because the method toString() is defined as a public method in Object , the method, when redefined in other classes, must also be public, hence the keyword public in the above definition. This was discussed in Chapter See Inheritance .

When working with lists, it is often convenient to write recursive methods. We can easily write a method that recursively calls itself to generate a string representation of a list given a reference to the first element in the list.

String toStringRecursive(IntListElement first)
{
  if(first == null)
    return "";
  else
    return (first.data+"\n")+
     toStringRecursive(first.next);
}

Using this method, toString() in class IntList can be implemented as:

public String toString()
{
  return toStringRecursive( head );
}

Notice that there are no local variables in either of these last two methods. The result is built in the stack of method calls. Suppose the list contains the elements 10, 20 and 30, in that order. Then a call to toString() would result in the following sequence of calls.

 

Notice how the result is built up in reverse order as the method calls return.

doubly linked lists

Implementing the "move current position backwards" operation would be rather difficult using our IntList class and the IntListElement . In order to move backwards, it would be necessary to move back to the beginning and then move forward again, stopping when current reached what used to be the previous element. To solve this problem, we can create a new list element class that contains two links, one pointing to the next element, and one pointing to the previous element. Such a list is called a double linked list . Here is our new list element.

class IntDListElement {
  IntDListElement(int value){ data = value;}
  IntDListElement next;
  IntDListElement previous;
  int data;
}

We can create a list of three elements with the following:

    IntDListElement first = new IntDListElement(1);
    IntDListElement second = new IntDListElement(2);
    IntDListElement third = new IntDListElement(3);
    first.next = second;
    second.previous = first;
    second.next = third;
    third.previous = second;

Pictorially, this would result in the following structure.

 

We leave it as an excercise to utilize this doubly linked element in a doubly linked list class that supports moving backwards as well as forwards through the list.

A generic stack

The list and stack classes that we implemented above only work with integers. What if you wanted to store strings or other objects on a stack? One solution would be to create different classes for each type. This is cumbersome and unnecessary. Java supports polymorphism, which means we can create one class that will handle all different types. The changes to our previous classes are minor. Let's start with a generic list element.

class ListElement {
  ListElement(Object value)
  {
    data = value;
  }
  ListElement next;
  Object data;
}

We have replaced int with Object . The class Object is a standard Java class and a reference of type Object can refer to any non-primitive type. In order to store primitive type values in our generic ListElement , we will need to use some additional standard Java classes that turn primitive types into reference types. There is one such class for each primitive type. Except for Integer which corresponds to the primitive type int , the names of the classes are the same as the primitive types except the first letter is capitalized. For example, new Integer(3) , is a non-primitive value that corresponds to the primitive value 3. To create a ListElement storing the value 3 we can use the following:

ListElement elem1 = new ListElement(new Integer(3));

Similarly, we could create a ListElement containing the float value 1.25 with:

ListElement elem2 = new ListElement(new Float(1.25f));

Strings do not require any special handling because they are already reference types. Here is a ListElement containing a String :

ListElement elem3 = new ListElement("element 3");

In order to retrieve the data from the elements, the program using the data will need to know what type of value is really there. Provided the programmer knows the true type, then a cast can be used to convert from Object back to the true type (see Section See The instanceof operator and casting non-primitive types ). For example, if the list only contains Float values, then the following expression could be used to retrieve a value:

Float f_value = (Float)elem2.data;

To recover a primitive float value from its Float class counterpart, use:

float value = f_value.floatValue();

The other primitive types are similar, making the obvious substitution for float in floatValue() . If you do not know what type of value is stored in a ListElement , Java provides the operator instanceof that can be used to test the type. We discussed instanceof in Section See The instanceof operator and casting non-primitive types .

Now that we have a generic list element, we can use this to create a generic list or a generic stack. We will make the change for the stack and leave the changes for the list as an excercise. In the following code, the changes are in boldface. All occurences of int have been replaced by Object and all occurences of IntListElement have been replaced by ListElement . The only other change was the name of the class from IntStack to Stack .

//GenericStack.java
class Stack
{  
  Object top()
  {
    if(top != null)
      return top.data;
    else
      return null;
  }

  void push(Object value)
  {
     if(top == null){
       top = new ListElement(value);
     }
     else {
       ListElement temp = new ListElement(value);
       temp.next = top;
       top = temp;
     }
  }

  Object pop()
  {  
    Object result = top();;
    if(top != null)
      top = top.next;
    return result;
  }

  boolean empty(){ return top == null; }

  private ListElement top = null;
}

Here is a program using the new stack to store double floating point values.

//GenericStackTest.java
class GenericStackTest{
  public static void main(String[] args)
  {
    Stack stack = new Stack();

    stack.push(new Double(1.111));
    stack.push(new Double(2.222));
    stack.push(new Double(3.333));
    while(!stack.empty()){
      double temp =
                ((Double)stack.pop()).doubleValue();
      System.out.println(temp);
    }
  }
}

It was not necessary to first store the popped value in temp . We did this to show how to convert the popped value to an object of type Double . The same output would be obtained if the body of the loop was simply,

System.out.println(stack.pop());

The output of this example is

3.333
2.222
1.111

Common programming error

When implementing linked list data structures, great care must be taken to assure that proper linked lists are always created. For example, it is possible to create a circularly linked list that has no beginning or end. This is fine, if that was intended; but if the intent was a linear linked list, then operations such as hasNext() may never return false. Then an innocent loop such as

while(list.hasNext()){
    ... = list.next();
    ...
}

becomes an infinite loop.

One good defense against such errors is the use of assertions, formal or informal. A formal assertion is one that you actually place in the code to be checked. If the assertion fails, an exception can be thrown. An informal assertion can be in the form of a comment that should be checked by the implementor of the method.

An example of an assertion on the insert method for a list might be, "the next field for the last element in the list is null." As discussed in Section xxx, just the process of thinking about what assertions you might write can result in better code. For example, in writing the assertion that the last element in the list is null, hopefully you would realize that you need to make sure that the first element inserted in an empty list, and an element inserted at the end of a list must have their next fields set to null.

Another way to avoid problems resulting from errors in implementing your own list class is to use an existing list class that has been thorougly debugged. Beginning with JDK1.2, standard Java includes an extensive collection of classes for handling lists, stacks and related structures. These can be found in the package, java.util . For example there is a class java.util.LinkedList . In addition there is a widely used library called the Java Generic Library from Objectspace. The package is officially called Com.objectspace.jgl . This package is included in several Java development environments and can be obtained for free from the Internet at http://www.objectspace.com/jgl/ .

Another, simpler option is to use the class Vector from the package java.util , that is part of the standard Java distribution (including JDK1.1). Although probably not implemented as a linked list, the class Vector supports essentially the same methods as found in the list classes discussed above. For example, you can insert an element at an aribitrary point, or remove an arbitrary element. A Vector is more like an array that can be expanded as necessary to accomodate new elements. The following example shows a Vector being created and then one element being inserted in the middle and another removed. This program essentially mimicks the operations of the routine main() used to test the class IntList on See //IntListTest.java class IntListTest{   public static void main(String[] args)   {     IntList list = new IntList();     // insert the integers 1 through 10 in the list     for(int i=1; i<=10; ++i)       list.insert(i);     // print the list     list.moveToHead();     while(list.hasNext())       System.out.println(list.next()); . A Vector can only hold references, not primitive types. Therefore we use the wrapper class Integer , that lets integers be treated as objects.

// VectorTest.java - using Vector as a list
import java.util.*;

class VectorTest {
  public static void main(String[] args)
  {
    Vector list = new Vector();
    for(int i=1; i<=10; ++i)
      list.addElement(new Integer(i));
    System.out.println(list);
    // insert 25 between 2 and 3
    list.insertElementAt(new Integer(25),2);
    list.removeElementAt(3);
    System.out.println(list);
  }
}

The standard Java package, java.util , also includes an implementation of a generic stack.

An example: Polish notation and stack evaluation

Ordinary notation for writing expressions is called infix , where operators separate arguments. Another notation for expressions, one that is very useful for stack-oriented evaluation, is called Polish , or parenthesis-free, notation . In Polish notation the operator comes after the arguments. Thus, for example,

3, 7, +      is equivalent to the infix notation      3 + 7

In Polish notation, going from left to right, the operator is executed as soon as it is encountered. Thus

17, 5, 2, *, +      is equivalent to      17 + (5 * 2)

A Polish expression can be evaluated by an algorithm using two stacks. The Polish stack contains the Polish expression, and the evaluation stack stores the intermediate values during execution. Here is a two-stack algorithm that evaluates Polish expressions where all operators are binary:

A two-stack algorithm to evaluate Polish expressions
  1. If the Polish stack is empty, halt with the top of the evaluation stack as the answer.
  2. If the Polish stack is not empty, pop the Polish stack into a variable called opval .
  3. If opval contains a value, push the contents of opval onto the evaluation stack.
  4. If opval contains an operator, pop the evaluation stack twice, first into b and then into a . Compute ( a opval b) and push the result onto the evaluation stack. Go to step 1.

We illustrate this algorithm in the following diagram, where the expression

13, 4, -, 2, 3, *, +

is evaluated.

opval

Polish Stack

eval stack

comment

 

13, 4, -, 2, 3, *, +

empty

initial configuration

13

4, -, 2, 3, *, +

empty

step 2l

 

4, -, 2, 3, *, +

13

step 3

4

-, 2, 3, *, +

13

step 2

 

-, 2, 3, *, +

4, 13

step 3

-

2, 3, *, +

4,13

step 2

 

2, 3, *, +

9

step 4

2

3, *, +

9

step 2

 

3, *, +

2, 9

step 3

3

*, +

2, 9

step 2

 

*, +

3, 2, 9

step 3

*

+

3, 2, 9

step 2

 

+

6, 9

step 4

+

empty

6, 9

step 2

 

empty

15

step 4

Let us write a program that implements this two-stack algorithm and test it with an evaluation of the polish expression, 16, 9, *, 3, 7, +, +. Each element of the expression will be represented as a string.

//Polish.java - two stack Polish evaluation algorithm
class Polish
{
public static void main(String[] args)
{
String[] expression =
{"13", "4", "-", "2", "3", "*", "+"};
Stack stack = new Stack();
Stack intArguments = new Stack();
String opval;

for (int i = expression.length - 1; i >= 0; --i)
stack.push(expression[i]);
while (!stack.empty()){
opval = (String)stack.pop();
if ( !isOperator(opval) )
        intArguments.push(opval);
else
        intArguments.push(eval(opval, intArguments));
}
System.out.println(" = " + intArguments.top());
}

  static boolean isOperator(String s)
{
return s.equals("+") ||
            s.equals("*") || s.equals("-");
}

  // apply a binary operator to the top two operands on
  // the stack
  static String eval(String operator, Stack stack)
{
String a, b;
b = (String)stack.pop();
a = (String)stack.pop();
if(operator.equals("+"))
return String.valueOf(Integer.parseInt(a) +
                             Integer.parseInt(b));
else if(operator.equals("-"))
return String.valueOf(Integer.parseInt(a) -
                             Integer.parseInt(b));
else
return String.valueOf(Integer.parseInt(a) *
                             Integer.parseInt(b));
}
}

By using code that has already been written and tested, such as Stack in the above example, the programmer has less work to do in the current project of implementing a Polish expression evaluation program.

Queues

A queue is a representation of a list of values where the normal mode of operation is to insert objects at one end and remove them from the other. In the United States, people stand in lines in order to get into a theater or check out at a store. In England these lines are called queues. People enter at the tail and leave from the head. A queue is a First In First Out (FIFO) data structure. Compare this with the stack we discussed earlier. A stack is a Last In First Out (LIFO) data structure, the last value pushed in is the first value popped out.

As with a stack, a queue can be implemented with an array, or as a linked list of elements. Here we present a generic queue based on our generic ListElement described earlier in this chapter. This class is very similar to the class Stack from this chapter. Instead of push() , top() , and pop() , we have add() which adds an element at the front, front() which returns the element at the front of the queue, and pop() which removes the element from the front of the queue and returns it. Also the class maintains two pointers, one to the head or first element, and one to the tail or last element. The stack only used one pointer that referred to the top element.

//Queue.java
class Queue
{
  Object front()
  {
    if(head != null)
      return head.data;
    else
      return null;
  }

  void add(Object value)
  {
    if(head == null){
      head = tail = new ListElement(value);
    }
    else {
      tail.next = new ListElement(value);
      tail = tail.next;
    }
  }

  Object pop()
  {  
    Object result = front();
    if(head != null)
      head = head.next;
    return result;
  }

  boolean empty(){ return head == null; }
  private ListElement head = null;
  private ListElement tail = null;
}

Our program to demonstrate the use of Queue is almost identical to the one we used for Stack . The big difference is in the output. This example will print the values in the order they are added to the queue, 1.111, 2.222 then 3.333.

//QueueTest.java
class QueueTest
{
  public static void main(String[] args)
  {
    Queue queue = new Queue();

    queue.add(new Double(1.111));
    queue.add(new Double(2.222));
    queue.add(new Double(3.333));
    while(!queue.empty()){
      double temp =
              ((Double)queue.pop()).doubleValue();
      System.out.println(temp);
    }
  }
}

Iterators

An iterator is a construct that allows you to iterate over a collection of objects such as a list or an array. Any integer variable can be used as an iterator for an array. It is often useful to be able to simultaneously maintain more than one iterator for a single collection of objects. For example, using one forward iterator and one backward iterator we can reverse the elements in a list, implemented as an array, as shown in the following example.

int foward = 0, backward = list.length-1;
while(forward < backward){
  int temp = list[forward];
  list[forward] = list[backward];
  list[backward] = temp;
  ++forward;
  --backward;
}

There are two iterators in this example, forward , and backward . Because arrays are a fundamental type in Java and many other languages, there is a built-in syntax for iterators that iterate over arrays. Two things are required of an iterator. You need some way to advance the iterator and fetch the next value. You also need some way to determine when you have iterated over the entire collection. For an array, we increment or decrement the index variable and then test to see if we have reached the end or the beginning of the array.

What about an iterator for classes such as List or Stack described in this chapter? The classes that implement singly linked lists have one implicit iterator built into the class. You can use the method next() to iterate over all of the elements of such a list, and hasNext() can be used to detect when the entire list has been scanned. The following example uses this implicit iterator to iterate over the entire list.

IntList list;
// code to fill the list would go here
list.moveToHead();
while(list.hasNext()){
  int value = list.next();
  // do something with value }
}

You cannot, using this implicit iterator, maintain two simultaneous iterators moving at different times or in different directions. In Java, you can create a separate class to implement an iterator for a class such as List . The simplest iterators have only the two methods next() and hasNext() .

An iterator class will, in general, be aware of some details about how a collection is implemented. For the IntList class, the iterator class will need to know that the list is stored as a linked list of IntListElement objects. The standard way to create an iterator is to ask the class, over which the iteration will occur, to create one. This method is typically called iterator() in Java. Here is the new iterator() method for class IntList :

IntListIterator iterator()
{
  return new IntListIterator(this);
}

As you can see, all this does is create an IntListIterator object passing it a reference to the list. Below is the iterator class. This implementation requires that the field head in class IntList , be changed from private to package access (see Section See Package access ) and that IntListIterator and IntList be in the same package.

// IntListIterator.java - simple forward iterator
class IntListIterator {

  // Create an iterator positioned before the first
  // element of the list.
  IntListIterator(IntList list)
  {
    current = null;
    this.list = list;
  }

  // Create an iterator positioned at element pos.
  IntListIterator(IntList list, IntListElement pos)
  {
    // pos must refer to an element in list
    current = pos;
    this.list = list;
  }

  //Same as next() in IntList.
  int next()
  {
    if(current == null)
      current = list.head;
    else
      current = current.next;
    return current.data;
  }

  //Same as hasNext() in IntList.
  boolean hasNext()
  {
    if(current != null)
      return current.next != null;
    else
      return list.head != null;
  }

  int current()
  {
    return current.data;
  }

  IntListIterator copy()
  {
    return new IntListIterator(list,current);
  }
  IntListElement current;
  IntList list;
}

Using this class we can now have as many forward iterators at the same time for a list as we wish. Suppose we wanted to check and see if a list was in fact composed of two identical shorter lists concatenated together. Below is a method that will check for this condition.

//IteratorExample.java
class IteratorExample
{
  static boolean checkDuplicate(IntList list)
  {
    // count the number of elements in the list
    int numElements=0;
    IntListIterator iterator = list.iterator();
    while(iterator.hasNext()) {
      iterator.next();
      ++numElements;
    }
    // check for an even number of elements
    if(numElements%2 != 0)
      return false;
    // now compare the first half with the second half
    IntListIterator first = list.iterator();
    IntListIterator second = list.iterator();
    // advance second to the start of the second half
    for(int i=1; i<=numElements/2; ++i)
      second.next();
    while(second.hasNext())
      if(first.next() != second.next())
        return false;
    return true;
  }
}

Below is another example of using iterators. In the example below we show how iterators can be used to recursively process a list. These two methods below can be added to the class IntList . The first method simply creates an empty list and calls a private helper method to do the copy.

  static IntList copy(IntListIterator iter)
  {
    return new IntList().copy_helper(iter);
  }

The second method is the recursive helper method.

  private IntList copy_helper(IntListIterator iter)
  {
    if(iter.hasNext()) {
      insert(iter.next());
      return copy_helper(iter);
    }
    else
      return this;
  }

Dissection of IntList copy_helper()

Test for the base case of the recursion which occurs when the iterator has been advanced over all elements and there are no more elements to process.

If there are more elements to be copied, insert the next element from the list being copied into this IntList object which is the copy. Remember, the static method copy() created a new IntList object that will be the copy. The method copy_helper() is operating on this new IntList object. After inserting the next element in the copy, recursively call copy_helper() which will eventually return a reference to this , after all elements have been copied.

When all elements have been copied into the copy, which is the object referred to by this , the IntList object being operated on by copy_helper() , simply return a reference to the copy. This will cause all of the recursive calls made in the repeated executions of the statement

return copy_helper(iter);

to return also.

 

Using iterators to implement append()

Let's implement the method append() for the class IntList . This method appends all of the elements from one list onto the end of another list. We will present three different versions. Our first solution does not take advantage of any iterator methods. Our second solution will use the existing built-in iterator in IntList . The third solution, shows how iterators can be used to create a simple implementation of append() .

Here is the first solution that does not use the other methods in IntList . In this way, the built-in iterators for the two lists are not repositioned.

void append(IntList list)
{
  IntListElement thisList = head;
  IntListElement otherList = list.head;
  IntListElement previous = null;
  // Position thisList on the last element by
  // advancing it off the end and then backing up one.
  // After the loop, previous will point to the last
  // element or be null if the list is empty.
  while(thisList != null){
    previous = thisList;
    thisList = thisList.next;
  }
  thisList = previous;

  // Loop over the other list and insert each element
  // onto the end (pointed to by thisList).
  while(otherList != null){
    // do the insert
    thisList.next=new IntListElement(otherList.data);
    thisList = thisList.next;
    // move to the next element of other list
    otherList = otherList.next;
  }
}

It is preferrable to use the higher level operations provided by a class, even when adding additional methods to a class. In this way, the number of methods that must change in response to some low level implementation detail change is minimized. Below is a first attempt at solution two which uses the existing routines from the class IntList .

void append(IntList list)
{
  // Position first lists built-in iterator on its
  // last element.
  while(hasNext())
    next();

  // Position the second lists built-in iterator on its
  // first element.
  list.moveToHead();

  // Add each element from the second onto the end
  // of the first.
  while(list.hasNext())
    insert(list.next());
}

The problem with the above code is that it changes the value of the field current for both lists. Such a change is probably unexpected by the programmer using append() , particularly the change in current for the explicit parameter list . To resolve this problem, we can save both current and previous for both lists and then restore them before the method returns, as shown below.

void append(IntList list)
{
  // Save positions of built-in iterators.
  IntListElement saveCurrent = current;
  IntListElement savePrevious = previous;
  IntListElement listCurrent = list.current;
  IntListElement listPrevious = list.previous;

  // Position first lists built-in iterator on its
  // last element.
  current = head;
  while(hasNext())
    next();

  // Position the second lists built-in iterator on its
  // first element.
  list.moveToHead();

  // Add each element from the second onto the end
  // of the first.
  while(list.hasNext())
    insert(list.next());

  // Restore the built-in iterators.
  current = saveCurrent;
  previous = savePrevious;
  list.current = listCurrent;
  list.previous = listPrevious;
}

An even more robust solution is to use iterators. In order to use iterators, we will first need to add a new insert() method that allows us to insert after the position indicated by an iterator. This is similar to our current insert() but instead of only allowing insertion after the single implicit iterator, we allow insertion after an arbitrary iterator. We leave the implementation of this new insert() as an excercise. Once the new insert() method is added to the class IntList , we can implement append() like this:

void append(IntList list)
{
  IntListIterator thisList = this.iterator();
  IntListIterator otherList = list.iterator();
  // Move iterator for first list to its last element.
  while(thisList.hasNext())
    thisList.next();
  // Add each element from the second onto the end
  // of the first.
  while(otherList.hasNext())
    thisList =
          insert(thisList, otherList.next());
}

This last solution completely isolates the implementation of append() from the implementation details of class IntList . This version of append() will work for any list implementation that has iterators, and an insert() method that takes an iterator and a value to insert.

Sorting a linked list

A very simple sorting algorithm to implement for linked lists is an insertion sort . This is similar to sorting a hand of playing cards by picking the cards up one at a time and placing them in their proper position. This is not an "in place" sort, meaning, we do not modify the original list. Instead, we create a new list that is a copy of the original elements but in the proper order. The following method can be used to sort an IntList list. The following example uses our original IntList class with the addition of a method to insert at a position specified by an iterator as discussed just above.

//IntListSort.java
class IntListSort
{
  static IntList sort(IntList list)
  {
    IntList sorted = new IntList();
    IntListIterator listIter = list.iterator();
    while(listIter.hasNext()){
      // select the next item to be inserted
      int newItem = listIter.next();
      IntListIterator sortedIter = sorted.iterator();
      IntListIterator previous = null;
      // loop until a bigger item is found in sorted
      while(sortedIter.hasNext() &&
         newItem > sortedIter.next()){
        previous = sortedIter.copy();
      }
      // insert before the bigger item which we do
      // by inserting after the element before it
      if(previous == null) // insert at head
        previous = sorted.iterator();
      sorted.insert(previous, newItem);
    }
    return sorted;
  }
}

Dissection of IntListSort

Create a new empty list that will eventually contain the elements from list , but in order, with the smallest elements first.

Create an iterator and then examine each of the elements in list using a while-statement. The body of the loop will insert the elements from list list into the list sorted so that elements in sorted are always in non-decreasing order.

We use two iterators to find the insertion point. The iterator previous will be null until the loop body has been executed at least once. From then on, previous will point to the element before the element pointed to by sortedIter . When the loop exits, previous will point to the element preceding the insertion point or be null , in which case, insertion should be done at the head of sorted .

Check for the special case of insertion at the head. To insert at the head we create a new iterator, positioned before the first element. Once previous is properly set, do the insertion.

 

Iterators and the interface Iterator

As we have shown above, iterators need to have two methods, hasNext() and next() . The standard Java interface Iterator from the package java.util requires these two methods plus a method remove() .

Early versions of Java used an interface, java.util.Enumeration, which was logically equivalent to Iterator, but without the remove() method. The method names were slightly different, hasMoreElements() and nextElement() .

A class that implements the Iterator interface must include a method remove() but the method is not required to actually remove the item indicated by the iterator. If the remove() method does not remove the item it should throw an UnsupportedOperationException .

The use of this interface simplifies code that uses iterators. All loops that use iterators now become more alike. When combined with the stylistic use of method iterator() to return an iterator for a container, many loops now take on the following form:

Iterator i = container.iterator();
while(i.hasNext()){
  SomeType local_variable = (SomeType)i.next();
  // do something with local_variable
}

We have used Iterator instead of some type specific iterator class. This means one less class for the reader of the code to understand. The only downside is that we may need to cast the result of next() into the appropriate type. The specification of next() in interface Iterator returns a value of type Object . As we have seen, this operation is safe in the sense that if we attempt an illegal cast, an exception will be thrown.

The interface Iterator is only useful for iterators that iterate over containers of non-primitive values. The added overhead of wrapping a primitive type into a wrapper class and then unwrapping it is probably not worth it for containers such as our IntList from Section See A singly linked list . Iterator is useful when working with generic containers. For example, the standard Java class LinkedList has a method iterator() that returns an Iterator object than can be used to iterate over the elements in the LinkedList .

Deleting objects

We have seen how to create objects using the keyword new . Each new object occupies some space in the computer's memory. So what happens to objects that are no longer needed? In some programming languages, notably C and C++, it is the programmer's responsibility to explicitly tell the computer when certain objects (they aren't called objects in C, but that is not important) are no longer needed. In Java, the computer automatically figures out when an object is no longer needed and removes it. This is called garbage collection. Using 1990's terminology it would be better named, memory recycling, but garbage collection was used to refer to this activity before the recycling of human created garbage became popular.

How does the computer know when an object is no longer needed? It doesn't, but it does know when the object can no longer be referenced by the program. If there are no legal references to an object, the memory allocated to the object can be recycled. Consider the following example:

String word = Console.in.readWord();
while(!word.equals("quit")){
  // do some processing with the word
  word = Console.in.readWord();
}

Each call to readWord() returns a reference to a new String object. At the end of each loop iteration, word is assigned to refer to a new String object, losing the reference to the previous object. If the rest of the loop does not create any additional references to the object referred to by word , then the memory for all but the last String object can be recycled.

We do not have space for an extensive discussion of garbage collection algorithms. To give you some idea of how these work we will describe simplified approximations of two approaches.

One way to determine if there are any legal references to an object is to locate all of the variables in the active methods. A method is active if it has been called and has not yet returned. For each of these variables that is a reference type, mark the object it refers to as live. Then examine each live object and find the reference type variables in those objects and mark the objects they refer to as live. Continue this process until no new objects are marked as live. Any object that was not marked is garbage and can be recycled. This is called mark and sweep garbage collection . This process of marking the objects and sweeping up the garbage is typically done when the computer begins to run low on memory. It can be very time consuming, possibly taking several seconds which can be annoying to people using the system.

Another approach is to count the references to a particular object as they are created. When a reference gets overwritten, the count of references to the object is decremented. When an assignment results in a new reference to the object, the count is incremented. When the count goes to zero, the object can be collected. This approach is appropriately called reference counting . Reference counting doesn't cause the big delays of mark and sweep; instead, it slows the entire system down a little bit all of the time because all operations that can affect references must deal with adjusting the counts.

There are many good books on garbage collection if you wish to learn more.

Packages

Even the simplest Java program uses classes that were written by others. This ability to reuse parts of programs is essential for building today's complex software systems. Collections of functions, procedures or classes are often called libraries. Essentially all programming languages or their development systems provide some mechanism for a program to use these routines or classes.

In Java, groups of related classes can be placed in a package . There are two primary reasons for organizing classes into packages. First, a field or method that is defined without any of the access modifiers, public , protected or private , can only be accessed from a method in a class from the same package. In this way, classes can expose some implementation details to other classes in the same package but not to classes outside of the package.

The second reason for using packages is to provide separate name spaces. This allows two different programmers or organizations to have classes with the same name and still use these classes in one program. For example a software company that would like to define some of the standard mathematics functions slightly differently could create their own Math class. This could be placed in a package with a name derived from the companies name. Part of the Java specification is a naming scheme for packages. This scheme is somewhat like Internet addresses in reverse, with the most general part of the name first. So a company with the Internet address www.coolsoft.com , might name their package containing the Math class com.coolsoft.general . If CoolSoft Corporation had a collection of classes to use for building graphical user interfaces, they might put them in a different package called com.coolsoft.gui . This last package might have classes with some of the same names as those in the standard Java package java.awt . For example, it is hard to find a better name for the class that implements a visual button than Button . There is already a class named Button in java.awt . Without packages to provide different name spaces, you couldn't write a program that used com.coolsoft.gui.Button in one place and j ava.awt.Button somewhere else.

Package access

As mentioned, a primary reason for using packages is to allow a group of classes to share methods and fields but not allow those methods or fields to be accessed outside of the package. In addition, a package can contain entire classes that are not visible outside of the package. We have already seen how the modifier private can be used to hide inplementation details inside of a class. In the same way, package access hides implementation details inside of a package. Package access is the default which is obtained by not specifying any access modifier. Another access level we have seen is public . This is the access modifier that must be used for any classes, methods, or fields that are to be made visible or exported outside of the package. In the following example we have modified IntListElement , IntStack , and IntList to create a package intContainers that exports the two classes IntStack and IntList . Only the parts that changed are shown. The missing portions can be filled in from the earlier examples in this chapter.

// IntListElement.java
package intContainers;

class IntListElement{
    // omitted
}

// IntStack.java
package intContainers;

public class IntStack
{
  public int top() // body omitted
  public void push(int value) // body omitted
  public int pop() // body omitted
  public boolean empty() // body omitted
}

// IntList.java
package intContainers;

public class IntList
{
  public void insert(int value) // body omitted
  public int next() // body omitted
  public void remove() // body omitted
  public void moveToHead() // body omitted
  public boolean hasNext() // body omitted
  private IntListElement head,current,previous;
}

They keyword public has been added to all of the methods in IntList and IntStack . It has also been added to the class definition for those two classes. Notice that the IntListElement class is not public. It has package access which is specified by the absence of either private or public. Package access prevents IntListElement from being used outside of the package. IntListElement is an implementation detail that should not be visible outside of the package.

Using packages

Let's review how we use packages. Whenever you wish to use a class from an existing package, you need to use an import statement to import the class. For simplicity, we usually import all of the classes from a package with import statements like:

import tio .*;

This statement imports all of the classes in the package tio . The "*" is called a wildcard, meaning give me all of the classes. We can also import specific classes. For example, in most of our examples we could have used this instead:

import tio .Console;

Most of the time, the only class we have been using directly is the class Console . Another alternative is to not use an import statement at all and instead always spell out the full name of the class. The full name of a class, called the qualified name, includes the package name. This can be rather awkward and is not recommended if you use the name of the package more than once. For example, we could use the following to read integers from the console:

int x = tio .Console.in.readInt();

The import statement told the compiler that if it encountered a class name it didn't recognize, it should try looking for it in the imported package. The import statements can save a lot of typing.

This explicit naming mechanism is what would make it possible to use two different Math classes. Here is how we could use the Math class from CoolSoft.

double x = Math.sqrt(y); // from java.lang
double y = com.coolsoft.Math.sqrt(y);

The package java.lang does not need to be imported. It is imported by default into every Java class. That is why we could write Math.sqrt() which uses the class Math from package java.lang , without having to use an import statement. The package java.lang is the only package that is automatically imported.

Creating packages

Every Java program can use classes from one unnamed package. Any classes in a single directory on your computer's disk, that do not specify a package name, are part of the same unnamed package. To place the classes into a named package, you need to do two things. You need to add a package statement to the top of each class in the package as shown in the example above. You also need to place the classes into an approriately named location on your computer's disk. For the intContainers package introduced above, you need to place the source files in a subdirectory with the same name as the package, "intContainers." If you are compiling your Java programs using a Unix or DOS command line, then with your current directory set to the one containing the subdirectory "intContainers,"execute the command:

javac intContainers/*.java

Note that the current directory is not intContainers but the one containing the subdirectory intContainers . This will compile all of the Java source files in the subdirectory. The above command is for Unix. On DOS you would use a "\" instead of a "/" to separate the subdirectory from the wildcard file name. If you are using an integrated development environment, you will probably need to create a project that includes the files from the package and then compile them.

By default, Java looks in the directory where Java was installed for packages, and then looks in the current working directory for packages. You can change this by changing the CLASSPATH environment variable. You will need to check with your instructor, or read the documentation with your system to determine the appropriate way to do this. For small projects this is usually not necessary.

Programming style

Code reuse, is the practice of reusing existing code in new programs. This has been an important part of programming from the beginning, but the degree of reuse is increasing. The complexity of today's applications requires code reuse. Code reuse reduces development time and improves reliability. The increased reliability derives from the fact that the reused components have, in general, been thorougly tested.

There are two sides to code reuse, the creation of reusable components and the use of those components. One of the strengths of Java is the large and growing collection of reusable components. As we have seen, these components are called classes and they are collected into packages. In this chapter we have introduced some basic data structures. It is important that you know how these data structures are created. When building real applications, you should, in general, not re-implement these basic data structures, but should instead select some appropriate reusable class or package that provides the functionality your application needs.

In a well designed program that uses data abstraction properly, if at some point you determine that the performance of a class from a pre-existing package is inadequate for your application, you should be able to easily replace that package with an implementation of your own. In this way you avoid expending effort "re-inventing" the wheel until you have determined that a truly specialized wheel is necessary.

Beginning with JDK1.2, the standard Java classes include a number of useful containers in the package java.util . These include LinkedList , Stack and several others.

Another option is the Java Generic Library (JGL) from Objectspace. JGL contains several packages. Although not standard Java packages, these packages are supported in many Java development systems and are freely available via the Internet. JGL includes implementations of singly linked lists, doubly linked lists, stacks and queues. The package provides forward and backward iterators for all container classes. It also includes several other important data structures that we have not discussed. JGL includes several algorithms including the ablity to sort any JGL container.

Summary

  • Self-referential structures use references or pointers to link together items of the same type.
  • The simplest self-referential structure is the linear or singly linked list. Each element points to the next element, with the last element having a link value of null .
  • Many list processing algorithms are naturally implemented recursively. Frequently, the base case is when the end of the list is reached. The general case recurs by moving to the "next" element.
  • The abstract data type (ADT) stack is implementable as a linked list, with access restricted to its first element, which is called the top. The stack has a LIFO (last-in-first-out) discipline implemented by the routines push() and pop() .
  • The ADT queue is also implementable as a linked list, with access restricted to its front and rear ends. The queue has a FIFO (first-in-first-out) discipline implemented by the routines add() and pop() .
  • A doubly linked list has a link to the next and previous elements. Having both forward and backward links facilitates some list operations.
  • Generic list structures can be created by having the list elements store a reference to an Object . Any non-primitive type can be stored directly in such an element. The wrapper classes from java.lang must be used to store primitive values in such a list.
  • Iterators are used to iteratively process all of the elements in a container such as a list. An iterator at the very least needs the two methods next() and hasNext() .
  • A group of related classes can be placed in a package. By doing this, some implementation details can be exposed to other classes in the same package without making them generally accessible. Packages also provide for namespaces so that two classes with the same name but from different packages can be combined in a single program.

Review questions

What causes a NullPointerException ?
  1. What is the default value for reference fields?
  2. Draw a picture of a singly linked list containing the values 10, 20, 30 in that order.
  3. Draw a picture of a doubly linked list containing the values 10, 20, 30 in that order.
  4. A stack is used to process data in what order, LIFO or FIFO?
  5. A queue is used to process data in what order, LIFO or FIFO?
  6. What standard Java type is used to turn a primitive int value into an object? Why would you want to do this?
  7. Why would you need an iterator for IntList when it already has methods hasNext() and next() ?
  8. IntList could have been implemented without the field previous . What operation would have been slowed down significantly if previous was not used?
  9. Name one operation that would be much faster on a doubly linked list than a singly linked list.
  10. How is package access specified? What does it mean?
  11. What was wrong with using the implicit iterator in IntList to implement append() as shown on See void append(IntList list) {   // Position first lists built-in iterator on its   // last element.   while(hasNext())     next();   // Position the second lists built-in iterator on its   // first element.   list.moveToHead();   // Add each element from the second onto the end   // of the first.   while(list.hasNext())     insert(list.next()); } ?
  12. Each time a method is called, some context such as the value of local variables and the address of the last statement executed must be saved. When the called method returns, the context of the method that did the call is restored. What data structure is used to store these contexts? Hint: Think about methodA() calling methodB() calling methodC() and then each returning in turn.
  13. If you wanted to write a computer program to simulate a bank teller, what data structure would you use to store the objects representing each simulated customer as they arrive at the bank?

Exercises

Write an insertion method that inserts an element before the first element of an IntList list.
  1. Write an insertion method that inserts an element after the last element of an IntList list.
  2. Write an insertion method that inserts an element at the first position in an IntList list following an element storing a particular data value. If there is no such element then insert the element after the last element.
  3. Generalize the previous three exercises. Write an insertion function that inserts an element in the n th position in a list, where 0 means the element is placed at the head of the list. If n is larger than the length of the list, insert the element at the tail of the list
  4. Modify the method next() in class IntList to throw a NoSuchElementException if there is no next element. The syntax for throwing the exception is

throw new NoSuchElementException();

  1. Add a constructor to class IntList that takes an array of integers and uses the array to build an initial list. The elements in the list should be in the same order as the elements in the array.
  2. Add a method toIntArray() to the class IntList , that returns a new array of integers that contains the same elements as the list, in the same order.
  3. Write a class that implements the same methods as IntList , but represent the list as an array of integers. Add a constructor that allows the programmer to specify the maximum size of the list. Use this to set the size of the internal array.
  4. Write a class List that can store a list of any non-primitive type values. Start with IntList and make the same changes that were made to create the generic class Stack .
  5. Create a class Data , that contains two integer fields, one for age and one for weight, and one string field for a name. Build a list of Data objects using List from the previous excercise. Then write a method to count the number of objects in the list that have age and weight fields above a given value.
  6. Write a class IntDList that uses the IntDListElement defined on See doubly linked lists . Include methods for insertion, deletion, and a method toString() .
  7. Add a method removeDups() to your class IntDList from the previous excercise. The method removes duplicate valued elements from the list.
  8. Write a class DListElement , that is a generic list element, like ListElement , but doubly linked.
  9. Use the DListElement of the previous excercise to implement a DList class with methods that function like those in IntList .
  10. Add method previousElement() to DListElement .
  11. Write a program that uses the class Stack to reverse the words in a sentence. The sentence to be reversed should be read using Console.in.readWord() . Use Console.in.hasMoreElements() to check for the end of the input. Use lastIndexOf() and subString() from class String to remove the period at the end of the last word of the sentence.
  12. Add a method concatenate(IntList list) to class IntList . This method does not copy the elements of list , as does append() , instead it simply sets the field next of the list referred to by this to point to the first element of the list referred to by list . Draw the list that would result from listOne.concatenate(listOne) , where listOne refers to a list of two elements. What happens if the resulting list listOne is printed using the method toString() from See Implementing toString() for IntList ?
  13. The previous excercise was used to construct a cycle. A cycle is a pointer chain that points back to itself. Cycles are particularly nasty run-time bugs that can be hard to recognize. Add a method iscycle() to class IntList that returns true if a cycle is detected and false otherwise. Hint: Save a reference to the initial element of the list and follow the links until either null is reached or the initial element is encountered.
  14. Modify concatenate() in the previous exercise to throw an IllegalArgumentException if the result of the operation would create a cycle. Do not do the concatenation in that situation. The exception IllegalArgumentException is defined in the package java.lang .
  15. Add a static method c opyCat(IntList a, IntList b) to class IntList , that returns a concatenated copy of the lists a and b . The original lists a and b should remain undisturbed. Notice that this method should work fine if called with both arguments referencing the same list.
  16. Add a method insert(IntListIterator iter, int value) , that inserts a new element with the field data set to value , following the element referred to by the iterator iter . The method should return a new IntListIterator , positioned at the element just inserted. Note that an iterator not pointing to any element ( current == null ) should be interpreted as positioned before the first element. This allows for insertion at any point. It is not possible to position the iterator after the last element.
  17. Using the iterator class IntListIterator , add a method with signature

IntList concatenate(IntListIterator index1,
                   IntListIterator index2)

to the class IntList . This method should return a new list that is the result of concatenating copies of the elements starting from index2 onto a list made from copies of the elements starting from index1 . Write an interative solution

  1. Use recursion to solve the previous problem.
  2. Starting with a linked list of objects as specified in excercise See Create a class Data, that contains two integer fields, one for age and one for weight, and one string field for a name. Build a list of Data objects using List from the previous excercise. Then write a method to count the number of objects in the list that have age and weight fields above a given value. , write a routine sortAge() that will sort the list according to its age values. Write a function sortName() that will sort in lexicographic order based on the name values.
  3. Evaluate the following Polish expressions by hand:

7, 6, -, 3, *
9, 2, 3, *, 4, -, +
1, 2, +, 3, 4, +, *

  1. Write corresponding Polish expressions for the following:

(7 + 8 + 9) * 4
(6 - 2) * (5 + 15 * 2
6 - 2 * 5 + 15 * 2

  1. Use the Polish program that we wrote on See //Polish.java - two stack Polish evaluation algorithm class Polish { public static void main(String[] args) { String[] expression = {"13", "4", "-", "2", "3", "*", "+"}; Stack stack = new Stack(); Stack intArguments = new Stack(); String opval; for (int i = expression.length - 1; i >= 0; --i) stack.push(expression[i]); while (!stack.empty()){ opval = (String)stack.pop(); if ( !isOperator(opval) )         intArguments.push(opval); else         intArguments.push(eval(opval, intArguments)); } System.out.println(" = " + intArguments.top()); } , to evaluate the six Polish expressions given or derived in the previous two excercises.
  2. The following lines occur in the evaluate() function in the Polish program:

   b = (String)stack.pop();
   a = (String)stack.pop();

What happens if we write

   a = (String)s.pop();
   b = (String)s.pop();

instead? The program should work properly on some Polish expressions but not on others. Explain.

  1. Write a routine that allows you to interactively initialize the contents of a Polish stack. Write a program to test your routine.
  2. When we tested our Polish program, the Polish expression we used did not have any unary operators in it. Try the program with the following expression:

2, -3, -, -4, 7, +, -1, -1, +, *, *

Is the Polish program able to handle this correctly? (It should be able to.) Write another version of the Polish program that can handle both unary plus and unary minus operators in the list. For example, your program should be able to handle the following Polish expression:

2, -, 3, -, -, 4, +, 7, +, -1, -, +, +, 1, +, *, *

In this expression, some of the plus and minus signs are unary and some are binary.

  1. Add a constructor to the class Queue that builds a queue from an array of objects.
  2. Add a method toArray() to the class Queue that returns an array that contains the same elements as the Queue . Did you copy the elements into the new array or just the references to the elements. Discuss the two alternatives.
  3. Use a general linked list structure to program sparse matrix addition. A sparse matrix is one in which most of its values are zero. A nonzero element of a sparse matrix will be represented by the triple ( i , j , value ). For each row i , the triples will be linked as a linear list. The will be an array with as many entries as their are rows in the matrix. Each array entry will be the list for the corresponding row. To add matrix A to matrix B , we take each row and merge them into a matrix C . For each row index, if only one matrix contains elements for that row, then that row is duplicated in C. If both matricies contain elements for a given row the rows are merged. If both rows have a triple with the same column value, then in the output row c i,j is the sum a i,j  +  b i,j . Otherwise the element with smallest column number becomes the next element of the output row.
  4. Although sparse matrix addition can be performed with just row linked lists, for multiplication, both row- and column-linked lists are required. You will not be able to use the list classes developed in this chapter. Each element can potentially have both a row successor and a column successor. If the elements are implemented by the class SMElement , then there will be two SMElement arrays, one for the rows and one for the columns. Each non-null array entry in the row array will be a link to the first non-zero row entry. The columns are handled similarly. Program sparse matrix multiplication.
  5. Implement a sparse polynomial class. Use a linked list of elements to represent the nonzero terms of the polynomial. A term is a real coefficient and a power. Write a complete polynomial manipulation package. Your package should be able to input and output polynomials, and it should be able to add, subtract, multiply, and copy polynomials.