What kind of data structure would I use to house an infinite grid?

I need to figure out how to make an infinite board (kind of 开发者_JS百科like what wordsquared.com uses) that can expand on demand without losing the location of objects that are already on the board.

What data structure(s) would I use to create a similar board?

I should also mention that I will need to do location queries, and be able to check the surroundings of a certain point.

---

Use a list. When you add an object to the board, add it to the list. When you remove an object from the board, remove it from the list. This is O(1) for insertion and deletion, which is as fast as it gets. Each object has an (x,y) coordinate.

Or did you have something else in mind? I can only answer the questions that you actually ask...

---

Two ways I can think of off hand:

1. Allocate a pool of nodes each of which has a pointer to the node above, below, to the left and to the right of the current node. Since your board should only grow, you won't have to deal with any ugly deletions. Keep a pointer to the top-left of the board for easy rendering (the traversal is simple and obvious).

2. Allocate a matrix of nodes and use it as-is. When you need to grow your board, allocate a new one and copy the data from the old to the new before deleting it. This will be a bit slow on reallocation, but will make for easy interaction with the board.