# Two dimensional matrix-like data type using lists and/or mutable lists

I am trying to think of an implementation of a two dimensional matrix-like data type.
Normally I would take an array of arrays but I'm bound to a relatively low language level which only provides lists and mutable lists, because this is part of (but not an exercise itself, I could simply use an inefficient solution) a software project at university. In this, we are only allowed to use a specific language level.
So of cause I could take a list of mutable lists and, in search of an item in row n and column m, get the m-th mutable list and go throught it until position n. But isn't there a better solution than going through the whole list?

• Do you want just to put/retrieve elements with certain indexes? Are there any other requirements or use cases, like searching by value? Commented Feb 28, 2015 at 12:21
• No, just put/retrieve. Forgot to mention that. Commented Feb 28, 2015 at 12:22
• And one more question: does it have to be constant size or resizable? Like you create it without specifying the size, and then you put elements it just automatically allocates the space. Commented Feb 28, 2015 at 12:26
• The size can stay the same after creation. Commented Feb 28, 2015 at 12:27
• I would think that lists are a higher level language feature. At the lowest level, memory is just a flat set of memory locations that are read/written by specifying the addresses of the locations. 1-d arrays are a fairly simple abstraction over that memory space. Lists are a more complex abstraction beyond arrays.
– poke
Commented Feb 28, 2015 at 14:08

Since you need constant size, and access elements by their indexes, I'd say go with 1-dimensional array of `WIDTH*HEIGHT` size. You can just translate indexes like `matrix[x+y*WIDTH]` or build a wrapper class to do it like `matrix.get(x, y)` - that way you don't have to track width, and you can add boundary checks.
Access by index will have a constant time (`O(1)`) performance.