The type link used to create a linked list actually does most of the work of the list. Before object-oriented programming, the link was often synonymous with list. The class definition of link is:
template <class Type>
class Link
{
public:
Link(const Type &LinkValue,Link *nextPtr);//creates a new node with specified value and next item
Link() {ptrToNextLink = NULL;}
virtual Link* insert(const Type &val); //insert item following this Link
Link* duplicate();// recursively duplicates list starting at this node
virtual Link* getNext(){return ptrToNextLink;}// returns pointer to next node
virtual Link* removeNext();// removes next node and adjusts next to next->next
Type& value(){return _value;} // returns a reference to data in node
virtual ostream& print(ostream &s){return s << _value;}
virtual istream& read(istream &s){return s >> _value;}
protected:
Type _value; // data stored in node
Link *ptrToNextLink;// link to next item
};
The link class controls the appearance of the list locally. It can insert and delete at a given point and move ahead one step. This means that any class that has access to the beginning of the list may use public functions to manipulate the list. In binary trees, this is not always the case. There are two nodes that follow a given node and the tree descending from one link may not be of a similar size to the tree descending from the other link. To correct this, it is important to have access to the links (see week 14).