doubly linked list primitive More...

#include <Link.h>

Public Member Functions
t &	val ()
	The `val()` member function will return a reference to the contents of the current node.
const t &	val () const
Link< t > *&	next ()
	These member functions allow traversal of the list.
const Link< t > *	next () const
Link< t > *&	prev ()
const Link< t > *	prev () const
	Link (t e, Link< t > p=0, Link< t > n=0)
	This is where the maintenance of the list happens.
	~Link ()
	This destructor destroys the rest of the list, i.e.
Link< t > *	unlink (Link< t > *=0)
	This function unlinks a given element of the list.
Protected Attributes
t	store
Link< t > *	Next
Link< t > *	Prev

Detailed Description

template<class t>
class casa::Link< t >

doubly linked list primitive

Intended use:

Public interface

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

Definition at line 116 of file Link.h.

Constructor & Destructor Documentation

template<class t>

casa::Link< t >::Link	(	t	e,
		Link< t > *	p = `0`,
		Link< t > *	n = `0`
	)			`[inline]`

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.

Clean up previous list if inserting in the middle of a list with "p==0".

Definition at line 159 of file Link.h.

template<class t>

casa::Link< t >::~Link ( )

This destructor destroys the rest of the list, i.e.

this object and all that follow.
Warning: 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;

Member Function Documentation

template<class t>

Link<t>*& casa::Link< t >::next ( ) [inline]

These member functions allow traversal of the list.

the next() functions retrieve the next element in the list, and prev() retrieves the previous element.

Tip: 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;

Definition at line 139 of file Link.h.

Referenced by casa::NoticeTarget::next().

template<class t>

const Link<t>* casa::Link< t >::next ( ) const [inline]

Definition at line 140 of file Link.h.

template<class t>

Link<t>*& casa::Link< t >::prev ( ) [inline]

Definition at line 141 of file Link.h.

template<class t>

const Link<t>* casa::Link< t >::prev ( ) const [inline]

Definition at line 142 of file Link.h.

template<class t>

Link<t>* casa::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.
Tip: The Link<t>* parameter is unused; It is a historical artifact which will be removed;

Referenced by casa::Stack< elem >::pop(), and casa::Stack< elem >::popVal().

template<class t>

t& casa::Link< t >::val ( ) [inline]

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

Definition at line 125 of file Link.h.

Referenced by casa::Stack< elem >::popVal().

template<class t>

const t& casa::Link< t >::val ( ) const [inline]

Definition at line 126 of file Link.h.