6.5 Sequenceable Classes

Classes Dlist, Slist, and Queue implement the Sequence interface. This interface, which extends the Collection interface, contains methods for collections in which the order of elements can be determined externally by the client of the collection, and elements can be accessed by index.

6.5.1 Dlist

Class Dlist implements a doubly-linked list of elements ordered externally by the client of the class. Duplicate entries are allowed.

Items can be inserted efficiently at the beginning, end, or middle of the list, and can be removed the same way. There are several ways to retrieve elements from within the collection. One is by numeric index. Another is by searching for an element that is equal to a given item, as determined by the equals() method inherited or overridden from class Object. Finally, you can search for an element which is identical to a given item, that is, equal in the sense of the == operator.

The primary difference between Dlist and Slist, described below, is that a Dlist provides an enumerator that allows for movement both forward and backward within the collection. The cost is that each node in the Dlist contains one more pointer than an Slist. The storage and maintenance of this extra pointer means that Slists are slightly more efficient in space and time.

The following example, given in its entirety in DlistExample.java, uses a Dlist to determine whether a word or sentence is a palindrome or not.

NOTE: Complete code for this exampleis located in the examples directory created for your installation of Tools.h++ Professional. The "Examples" chapter in Part V, "Resources," describes the location of that directory, or you can check the online build guide for your installation media.

/**
 * Uses two BidirectionalEnumerations, one starting at the front
 * and one at the back, to determine whether the characters in
 * the Dlist represent a palindrome.
 */
public boolean isPalindrome(Dlist dlist) {
  // Create two enumerators:
  BidirectionalEnumeration e1 = dlist.bidirectionalElements();
  BidirectionalEnumeration e2 = dlist.bidirectionalElements();

  // Move one to the back of the list:
  e2.setToEnd();
  /*
   * Check for equality between corresponding characters
   * as we move the enumerators toward each other until
   * they meet in the middle.
   */
  for (int i=0; i<dlist.size()/2; ++i) {
    if (!e1.nextElement().equals(e2.previousElement()))
   return false;
        }

  // WoW! (It's a palindrome):
  return true;
}

In testing whether a string is a palindrome or not, this program does not consider white-space and punctuation. In fact, anything other than letters and digits are not considered.

For example:

java DlistExample "A man, a plan, a canal: Panama!"
"A man, a plan, a canal: Panama!" is a palindrome.

java DlistExample "Harrelson to Boswell to Kranepool"
"Harrelson to Boswell to Kranepool" is not a palindrome.

6.5.2 Slist

Class Slist implements a singly-linked list of elements ordered externally by the client of the class. Duplicate entries are allowed.

Items can be inserted efficiently at the beginning, end, or middle of the list, and can be removed in the same way. There are several ways to retrieve elements from within the collection. One is by numeric index. Another is by searching for an element that is equal to a given item, as determined by the equals() method inherited or overridden from class Object. Finally, you can search for an element which is identical to a given item; that is, equal in the sense of the == operator.

See the entry for Dlist above for a discussion of the difference between classes Dlist and Slist.

6.5.3 Queue

Class Queue implements a First-In-First-Out (FIFO) queue of objects. A Queue is a sequential list for which all insertions are made at one end via put(), but all removals are made from the other end via get(). Duplicate entries are allowed.

Note that this class extends Slist and that you can use inherited methods such as isEmpty() and size().