As far as my experience goes, there are two ways to implement a world space.
note: feature means an object with which your player may collide with. A feature can be a wall, a monster, a bullet...
Per unit of space
Usually the choice for 2D games. You make a grid out of your world, where each square (or triangle, hexagon, or whatever you wish) can be as large as a tile, down to a single pixel (or even less if you want). A value in the grid determines how to act when the player collides with a given location (commonly 0 for no-collision and 1 for collision). Collision detection is O(1), and memory usage is O(w*h) where w and h are the width and height of your space respectively; regardless of whether or not there are features in it. Data structure is as simple as a 2-dimensional array.
Usually the choice for 3D games. You have a set of features, and collision detection is performed per-feature. There are interesting data structures, such as KD-trees, that help you determine which features are likely to be in a collision with the player, so you don't have to check it for every single object. Collision detection is non-trivial, and is O(n), for n features, and memory usage is O(n) as well. Data structure is a list, tree or dictionary that lets you do lookup by x,y,z location.
However, per-feature is also used in 2D (or pseudo 3D). Take for instance old shooters. Walls can be implemented as lists of line segments, which is a simple variant of the per-feature technique.
Dynamic feature placement is possible with both techniques. In the first technique, you simply modify your array during execution. Set an element in the grid from 0 to 1, and bam! you have a wall where you didn't before. In the second technique, just add a feature to your features list, and you're ready to go.