238 5. Engine Support Systems
link.m_pPrev = link.m_pNext = NULL;
}The code is a bit simpler when we use the m_root design:
void LinkedList::remove(Link<ELEMENT>& link)
{
// The link must currently be a member of the list.
ASSERT(link.m_pNext != NULL);
ASSERT(link.m_pPrev != NULL);
link.m_pNext->m_pPrev = link.m_pPrev;
link.m_pPrev->m_pNext = link.m_pNext;
// Do this to indicate the link is no longer in any
// list.
link.m_pPrev = link.m_pNext = NULL;
}The example code shown above highlights an additional benefi t of the
circularly linked list approach: A link’s m_pPrev and m_pNext pointers are
never null, unless the link is not a member of any list (i.e., the link is unused/
inactive). This gives us a simple test for list membership.
Contrast this with the “loose” head/tail pointer design. In that case, the
m_pPrev pointer of the fi rst element in the list is always null, as is the m_pN-
ext pointer of the last element. And if there is only one element in the list, that
link’s next and previous pointers will both be null. This makes it impossible to
know whether or not a given Link is a member of a list or not.
Singly-Linked Lists
A singly-linked list is one in which the elements have a next pointer, but no pre-
vious pointer. (The list as a whole might have both a head and a tail pointer, or
it might have only a head pointer.) Such a design is obviously a memory saver,
but the cost of this approach becomes evident when inserting or removing an
element from the list. We have no m_pPrev pointer, so we need to traverse the
list from the head in order to fi nd the previous element, so that its m_pNext
pointer can be updated appropriately. Therefore, removal is an O(1) operation
for a doubly-linked list, but it’s an O(n) operation for a singly-linked list.
This inherent insertion and removal cost is oft en prohibitive, so most
linked lists are doubly linked. However, if you know for certain that you will
only ever add and remove elements from the head of the list (as when imple-
menting a stack), or if you always add to the head and remove from the tail (as
with a queue—and your list has both a head and a tail pointer), then you can
get away with a singly-linked list and save yourself some memory.