It is possible that a patent covers a data structure, but it has to be tied to a computer-readable medium and structurally and functionally interrelated to that medium.
The USPTO makes a distinction between "functional descriptive material" and "nonfunctional descriptive material." a data structure is a type of functional descriptive material, provided that it imparts some functionality. Nonfunctional descriptive material includes things like music and literary works. So, for example, you can't get a patent on a book, or a plot device - that is nonfunctional descriptive material.
You can, however, patent functional descriptive material if you tie it to a computer-readable medium. The case In re Lowry, 32 F.3d 1579 (Fed. Cir. 1994) held that a claim to a data structure stored on a computer readable medium that increased computer efficiency was statutory. However, the case In re Warmerdam, 33 F.3d 1354 (Fed. Cir. 1994) held that a claim to a data structure alone was not patentable subject matter. You can read a nice summary of all of this in the USPTO's Manual of Patent Examining Procedure (MPEP) in section 2106 (http://mpep.info/2100_2106). This area of patent law (patentable subject matter) is a hot topic right now, so watch for changes and new developments.
The practical take away is that you can't just conclude that the data structure is unpatentable and thus isn't covered by a patent. If you're very worried, you can search to see if the particular data structure is patented or read the terms and conditions associated with use of the data structure (what you're doing may be permitted, and developers may be given a license to use the data structures).
As to trademarks, I wouldn't worry about that. Trademarks are used to identify a brand to consumers; they deal with the source of the goods. I can't image a scenario in which a court determines that a functional data structure is a valid trademark.
I hope this helps.