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 ?
