// thinkbeforecoding

Data Structures and Algorithms

2008-12-24T11:05-06 / jeremie chassaing

I had a peek through Jon Skeet’s blog this morning at a free eBook called Data Structures and Algorithms by Granville Barnett and Luca Del Tongo.

The book is clear and presents the usual linked lists, trees, sets structures in a concise yet precise way.

There’s something new I had not seen in other algorithm books before. The algorithms are written in pseudo code, but there is a chapter about unit testing your implementation.

If the writers read this, I just would like to share a little tricks that make linked list algorithms easier to write..

Linked list algorithms are always bloated with tests like this :

        if (head == null)

            head = ...;

        else

            node->Next = ...;

Actually the content of head and then content of node->Next are both pointers on next node. But the way to reference those two locations is different, ending in a lot of if statements.

If the language supports reference variables or pointer, you can use a double pointer to hold the current position :

Node** next = &head;

This way there is no more difference between the head (*next) and nodes Next pointers. The little tricky thing is to move to next location :

next = &((*next)->Next);

With this you can consider every ‘Next’ pointer including head as equivalent. No more if statement !

By the way, I was trying to find out how to do this on C#, but is it possible without going unsafe ?