> Its possibly the most commonly used data structure, and I doubt they would add the overhead of another set of methods on each instance.

Unless I'm grossly mistaken, Python methods add basically no per-instance overhead (they add per-class overhead.)