What tile storage structure to use on a side scroller?

I am developing a 2d side scroller in slick2d which i would like to be tile based, but I don't really know how to store the tiles. My game has infinite dynamicly generated terrain and is interactable (a bit like a mix of minecraft and terraria). I am currently using a

Map < Integer, Map < Integer, Tile > >

object but it doesn't seem right because I need dynamic world loading and generation. I am using JBox2d for physics.

Is there any better way to store the data in a more efficient way because only a portion of the world is supposed the be loaded because the world size can become infinitly big

Solution

You should take a look at the cunk-approach (There's a good reason games like Minecraft have chunks). Select a chunk size (for example 8x8) and create a Chunk data structure (class). Inside the chunk, you can store the static tiles inside a normal Array[][] if possible (faster), or, if needed, in an ArrayList.

public class Chunk
{
   private int xPosition;
   private int yPosition;

   private Tile[][] staticTiles;
   private ArrayList<Tile> dynamicTiles;

   ...

   public boolean isInRenderRange()
   {
       ... 
   }

   public boolean isInUpdateRange()
   {
       ...
   }

   ...
}

Then you can go ahead and create the Level data structure. I would recommend something like a basic ArrayList where you can just add and remove elements as you which. You can just iterate over all elements (chunks) in your update and render methods and check for isInRenderRange() and isInUpdateRange().

This will give you the benefit of not having to deal with very complex data-structures like multi-linked lists. You can just change each chunks x- and yPosition when moving backwards, forwards, upwards or downwards. Each tile inside the chunk should have a reference to the chunk they are in in order to get their absolute position.

If you have huge loads of chunks you can sort the ArrayList once in a while to make use of branch-prediction in the extensive render and update calls.