Circular Linked List

Point the head at the tail.

Useful for implementing a queue which receives really heavy traffic; instead of dropping the head of the line and creating a new node for the tail, you use the head as the new tail.

This helps quite a bit if garbage collection / object allocation was a significant speed hit, but it has its drawbacks:

1. You need to think hard about whether or not an overflow or underflow is possible, because you wont get a null pointer exception or anything like that by default... you'll simply overwrite still valid data, or read stale data. This is bad. This is really bad. Mainly because whatever is read was, or will be, at some point valid, making stack traces further down the line (and even debugging attempts) quite confusing. Getting the head/tail checking right can be a bit tricky...

2. Resizing a simple queue is trivial. Resizing a linked list less so. More references to update, more opportunities to screw up. And more subtle tests to miss.

I don't get it... resizing a linked list seems pretty straightforward to me.

Normally, that's true. However, the author seems to be really into low-level performance-oriented details, so the implementation the author is considering may be very complicated. The author may want to avoid using a DoubleLinkedList, for example, or may be concerned about concurrency issues (resizing it without locking the whole thing or invalidating any iterators, for example).

Okay, that makes some sense. Because otherwise I'd say pick a Container package for the circular linked list and move on to something a little more worth your time, fella.

Hmm.... That's a bit presumptuous, especially the "fella" part. But I digress.

Another use for circular lists is in GUI implementations. Most folks think of a graphical environment as a tree, since objects are contained within other objects, ad nauseum. However, it may prove more conceptually elegant to express hierarchies as circular lists. For example, in PC/GEOS, objects were arranged in this manner, as they were also in GEM. The idea being, given any reference to a widget, you can always find its root object by just following the list. For example, when trying to find the smallest enclosed widget corresponding to a mouse click, you want to start searching with the leaves first. Using a circular list for this allows this search to occur in constant space. --SamuelFalvo?

CategoryDataStructure