Sorry if this is an insultingly obvious concept, but it's something I haven't done before and I've been unable to find any material discussing the best way to approach it.

I'm wondering what's the best data structure for holding a 2D grid of unknown size. The grid has integer coordinates (x,y), and will have negative indices in both directions.

So, what is the best way to hold this grid? I'm programming in c# currently, so I can't have negative array indices. My initial thought was to have class with 4 separate arrays for (+x,+y),(+x,-y),(-x,+y), and (-x,-y). This seems to be a valid way to implement the grid, but it does seem like I'm over-engineering the solution, and array resizing will be a headache.

Another idea was to keep track of the center-point of the array and set that as the topological (0,0), however I would have the issue of having to do a shift to every element of the grid when repeatedly adding to the top-left of the grid, which would be similar to grid resizing though in all likelihood more frequent.


  • 5
    Is the grid sparse or dense? If it's sparse, use a dictionary with the XY coordinate pair as a key; see stackoverflow.com/questions/11837139/…. If it's dense, write a new data structure having an indexer that routes negative indexes into a different list. Commented May 27, 2014 at 22:45
  • Does unknown mean unknown until creation or may expand infinitely in any direction?
    – Blrfl
    Commented May 28, 2014 at 11:53
  • Dictionary would be easy. Commented May 28, 2014 at 19:52
  • @Blrfl starts small and may expand infinitely Commented May 28, 2014 at 23:56

2 Answers 2


Write a new data structure having an indexer that routes negative indexes into a different list.

public class PositiveNegativeList<T>
    List<T> PositiveList;
    List<T> NegativeList;

    public PositiveNegativeList()
         PositiveList = new List<T>();
         NegativeList = new List<T>();

    public T this[int index]
            if (index < 0)
               return NegativeList[index * -1];
               return PositiveList[index];

            if (index < 0)
               NegativeList[index * -1] = value;
               PositiveList[index] = value;

    public void Add(T item)

Code now tested. Note that nothing is ever as simple as it should be; you will need an Add() method of some kind to get new items into the Lists.

  • There's no need to use Activator. It is perfectly valid to use new List<T>(); within the constructor. The casts are unnecessary as well.
    – Dan Lyons
    Commented May 28, 2014 at 17:41
  • @DanLyons: Are you sure? I don't think that compiles; the List<T> constructor expects a declared type, like string. I do think you're right about the casts, though. Commented May 28, 2014 at 17:42
  • Yeah, the declared type is coming from the type parameter on the class definition. I tossed it into a quick console project to confirm. The only change I had to make was replacing this(int index) with this[int index].
    – Dan Lyons
    Commented May 28, 2014 at 17:47
  • @DanLyons: I'm hobbled by the fact that my IDE is on a different computer than my Internet (for security reasons). Commented May 28, 2014 at 17:48
  • Shouldn't that Activator note be removed now that the code doesn't use it?
    – svick
    Commented May 28, 2014 at 19:46

I am going to start by assuming that you know how to create a grid with X indices 0 to xmax and Y indices 0 to ymax.

If the bounds of your indices are xlower to xupper and ylower to yupper, then you have to map indices in this range to indices in the first range.

If indices in the first range are x1 and y1, and the indices in the second range are x2 and y2, then:

x1 = x2 - xlower;
y1 = y2 - ylower;

Now you have indices that can be used in a regular grid.

This sounds so simple, I am wondering whether I missed some important details.

  • Thanks for your response. The grid is expected to be expanded during runtime. Using this solution would mean that adding to the "top left" of the grid would require that the grid be both shifted and less frequently expanded also. Do you think that a multiple grid approach would be better? (no shift required) Commented May 28, 2014 at 23:46
  • @TheSecretImbecile, What data structure are you thinking of using for the grid?
    – R Sahu
    Commented May 29, 2014 at 23:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.