236 5. Engine Support Systems
template< typename ELEMENT >
struct Link
{
Link<ELEMENT>* m_pPrev;
Link<ELEMENT>* m_pNext;
// No ELEMENT* pointer required, thanks to
// inheritance.
};class SomeElement : public Link<SomeElement>
{
// other members...
};
The big pitfall of the intrusive linked list design is that it prevents an ele-
ment from residing in more than one linked list at a time (because each ele-
ment has one and only one link). We can allow an element to be a member of
N concurrent lists by providing it with N embedded link instances (in which
case we cannot use the inheritance method). However, the number N must
be fi xed a priori, so this approach is still not quite as fl exible as the extrusive
design.
The choice between intrusive and extrusive linked lists depends on the
application and the constraints under which you are operating. If dynamic
memory allocation must be avoided at all costs, then an intrusive list is prob-
ably best. If you can aff ord the overhead of pool allocation, then an extrusive
design may be preferable. Sometimes only one of the two approaches will
be feasible. For example, if we wish to store instances of a class defi ned by a
third-party library in a linked list and are unable or unwilling to modify that
library’s source code, then an extrusive list is the only option.Head and Tail Pointers: Circular Lists
To fully implement a linked list, we need to provide a head and a tail pointer.
The simplest approach is to embed these pointers in their own data structure,
perhaps called LinkedList, as follows.
template< typename ELEMENT >
classLinkedList
{
Link<ELEMENT>* m_pTail;
Link<ELEMENT>* m_pHead;
// member functions for manipulating the list...
};
You may have noticed that there isn’t much diff erence between a
LinkedList and a Link—they both contain a pair of pointers to Link. As it