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.

throw vs throw ex: C# .NET Exceptions

There are a couple options to raise an exception again after it has been caught. One option is to raise the exception again by using the "throw exception" keyword like below:

try 
{
   ...//code that encounters an exception
}
catch (Exception ex)
{
   ...//exception handling code
   throw ex; //raise the exception again
}

The disadvantage in this way is that the original context of the exception is lost. There is no longer a meaningful call stack attached to the exception because it will contain the latest context from the newly added throw. If you plan to throw the exception in this matter you should wrap the original exception into another new more high level (application) exception. The new exception would add more high level info about the original exception.


The second option is to use the throw keyword alone with out passing the actual exception variable. This tells the .NET framework to throw the original exception without updating its context like below:

try 
{
   ...//code that encounters an exception
}
catch (Exception e)
{
   ...//exception handling code
   throw; //notice the exception e is omitted
}

This way should be used when the exception is trivial enough and the code is too small to require wrapping into another exception. Again the advantage here is that you maintain the original call stack so that any user of this code can track the cause of the exception.

It's worth noting that Java is different in this aspect and using "throw ex" in Java will retain the original stack trace.

Nearby Windows Phone 7 Reviews and Maps App

Nearby is a new Windows Phone 7 (WP7) app. The app can be downloaded here from the Windows Phone 7 app store.

Nearby shows the user nearby places automatically upon opening. The user can scroll through the list of nearby places and find more information on a location he is interested in. Information for a location includes phone, address, website, rating, and distance. You can see the directories where the location is found such as Yelp, Yahoo and CitySearch. Using Nearby, you can view the location's page on Yelp and other sources within the app. Browsing to the Yelp or Yahoo page for the business allows you to see reviews and more info.





With Nearby, you can find step-by-step directions to the location you are interested in. You can also navigate through the itinerary steps and see the steps on the map.





Nearby allows you to bookmark your favorite locations so that you can find them easily. You may also share a location with a friend via SMS text or email. Calling a place is as easy as touching the phone icon or phone number after selecting a business.





List of favorite places and businesses for easy access.



Find out more about Nearby at http://www.challengesolutions.net