Previous Section
 < Free Open Study > 
Next Section


6.7 A Specialized List ADT

We have defined Unsorted and Sorted List ADTs and given several implementations of each. Our lists can be used for many applications. However, some applications always need special-purpose lists. Perhaps they require specific list operations that are not defined by our List ADTs, or perhaps the specific qualities of our lists (unique elements) do not mesh well with the requirements of the application. In such cases, we may be able to extend one of our list classes to create a new list that meets the needs of the application. Alternatively, we might create a new list class customized for the application in question.

In the Case Study later in this chapter, we need lists with a unique set of properties and operations. The lists must hold elements of the type int; duplicate elements are allowed. The lists need not support ,, or . In fact, the only list operations that we have been using that this new list construct requires are the operation and the iterator operations. For the Case Study, we will need to process elements from left to right and from right to left, so we need to support two iterators. In addition, we plan to insert items at the front and at the back of our lists. The reasons for these requirements are made clear in the Case Study; for now, we just accept the requirements as stated and consider how to implement the new list.

Let's summarize these specifications in a CRC card.

Click To expand

Given this unique set of requirements, we decide to start from scratch for our new List ADT. Of course, we can reuse our knowledge of lists and perhaps even reuse (cut and paste) some of the code from the previous list implementations. Because the new list construct creates a specialized list for a specific application, we call the list class SpecializedList. To satisfy the requirement that we be able to iterate through the list in both directions, instead of our standard "current position" property, lists of the class SpecializedList have both a "current forward position" and a "current backward position" and provide iterator operations for traversing the list in either direction. Note that this statement does not mean that an iteration can change directions-rather, two separate iterations can be going on at the same time, one forward and one backward.

One advantage of a doubly linked structure is that it supports the ability to traverse a structure in both directions. When a structure is linked in only one direction, it is not simple to traverse it in the other direction. Because a doubly linked list is linked in both directions, traversing the list forward or backward is equally easy. On the other hand, a circular structure with the external pointer pointing to the last item in the structure gives direct access to both the front element and the last element. A doubly linked circular structure would be ideal (see Figure 6.21).

Click To expand
Figure 6.21: A circular doubly linked list
struct NodeType;

class SpecializedList
{
public:
  SpecializedList();                            // Class constructor.
  ~SpecializedList();                           // Class destructor.
  SpecializedList(const SpecializedList& someList);
  // Copy constructor.

  void ResetForward();
  // Initializes current position for an iteration
  //  through the list from first item to last item.

  void GetNextItem(int& item, bool& finished);
  // Gets the next item in the structure.
  //  finished is true if all items have been accessed.
  // GetNextItem and GetPriorItem are independent; a forward
  //  iteration and a backward iteration may be in progress
  //  at the same time.

  void ResetBackward();
  // Initializes current position for an iteration
  //  through the list from last item to first item.

  void GetPriorItem(int& item, bool& finished);
  // Gets the previous item in the structure.
  //  finished is true if all items have been accessed.

  void InsertFront(int item);
  // Inserts item as the first item in the structure.

  void InsertEnd(int item);
  // Inserts item as the last item in the structure.

  int LengthIs();
  // Returns the number of items in the structure.
private:
  NodeType* list;
  NodeType* currentNextPos;
  NodeType* currentBackPos;
  int length;
};

struct NodeType
{
  NodeType* next;
  NodeType* back;
  int info;
};

The constructor must set the list pointer to NULL and the length to 0.

SpecializedList::SpecializedList()
{
  length - 0;
  list = NULL;
}

Although we provide a length operation, we give the user another way of determining when the last item has been accessed. GetNextItem and GetPriorItem both have an extra parameter, a Boolean flag. This flag is set to true when the last item has been returned. ResetForward sets currentNextPos to NULL, and GetNextItem returns the next item in the structure, setting finished to true when currentNextPos equals list. ResetBackward sets currentBackPos to NULL, and GetPriorItem returns the previous item in the structure, setting finished to true when currentBackPos equals list->next.

void SpecializedList::ResetForward()
// Post: currentNextPos has been initialized for a forward
//       traversal.
{
  currentNextPos = NULL;
}

void SpecializedList::GetNextItem(int& item,
     bool& finished)
// Pre:  ResetForward has been called before the first call to
//       this function.
// Post: item is a copy of the next item in the list.
//       finished is true if item is the last item in the list and
//       false otherwise. {
{
  if (currentNextPos == NULL)
    currentNextPos = list->next;
  else
    currentNextPos = currentNextPos->next;
  item = currentNextPos->info;
  finished = (currentNextPos == list);
}

void SpecializedList::ResetBackward()
// Post: currentBackPos has been initialized for a backward
//       traversal.
{
  currentBackPos = NULL;
}

void SpecializedList::GetPriorItem(int& item,
     bool& finished)
// Post: item is a copy of the previous item in the list.
//        finished is true if item is the first item in the list;
//        false otherwise.
{
  if (currentBackPos == NULL)
    currentBackPos = list;
  else
    currentBackPos = currentBackPos->back; 
  item = currentBackPos->info;
  finished = (currentBackPos == list->next);
}

Click To expand
Figure 6.22: Inserting at the front and at the rear

InsertFront inserts the new item as the first item in the list (see Figure 6.22a). InsertEnd inserts the new item as the last item in the list (see Figure 6.22b). The results look quite different in the diagram, but a careful examination reveals that they are identical except for the external pointer list. Inserting an item at the beginning does not change list; inserting one at the end does. We can use the same insertion routine for both, but have InsertEnd move list.

void SpecializedList::InsertFront(int item)
// Post: item has been inserted at the front of the list.
{
  NodeType* newNode;

  newNode = new NodeType;
  newNode->info = item;
  if (list == NULL)
  { // list is empty.
    newNode->back = newNode;
    newNode->next = newNode;
    list = newNode;
  }
  else
  {
    newNode->back = list;
    newNode->next = list->next;
    list->next->back = newNode;
    list->next = newNode;
  }
  length++;
}

void SpecializedList::InsertEnd(int item)
// Post: item has been inserted at the end of the list.
{
  InsertFront(item);
  list = list->next;
}

We leave the implementations of the class destructor, copy constructor, and overloaded assignment operator plus functions LengthIs and MakeEmpty as a programming assignment.

Test Plan

Items must be inserted at both ends of the list, and traversals must go both forward and backward. Note that some of the operations have not been implemented. For example, we can't test the constructor by printing the length. But how can we test it? Well, if the other operations work correctly, then the constructor can be assumed to be correct. Rather than testing all the front insertions and then all the end insertions, let's change the pattern somewhat and mix them up.

Operation to Be Tested and Description of Action

Input Values

Expected Output

InsertFront

   
  • Insert five items

1, 2, 3, 4, 5

 

InsertEnd

   
  • Insert two items

0, -1

 

InsertFront

   
  • Insert one item

6

 

InsertEnd

   
  • Insert one item

-2

 

ResetForward

   

GetNextItem

   
  • Call nine times, print each time

 

6, 5, 4, 3, 2, 1, 0, -1, -2

ResetBackward

   

GetPriorItem

   
  • Call nine times, print each time

 

-2, -1, 0, 1, 2, 3, 4. 5, 6

We should also test each time GetNextItem and GetPriorItem are called to see whether we have reached the end of the traversal. On the Web, the file SpecialDr.cpp is the driver for this class, Speciall.in is the input file representing this test plan, and Speciall.out is the output. The file SpecializedList.h contains the code from this chapter.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)