Game Engine Architecture

234 5. Engine Support Systems

and previous pointers appropriately as well. There are four cases to handle

when adding a node to a linked list:

• Adding the fi rst element to a previously-empty list;


• Prepending an element before the current head element;


• Appending an element aft er the current tail element;


• Inserting an interior element.
  These cases are illustrated in Figure 5.8.
  Removing an element involves the same kinds of operations in and
  around the node being removed. Again there are four cases: removing the
  head element, removing the tail element, removing an interior element, and
  removing the last element (emptying the list).

The Link Data Structure

Linked list code isn’t particularly tough to write, but it can be error-prone.

As such, it’s usually a good idea to write a general-purpose linked list facility

that can be used to manage lists of any element type. To do this, we need to

separate the data structure that contains the links (i.e., the next and previ-

ous pointers) from the element data structure. The link data structure is typi-

cally a simple struct or class, oft en called something like Link, Node, or

LinkNode, and templated on the type of element to which it refers. It will usu-

ally look something like this.

Head Tail

Head

Tail

Head

Tail

Head

Tail

Head

Tail

Head

Tail

Head

Tail

Head

Add First Tail

Prepend

(Push Front)

Insert

Append

(Push Back)

Figure 5.8. The four cases that must be handled when adding an element to a linked list: add

fi rst, prepend, append, and insert.