[robmccoll]

Performance tip (for circular linked lists and linked lists in general): store your list nodes in a dynamically allocated array. Keep freed nodes in an in-place freed list inside the array and in a stack-like structure in-place beyond the part of the array that is currently in use. This cuts down on fragmentation in the memory allocator since you are allocating one larger contiguous chunk of memory instead of many smaller pieces, keeps your data closer together in the memory space to help with cache performance and prefetching, and allows you to switch to array indices instead of pointers. Why array indices? If the data uses indices for its references rather than pointers, sharing it across process memory spaces at different addresses is trivial. It also allows you to serialize the data to disk or the wire without having to perform any changes to the representation.