What data structures can efficiently store 2-d "grid" data?

Question

I am trying to write an application that performs operations on a grid of numbers, where each time a function runs the value of each cell is changed, and the value of each cell is dependent on its neighbours. The value of each cell would be a simple integer.

What would be the best way of storing my data here? I've considered both a flat list/array structure, but that seems ineffective as I have to repeatedly do calculations to work out which cell is 'above' the current cell (when there is an arbitrary grid size) and nested lists, which doesn't seem to be a very good way of representing the data.

I can't help but feel there must be a better way of representing this data in memory for this sort of purpose. Any ideas?

(note, I don't think this is really a subjective question - but stack overflow seems to think it is.. I'm kinda hoping there's an accepted way this sort of data is stored)

Answer 1

Here are a few approaches. I'll (try to) illustrate these examples with a representation of a 3x3 grid.

The flat array

+---+---+---+---+---+---+---+---+---+ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | +---+---+---+---+---+---+---+---+---+  a[row*width + column] 

To access elements on the left or right, subtract or add 1 (take care at the row boundaries). To access elements above or below, subtract or add the row size (in this case 3).

The two dimensional array (for languages such as C or FORTRAN that support this)

+-----+-----+-----+ | 0,0 | 0,1 | 0,2 | +-----+-----+-----+ | 1,0 | 1,1 | 1,2 | +-----+-----+-----+ | 2,0 | 2,1 | 2,2 | +-----+-----+-----+  a[row,column] a[row][column] 

Accessing adjacent elements is just incrementing or decrementing either the row or column number. The compiler is still doing exactly the same arithmetic as in the flat array.

The array of arrays (eg. Java)

+---+   +---+---+---+ | 0 |-->| 0 | 1 | 2 | +---+   +---+---+---+ | 1 |-->| 0 | 1 | 2 | +---+   +---+---+---+ | 2 |-->| 0 | 1 | 2 | +---+   +---+---+---+  a[row][column] 

In this method, a list of "row pointers" (represented on the left) each is a new, independent array. Like the 2-d array, adjacent elements are accessed by adjusting the appropriate index.

Fully linked cells (2-d doubly linked list)

+---+   +---+   +---+ | 0 |-->| 1 |-->| 2 | |   |<--|   |<--|   | +---+   +---+   +---+  ^ |     ^ |     ^ |  | v     | v     | v +---+   +---+   +---+ | 3 |-->| 4 |-->| 5 | |   |<--|   |<--|   | +---+   +---+   +---+  ^ |     ^ |     ^ |  | v     | v     | v +---+   +---+   +---+ | 6 |-->| 7 |-->| 8 | |   |<--|   |<--|   | +---+   +---+   +---+ 

This method has each cell containing up to four pointers to its adjacent elements. Access to adjacent elements is through the appropriate pointer. You will need to still keep a structure of pointers to elements (probably using one of the above methods) to avoid having to step through each linked list sequentially. This method is a bit unwieldy, however it does have an important application in Knuth's Dancing Links algorithm, where the links are modified during execution of the algorithm to skip over "blank" space in the grid.