Title: Pointers in Hyperspace

Often things make more sense, or become easier to handle, in more dimensions. As a simple example, imagine taking a linked list and having to put each item in one of a number of sub-lists according to some criterion. If you imagine the list as a one-dimensional line of boxes with arrows pointing from one to the next (if you're Western it will probably be left to right), perhaps you'll first think of iterating through it and copying each item to the appropriate sub-list. If, though, you introduce another dimension and imagine folding the line at appropriate points, so each item is at a vertical position appropriate to its criterion (the pointers still point straight to the right), it's easier to think of code that does the job by only changing the pointers:

#include <stdlib.h>
typedef int /* or whatever */ T;
typedef struct Node {
  T* data;
  struct Node* next;
} Node;
int f(T* n);
void splitList(Node* list, Node** firsts, int numFirsts) {
  int i; Node** last = (Node**)malloc(sizeof(Node*)*numFirsts);
  for(i=0; i<numFirsts; i++) firsts[i]=NULL;
  while(list) {
    int x=f(list->data);
    if(firsts[x]) last[x]->
                next=list; else firsts[x]=list;
    last[x]=list;
    list=list->next;
  }
  for(i=0; i<numFirsts; i++)
           if(firsts[i]) last[i]->next=NULL;
  free(last);
}

This code is written less clearly than I'd like for space. It destroys the original list but does not require nearly so much temporary memory, and depending on the application it could be better.

In this example a new algorithm became obvious by moving from one dimension to two. You might have been able to think of it anyway, but systematic methods help when data structures become more complicated. When imagining data structures, many would naturally think of a two-dimensional diagram featuring objects, with attributes and pointers to other objects. Computer memory is actually one-dimensional (at least in organisation; I'm not talking about hardware details here), but thinking of the data structures in a two-dimensional way helps them to make more sense.

Depending on the data structure, thinking of it in three or even more dimensions might help. This should not be just dismissed on the grounds that two would be adequate for representing it, since we have already seen the benefits of thinking in two dimensions when in fact one would do. Considering more dimensions may make certain algorithms become apparent when they were not obvious before, particularly when the task involves transforming one data structure into another of a completely different form, as many of these can be considered geometrically.

The strength lies in the fact that algorithms follow naturally from geometric transformations. If you have a very complicated data structure that you want to transform, and you can describe the form it's in now and the form you want it in, if you use enough dimensions you can consider the transformation geometrically and then almost read off the code. This is better than sitting in front of a blank page wondering what sort of algorithm to write.

The general case is to consider data structures in as many dimensions as it takes. You don't have to actually imagine hyperspace as long as you know its properties, such as each dimension is orthogonal to all the others (this is the property we are interested in), but if you really want to imagine it then the first mistake is to try to visualise it. Sighted people often find it hard to imagine in more than three dimensions because their conjecture of space is visual in nature. This means that, when they try to think in hyperspace, they usually take a cross-section through it and hold the other dimensions constant, or use some other method of projection. This can work if you always understand which cross-section you're looking at, but it could compromise the ease of understanding that extra dimensions give. But we were all born blind and are all capable of imagining space in ways that are not visual (for example, you probably know the position your body is in without having to think visually). If you can break the visual habit, extra dimensions, while still not natural, become easier.

How many dimensions does it take? This depends on the structure. If an entity has a number of pointers, try imagining that they all go off in orthogonal directions, as this enables you to manipulate one dimension independently of the others. Be careful, though, otherwise a binary tree turns into a lattice with coinciding nodes! This is easily solved by roping in another dimension and giving each object its own place along it (as in the machine address), although there is limited use in applying this to something as simple as a binary tree anyway.

In this way, many operations can be described quite simply as croppings (slice off the part of hyperspace you don't want), reflections (or, equivalently, rotations through another dimension), projections (to lose information or to multiplex), foldings (to demultiplex), and other transformations. And of course don't be afraid to introduce extra dimensions when adding information to the structure, as in folding the linked list.