List with Current (v 0.4) -- an Anti-Pattern


Joseph Bergin

csis.pace.edu/~bergin
berginf@pace.edu

Intent

To provide the simples possible linked list ADT.

Other Names

This is sometimes called Linked List, but we have another pattern by this name that is more sophisticated.

Problem

Students need to learn about linked structures relatively early in their student careers. Building a linked list ADT is a sophisticated business however. Some instructors might want a simpler alternative than the Linked List Pattern.

Motivation

This pattern provides mechanisms for several linked list algorithms in a simple package. It consists of only a single class which can be easily used and fairly easily mastered.

Context

This pattern may occur early in the student's education as an example of a list ADT. It can then be used to solve simple problems.

Example

Following is an outline of a C++ list class template that contains the required elements of this pattern. It maintains the implementation invariant that the current pointer logically refers to the value in the node following the one to which it physically points. It maintains a header node that is not logically part of the list. The current pointer is never NULL. 


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
}

Required Elements

Structurally this pattern requires a linked structure with an additional notion of the "current" location. This is usually implemented as a pointer to one of the nodes in the list. List operations advance this current location and other list operations perform actions at the point of current.

Structure

A single class with both list operations and a current pointer. See the example, above, for details.

A List, showing its current

Variations

The list could be doubly linked, making it possible for "current" to retreat as well as advance.

Applicability

This pattern can be used with many simple algorithms.

Consequences

This design is simple. While it can be used for algorithms requiring no more than a single current it is not adequate for more sophisticated work. ADT's should be designed so that they can be useful in a wide variety of problems. Students should see good ADT designs. On the other hand, student's need to see simple things early while their sophistication is growing.

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.

Known Uses

This pattern has been used in a large number of contemporary textbooks.

Related Patterns

Link Pattern is used by this pattern.

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.

References

"Lists with Current Considered Harmful", Joseph Bergin, see: http://csis.pace.edu/~bergin/