Link.h

Classes

Link -- doubly linked list primitive (full description)

template<class t> class Link

Interface

Public Members

t &val()

const t &val() const

Link<t> *&next()

const Link<t> *next() const

Link<t> *&prev()

const Link<t> *prev() const

Link(t e,Link<t> *p=0,Link<t> *n=0) : store(e), Prev(p)

~Link()

Link<t> *unlink(Link<t> * = 0)

Description

Review Status

Reviewed By:: UNKNOWN
Date Reviewed:: before2004/08/25

Etymology

This class provides the primitives for creating a class of linked data structures. Thus it is called Link.

Synopsis

This class provides a minimal doubly linked list implementation. All of the work is performed by the constructor. This class does not keep track of the head of the list; this is left to the user of the class. This class can be thought of as the "nodes" of a linked list, but conceptually each of the nodes is a list itself. This class will typically not be used by the average user because although it is a functional doubly linked list implementation, List<t> provides a higher level of abstraction.

Example

This example makes Link behave like a stack:

    #include <iostream>
        #include <casa/Containers/Link.h>
    
        main() {
            Link<int> *hed = new Link<int>(23);
    
            hed = new Link<int>(12,0,hed);
            hed = new Link<int>(19,0,hed);
            hed = new Link<int>(10,0,hed);
    
            while (hed) {
                Link<int> *cur = hed;
                hed = hed->unlink();
                cout << cur->val() << " ";
                delete cur;
            }
            cout << endl;
        }

The output from the previous example would be:

           10 19 12 23

As each new link is being created, the new element goes at the beginning of the list because the previous head of the list, hed, is being passed in as the next list element.

This next example demonstrates how a queue could be created instead of a stack:

    #include <iostream>
        #include <casa/Containers/Link.h>
    
        main() {
            Link<int> *hed = new Link<int>(23);
            Link<int> *cur = hed;
    
            cur = new Link<int>(12,cur);
            cur = new Link<int>(19,cur);
            cur = new Link<int>(10,cur);
    
            while (hed) {
                cur = hed;
                hed = hed->unlink();
                cout << cur->val() << " ";
                delete cur;
            }
            cout << endl;
        }

The output here would be:

           23 12 19 10

Member Description

t &val()
const t &val() const

The val() member function will return a reference to the contents of the current node.

Link<t> &next()
const Link<t> next() const
Link<t> &prev()
const Link<t> prev() const

These member functions allow traversal of the list. the next() functions retrieve the next element in the list, and prev() retrieves the previous element.

The non-const versions of these functions return a reference to the pointer to the next element in the list. This allows for modification of the list if necessary, e.g. for removal of elements.

Link(t e,Link<t> p=0,Link<t> n=0) : store(e), Prev(p)

This is where the maintenance of the list happens. The parameters are:

e -- the element to be added
p -- the previous element of the list
n -- the next element of the list

If the previous element is non-null it is used to get all of the information necessary to add this new element to the list. If the previous element is null and the next element is non-null it is assumed that the new element is being added to the beginning of the list, i.e. before the next element but with no previous element.

~Link()

This destructor destroys the rest of the list, i.e. this object and all that follow.

If the destructor is called for a Link<t> in the middle of a list the elements which occur before the object will be left dangling, and the objects which follow the deleted object will also be deleted.

Link<t> unlink(Link<t> = 0)

This function unlinks a given element of the list. It requires no parameters because the node has links to the previous and next elements in the list. This is useful when removing a single element from the list because the destructor, Link::~Link, will delete the rest of the list elements if they are linked in with this. This function returns the next element in the list.

The Link<t>* parameter is unused. It is a historical artifact which will be removed.