The Ginger Mumbly

For a while I was playing with the idea of improving my coding skills by improving my visualisation skills. I had this idea that people who were good coders (and I have known a few) are good visualisers. Note, this is very different from thinking that you can make programming easier by making it easier because you have to able to manipulate these visual images in programmatic ways that are very hard to do visually.

So, on the train yesterday, on the way to London, I sat down and tried to imagine what the answer to the reversed linked list problem might be (yes, after a few years, it's still smarting). I was surprised that the answer that I came up with was a recursive one. I'll try to explain what I was thinking. See if it works for you.

OK, first of all, you have to understand what a linked list is. A link list is a set of storage places, each of which has an address - like a phone number. The way you deal with a list is that you're given a pointer to its head which is like being given the first storage space. In my head I image each item on the list to be a barrel that has it's address embossed into the wood (that can't change) next to the embossed address is the address of the next item in the list - you can change that so it's written on a post-it note pad. If you follow the addresses written on the post-it notes the trail will lead you from barrel to barrel until finally you reach a barrel which has the post-it note with "NULL" written on it. That's the end of the list. Each of the barrels - the items in the list - have contents. If I bent over I could see what was in the barrel (each barrel is cut away on one side) but for this exercise, I don't need to know what's inside. So how do I reverse this list?

Well, I look at the address that I've been given for the first barrel. I know because this is the first barrel that in the final, reversed list, it will have to be the last, so the first thing I need to do is write "NULL" on the post-it pad on the first barrel. But hang on, before I do that, I need the address of the next barrel which is already written there. I take the post-it off the top of the pad and stick it to my clipboard. I don't know where I got my clipboard from, but I've got one. Now I write "NULL" on the pristine post-it pad.

Now I know where I'm going and I'm just about to set off when I realise that when I get to the next barrel, I'm going to need the address of this one. So I write the number of this barrel - the embossed number that can't be changed on a piece of paper on my clipboard. And off we go, comparing the number on the barrels with the number on my clipboard.

Now I'm starting to get the hang of this. I know that I'm going to need the number on the post-it pad on the new barrel. So I screw up the old post-it and stick the new one on my clipboard. I write the address I've just come from - the address on the paper on my clipboard - onto the pristine post-it pad. Then I cross that address out and write the address embossed on the barrel. And off we go to the next barrel.

I keep doing the manoeuvres outlined in the last paragraph until I get to a barrel where the post pad has "NULL" written on it. Now I know I'm at the end of the list. I remove the post it note with NULL written on it, write the address from my clipboard on the pristine pad and then write the embossed address from the barrel onto my clipboard. I take this number back to the start (some cloud that I emerged from into these forest of barrels). This is the address of my new reversed linked list.

Oof - is that any help? I'm not sure. After I'd sat and thought that all through on the train, I wrote some pseudo-code and today I wrote it in C. All of that too-ing and fro-ing turns out to only be these 10 lines in C:

List_Pointer reverse_list(List_Pointer next_ptr,List_Pointer list){ List_Pointer temp = (List_Pointer) list->next; list->next = next_ptr; if(temp == NULL) {  return list; } return reverse_list(list, temp);}

This post was influenced by some reading I've been doing recently about ways of improving your memory. I read "How to Develop a Super Power Memory" by Harry Lorayne which is very interesting but doesn't mention "Memory Palaces" which are mentioned in Derren Brown's Trick of the Mind Book. I think you might be able to use some of these methods to get a much better visualisation of the inner workings of a computer programme.

There's some support for this from a quote of Charles Simonyi quoted in Robert X. Cringely's Accidental Empires: "I have to really concentrate, and I might even get a headache just trying to imagine something clearly and distinctly with twenty or thirty components" says Simonyi "When I was young I could easily imagine a castle with twenty rooms with each room having ten different objects in it. I can't do that anymore." Could improving your memory using memory techniques drastically improve your performance as a computer programmer? I don't know, but it's worth trying to find out.