The half-edge data structure, used in computational geometry.

I remember when I first discovered it, it drove home the point that choice of data structure can really matter - it made a bunch of problems I'd been working on much easier to solve, as it gave a different way of looking at things.