Data Structure isomorphisms Disclaimer: I am not a CS theorist.

Coming from abstract algebra, I'm used to dealing with things that are equal up to a isomorphism - but I'm having a trouble translating this concept to data structures. I first thought that straight up set theoretical bijective morphisms would suffice, but I ran into a wall quite rapidly - those are just encodings and do not capture the computational essence of the data structure.

Is there a more restrictive (but more useful) definition? (Or if not, why?) Is there a canonical definition of category of "constructed data structures"?
There is not a canonical such category, for the same reason there is no canonical category of computations. However, there are large and useful algebraic structures on data structures. 

One of the more general such structures, which is still nevertheless useful, is the theory of combinatorial species. A species is a functor $F : B \to B$, where $B$ is the category of finite sets and bijections between them. You can think of  species as being families of structures indexed by abstract sets of locations. This explains the functoriality over $B$ -- such families have to be invariant with respect to renaming the abstract labels. Then, the calculus of species basically replays generating function methods at the functorial level, to generate sets of data structures instead of counts. 

To see this theory implemented in a programming language, you can read Brent Yorgey's Haskell Symposium paper, Species and functors and types, oh my!. I think Sage also has a species package, though of course it's oriented towards computer algebra rather than programming.