Half-Edge Data Structure with holes
The cube-like mesh shown in the images is a non-manifold mesh. Officially half edge data structures do not support such a topology. However, this case can be supported by continuing the boundary half edges through the non-manifold node. This is apparently the way it is done in 3DS Max, and also Blender. You can look at this article for several extension to the data structure to support non-manifold meshes.