Good mesh data structures

What sort of application? For example, you need very different mesh structures for in-game rendering than for a modelling tool.

For terrain editor application.

I want to generate triangular meshes as representation of terrain specified by
heightmap input. The mesh generation algorithm used is Data-Dependent Triangulation.

In the later stage, I also want to implement some sort of interface for terrain
deformation (i.e. after generation you can adjust the terrain to make other
features, such as holes, cliffs, caves, etc) so probably need the data structures
which are efficient in merging or splitting faces

How is it?

You should have a look at www.openmesh.org.

CGAL also has a data structure for triangle meshes: http://www.cgal.org/Manual/3.4/doc_html/cgal_manual/packages.html#Part:TriangulationsAndDelaunayTriangulations