Top Up Prev Next Bottom Contents Index Search

1.6 Doubly linked lists


Support for doubly linked lists is found in DoubleLink.h. The class DoubleLink implements a base class for nodes in the list, class DoubleLinkList implements the list itself, and class DoubleLinkIter forms an iterator. WARNING: We consider this class to have serious design flaws, so it may be reworked quite a bit in subsequent Ptolemy releases.

1.6.1 Class DoubleLink

A DoubleLink object is an item in the list defined by DoubleLinkList. Normally, a programmer will not interact directly with this class, but rather will use methods in DoubleLinkList. Nonetheless, we present it here because some of the methods of DoubleLinkList do refer to it.

There are two constructors:

DoubleLink(Pointer p, DoubleLink* next, DoubleLink* prev): 
DoubleLink(Pointer p);
The first form initializes the next and prev pointers of the node as well as the contents. The second form sets these pointers to null and only initializes the contents pointer.

Pointer content(); 
Return the content pointer of the node.

virtual ~DoubleLink(); 
The destructor is virtual.

void unlinkMe(); 
Delete the node from the list it is contained in. I.e. connect the elements pointed to by the prev and next pointers. The object pointed to by the node is not deleted.

The following data members are protected:

DoubleLink *next; // next node in the list 
DoubleLink *prev; // previous node in the list
Pointer e; // contents of this node

1.6.2 Class DoubleLinkList

DoubleLinkList(); 
DoubleLinkList(Pointer* e);
The first constructor creates an empty list. The second creates a one-node list containing the object pointed to by e. That object must live at least as long as the link lives.

virtual ~DoubleLinkList(); 
The destructor is virtual. It deletes all DoubleLinks in the list, but does not delete the objects pointed to by each link.

DoubleLink* createLink(Pointer e); 
Return a newly allocated DoubleLink that contains a pointer to e. It is up to the caller to delete the DoubleLink, or to use either removeLink or remove.

void insertLink(DoubleLink *x); 
void insert(Pointer e);
These methods insert an item at the beginning of the list. The first inserts a DoubleLink; the second creates a DoubleLink with createLink and inserts that. If the second form is used, the link should only be removed using removeLink or remove, not unlink, because unlink will not delete the DoubleLink.

void appendLink(DoubleLink *x);
void append(Pointer e);
These methods append at the end of the list. The first appends a DoubleLink; the second creates a DoubleLink with createLink and appends that. If the second form is used, the link should only be removed using removeLink or remove, not unlink, because unlink will not delete the DoubleLink.

void insertAhead(DoubleLink *y, DoubleLink *x); 
void insertBehind(DoubleLink *y, DoubleLink *x);
The first method inserts y immediately ahead of the DoubleLink pointed to byx; the second inserts y immediately after the DoubleLink pointed to byx. Both of these functions assume that x is in the list; disaster may result otherwise.

DoubleLink* unlink(DoubleLink *x); 
Remove the link x from the list and return a pointer to it. Make sure that x is in the list before calling this method, or disaster may result.

void removeLink(DoubleLink *x); 
This is the same as unlink, except that x is deleted as well. The same cautions apply.

void remove(Pointer e); 
Search for a DoubleLink whose contents match e. If a match is found, the node is removed from the list and the DoubleLink is deleted. The object pointed to by e is not deleted. The search starts at the head of the list.

int find(Pointer e); 
Search for a DoubleLink whose contents match e. If a match is found, 1 (true) is returned; otherwise 0 (false) is returned. The search starts at the head of the list.

virtual void initialize(); 
Delete all DoubleLinks in the list and make the list empty.

void reset(); 
Make the list empty, but do not delete the DoubleLinks in each of the nodes.

int size(); 
Return the number of elements in the list. This method should be const but isn't.

DoubleLink *head();
DoubleLink *tail();
Return a pointer to the head or to the tail of the list. If the list is empty both methods will return a null pointer.

DoubleLink *getHeadLink(); 
Pointer takeFromFront();
The first method gets and removes the head link, returning a pointer to it. The second method returns the object pointed to by the head link, and deletes the DoubleLink. If the list is empty, both functions return a null pointer.

DoubleLink *getTailLink(); 
Pointer takeFromBack();
These methods are identical to the previous pair except that they remove the last node rather than the first.

The following two data members are protected:

DoubleLink *myHead; 
DoubleLink *myTail;

1.6.3 Class DoubleLinkIter

DoubleLinkIter is an iterator for DoubleLinkList. It is only capable of moving "forward" through the list (following the "next" links, not the "prev" links). Its next operator returns the Pointer values contained within the nodes; it is also possible to use the non-standard nextLink function to return successive DoubleLink pointers.



Top Up Prev Next Bottom Contents Index Search

ptolemy@eecs.berkeley.edu
Copyright © 1990-1997, University of California. All rights reserved.