Game Engine Architecture

237

turns out, there are some distinct benefi ts to using an instance of class Link to
manage the head and tail of the list, like this:

template< typename ELEMENT >

classLinkedList

{

Link<ELEMENT> m_root; // contains head and tail

// member functions for manipulating the list...

};

The embedded m_root member is a Link, no diff erent from any other Link in
the list (except that its m_pElement member will always be NULL). This allows
us to make the linked list circular as shown in Figure 5.9. In other words, the
m_pNext pointer of the last “real” node in the list points to m_root, as does
the m_pPrev pointer of the fi rst “real” node in the list.
This design is preferable to the one involving two “loose” pointers for the
head and tail, because it simplifi es the logic for inserting and removing ele-
ments. To see why this is the case, consider the code that would be required
to remove an element from a linked list when “loose” head and tail pointers
are being used.

void LinkedList::remove(Link<ELEMENT>& link)

{

if (link.m_pNext)

link.m_pNext->m_pPrev = link.m_pPrev;

else

// Removing last element in the list.

m_pTail = link.m_pPrev;

if (link.m_pPrev)

link.m_pPrev->m_pNext = link.m_pNext;

else

// Removing first element in the list.

m_pHead = link.m_pNext;

5.3. Containers

Head

Tail

m_root

Figure 5.9. When the head and tail pointers are stored in a link, the linked list can be made
circular, which simplifi es the implementation and has some additional benefi ts.