233The easiest way to implement a dynamic array is to allocate an n-element
buff er initially and then grow the list only if an att empt is made to add more
than n elements to it. This gives us the favorable characteristics of a fi xed-
size array but with no upper bound. Growing is implemented by allocating
a new larger buff er, copying the data from the original buff er into the new
buff er, and then freeing the original buff er. The size of the buff er is increased
in some orderly manner, such as adding n to it on each grow, or doubling it
on each grow. Most of the implementations I’ve encountered never shrink the
array, only grow it (with the notable exception of clearing the array to zero
size, which might or might not free the buff er). Hence the size of the array be-
comes a sort of “high water mark .” The STL std::vector class works in this
manner.
Of course, if you can establish a high water mark for your data, then you’re
probably bett er off just allocating a single buff er of that size when the engine
starts up. Growing a dynamic array can be incredibly costly due to realloca-
tion and data copying costs. The impact of these things depends on the sizes
of the buff ers involved. Growing can also lead to fragmentation when dis-
carded buff ers are freed. So, as with all data structures that allocate memory,
caution must be exercised when working with dynamic arrays. Dynamic ar-
rays are probably best used during development, when you are as yet unsure
of the buff er sizes you’ll require. They can always be converted into fi xed size
arrays once suitable memory budgets have been established.)
5.3.4.3. Linked Lists
If contiguous memory is not a primary concern, but the ability to insert and
remove elements at random is paramount, then a linked list is usually the data
structure of choice. Linked lists are quite easy to implement, but they’re also
quite easy to get wrong if you’re not careful. This section provides a few tips
and tricks for creating robust linked lists.
The Basics of Linked Lists
A linked list is a very simple data structure. Each element in the list has a
pointer to the next element, and, in a doubly-linked list , it also has a pointer to
the previous element. These two pointers are referred to as links. The list as a
whole is tracked using a special pair of pointers called the head and tail point-
ers. The head pointer points to the fi rst element, while the tail pointer points
to the last element.
Inserting a new element into a doubly-linked list involves adjusting the
next pointer of the previous element and the previous pointer of the next ele-
ment to both point at the new element and then sett ing the new element’s next
5.3. Containers