csis.pace.edu/~bergin
berginf@pace.edu
template <class E>
class list
{ public:
list()
... // destructor, etc.
void reset(); // reset current to beginning
void advance(); // advance current location
bool atEnd(); // tell if current is at end of list.
void insert(E); // insert E at current location;
void delete(); // delete the current item
E value(); // return the value stored at current location
... // additional members
private:
node* head;
node* current;
...// additional implementation details
};
list::list()
: head(new node (E(), NULL), // header node
current(head)
{
}
void list::reset()
{ current = head;
}
void list::advance()
{ if(current->next != NULL) current = current->next;
else // error handling
}
bool list::atEnd()
{ return current->next == NULL;
}
void list::insert(E element)
{ node* temp = new node(element, current->next);
current->next = temp;
}
void list::delete()
{ if(current->next != NULL)
{ node* temp = current->next;
current->next = temp->next;
delete temp;
}
else
// error handling or no-op
}
E list::value()
{ if(current->next != NULL) return current->next.value;
else // error handling
}
A List, showing its current
Object-oriented design requires that designers pay attention to reusability and generality. This especially true when building infrastructure classes like ADTs which need to be applicable in a wide variety of circumstances. No design would be considered a good one if it requires frequent re-writing of code and recompilation. No design would be considered good unless it presents an interface to the world of sufficient generality to be useful to a variety of clients. No design would be considered even adequate if the abstraction boundary presented by the interface needs to be crossed often to implement needed algorithms.
The pattern presented here is flawed however, as it doesn't permit a large class of simple problems to be solved without breaking encapsulation. The difficulty arises because many algorithms require more than one current location to be maintained.
Suppose that we have searched through the list advancing as we go and have come to some location. Suppose that the problem is now to determine if the list contains another value equal to the current value, and if so, to delete the current value, leaving the other in place. This is impossible to do efficiently as we must leave the current position to determine if there is another with the same value. We could then (possibly) re-search for the original value and remove it, but this wastes time that need not be wasted if the interface were more flexible. Even a process as simple as swapping the values in two list positions becomes problematical and inefficient with this model.
The difficulty here is that there are two different ideas at play: the list, which is a storage structure, and the current location, which is logically just a value connected to (two) others. The design needs to separate these two ideas if algorithmic programming is to be adequately supported.
Note, however, that if you are not trying to write an ADT, this pattern might be indicated. In particular, for some specific applications it works nicely. For example, if you were trying to implement a Rolodex of names & phone numbers, this might be just the right abstraction, since a rolodex has exactly one "current" card. The important thing here is that you are not attempting a general ADT, but a specific application.
Linked List Pattern meets the desired criteria of generality much better than this one. It separates the idea of location into a separate Iterator class. There may be as many iterators as the problem requires.