Tiles Data Structure

Currently I am setting things up in GameLogic and StageMap classes so I can have the tiles entity shows up according to the specified XML file.
It brings me to the design issues with the data structure storing the tiles. There are several possibilities I can think of currently:

1. Using array: use an array, and each tile keep track of it's position.
2. Using double array: use a double array to represent the position of each tile.
3. Using "Link": each tile has a pointer to the tile next to it.

I might end up using combinations. Perhaps what I need to do is try to implement the feature (tile setup, multiple set of tile, randomizing, fusing, collision detection), and using search function (GetTile(X, Y)...etc) to access the tile, regardless of the data structure I am using. Then improve the data structure to minimize the access cost. I think that will minimize the change I have to make, also leave room for possible improvement.