Use Doubly Linked Not Singly Linked Lists

If you're going to write a general use library and use a linked list, please make it doubly linked. I was recently working with the Box2d library which I have to say is a great physics engine. The engine maintains a linked list of what it calls Fixtures attached to each body. While I was trying to use this list I was shocked to find that it was a singly linked list. In other words the list only had a "next" pointer, no previous pointer.

Unless you have a good reason like tail-sharing I really don't see why someone would do that especially in a general opensource library that would be used in a broad range of applications. First off, before we go into the pros and cons of both designs let's briefly talk about linked lists. A linked list is a data structure used to store a group of data objects by connecting objects with a "link". The link is basically a pointer from one object to the next one, previous one, or both. If there's only one link it's called a singly linked list. If there's both a previous and a next link, it's called a doubly linked list. The best part about a linked list is that it's very cheap to add and remove objects. All we need to do is add a new link or remove a link and assign a pointer to a different object. The worst part about a linked list is random access. If we need to access an object that happens to be in the middle of the list, there's no way to reach that object but to traverse through all the objects before it or after it.

When designing software, we're supposed make libraries as flexible and general as reasonably possible. We already know that access is the main weakness of linked lists. The least we can do to make accessing objects a little easier is to make the list a doubly linked one. In the case of linked lists it's easy to see why someone might need to go backwards in a list. But even if it weren't so obvious, if adding something doesn't cost much and it satisfies a common use it should be done in a general purpose type of library.

Looking at the pros and cons of a singly and doubly linked list, it also makes more sense to make them doubly linked. The only pro of using singly linked lists is that it saves memory but all we're saving is a pointer which is about 32 or 64 bits per object. The con is being limited to traverse a list in only one direction. Singly linked lists also make it more challenging to delete objects. The pro of having a doubly linked list is that from any object in the list we can move in either direction. Also it's a lot easier to delete an object in a doubly linked list. The con of doubly linked lists is that we use a little more memory for the second pointer. However the additional memory (32 or 64 bits per object) used is insignificant. In terms of asymptotic notation, we're still using O(n) memory which means our memory usage is linear with respect to the number of objects.

The good news is that I was able to modify the list and make it doubly linked. Take home message: bi-linking = bi-winning.