Building a Pugly-Linked List

Meet Janie. Janie has an ever-changing menagerie of pugs, and would like to use a data structure to keep track of them. What data structure would be most suitable?

Sad pug
Sad pug image by wikimedia user DodosD. Reused under Creative Commons license.

Janie could keep her pugs in an array, but this isn’t a good choice for several reasons. Arrays are best for collections of constant size, while the size of her menagerie varies. Further, any ordering of the pugs will require re-sorting the array as pugs enter and leave, and without this ordering we lose the benefit of being able to find a given pug in O(1) time by indexing into the array.

Queues and stacks don’t have the constant size problem – we expect them to grow and shrink. However, they’re unsuitable because they define the order in which pugs have to be removed after they’re added; the oldest pug might usually tend to come off the queue first, but not always, and we certainly hope the newest pug won’t be popped off the stack right away.

Consider a linked list, however. A linked list is a data structure in which we have some number of nodes, each of which points to the next node on the list; by maintaining a pointer to the head of the list, we can obtain the rest of the objects by following the next pointers. In a doubly-linked list, each node contains a pointer to the next node and a pointer to the previous node.

We’ll modify this slightly to get a pugly-linked list. The head of each pug (its head pointer) will point towards the previous pug in the list, and the tail of each pug (its tail pointer) will point to the next pug in the list. (Normally, we’d keep one head and one tail pointer, pointing to the first and last elements of the doubly-linked list, while each node would have previous and next pointers…but we’ll abuse the terminology a bit to make it pug-specific). If the tail pointers are curly this will, naturally, give us a circular list.

If we need to find a specific pug, we can iterate through the list, which is the same thing we’ll need to do with an unsorted array – but we won’t have any empty cells from missing pugs. We just look at the first pug and follow the tail pointers until we find the pug we want. We can add pugs in constant time – just set its head to point in the same direction as the first pug’s head, set its tail to point at the first pug, and set the first pug’s head to point the new pug, which has now become the first pug in this pugly-linked list. We can remove pugs (provided we have a pointer to them) in constant time as well, by updating the next and previous pugs to point at each other rather than the pug being removed.

And this is how Janie can keep track of all her pets with a pugly-linked list.