With the exception of some aspects in fire bending. All bending abilities in avatar work under the premise of manipulating the {%insert element here} that already exists.
An example of this is in the water benders drawing moisture from the air, or better yet, the way blood bending was explained. It is said to be possible because a persons blood contains water (the bender cannot simply create water from nothing).
This is also why water benders like to carry around waterskins. In earth bending it is less obvious since there is earth everywhere, but there are a number of episodes where they are stranded somewhere away from their element and become somewhat handicapped.
Whether the ground becomes unstable after earth bending would be entirely up to the bender themselves, although I would say there is such a thing as "best bending practices" where they would learn to use the existing earth in a way that doesn't deteriorate the structure.
It does not have to create a mirrored empty space like the image of a puzzle you are imagining, but if the bender wanted to they certainly could! Instead they would perhaps use a smaller depth of the earth spread out across a larger space along the caves wall/floors to create their new earth wall.
This would result in the existing space in the cave expanding, its just unnoticeable because of how spread out it was. The point is that there are soooooo many earth bending styles shown that although we can confirm that they must use existing earth, we can not confirm how any potential bender would use it because everyone bends a little differently! The large wall would indeed require to be made out of existing earth, however as a nation-wide project I would say that it is fairly self explanatory that they would have collected earth from a place that would not make the entire ground unstable.
Edit for linkable reference:
The Prison Rig is a perfect example of this. The fire nation constructed this prison to hold earth benders and the reason it works is because it is made entirely out of metal and is miles away from any rock or earth so the earth benders have nothing to control. Thus, it is canon that earth benders must use the existing earth to control/manipulate. The way they escape this prison Book 1, Episode 6 also confirms this point. The entire reason the last fight I am showing in the picture below was dramatic is because the earth benders had just the small amount of stolen coal to use in their fight.
side note: avatar is no anime :P