Algorithm: Dimension increase in 1D representation of Square Matrix

Consider the matrix with dimension $m \times m$:

$$
M =
\begin{array}{cc}
1 & 1 & 1 \\
0 & 1 & 1 \\
1 & 0 & 1 \\
\end{array}
$$

Its 1-D representation:
$$ M^* = \begin{array}{cc} 1 & 1 & 1 && 0 & 1 & 1 && 1 & 0 & 1\end{array}$$

Now, another dimension added, so that the matrix becomes:

$$
N =
\begin{array}{cc}
1 & 1 & 1 & 0 \\
0 & 1 & 1 & 0 \\
1 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
\end{array}
$$

$$ N^* = \begin{array}{cc} 1 & 1 & 1 & 0 && 0 & 1 & 1 & 0 && 1 & 0 & 1 & 0 && 0 & 0 & 0 & 1\end{array}$$

Update

The data structure can be any linear data structure (Array, Single LL, Double LL) not necessarily contiguously linear. The goal is to dynamically add or remove dimensions from the Matrix with least number of operations.

The best I can think of is to repopulate $N^*$ in $\theta(N^2)$ every time a new dimension is added.

There is a simple solution, but it requires a different 1D
representation of your matrix $M$. You suppose it is stored in an
arbitrarily long 1D array $A$, so that new elements can be added.

Then the elements of the matrix $M$ are stored such that: $M[i,j]$ is
stored in $A[k]$ with $k=(j-1)^2+i$ if $i\leq j$ and $k=i^2-j+1$
otherwise.

Other similar formulae are also possible.

The idea is to stores in order the successives layers of increased
matrix size starting with the $1\times 1$ matrix.

Storing order of a $3\times3$ matrix is described here, each element of the matrix being its index in $A$. The first index $i$ is the line index of matrix $M$ representation:


1 2 5

4 3 6

9 8 7

When you increase the size $m$ of the matrix, you only have to add the new
layer at the end, i.e. add the representation of the last row and last column
at the end of the used part of array $A$. The cost is linear in $m$.

Explanation

The initial version of the question asked for a linear data structure,
without explicitly allowing for linked-lists, which I do not consider
more linear than anything else, the memory having generally a linear
address space. Hence I assumed the idea was to use, as efficiently as
possible, a one dimensional array $A$, without trying to mimic pointers.

I started looking for an efficient way to store (and retrieve) the
elements $M(i,j)$ of the matrix $M$ in $A$, so that extending the
matrix with an extra dimensional layer for the highest values of the
indices, could be done cheaply ... the cheapest being to add the new
layer right at the end of the existing matrix, so that the cost would
be no more than the number of elements to be copied.

To do that, while keeping a uniform indexing scheme requires to have
done it uniformly, starting from the $1\times 1$ matrix. The question
being somewhat imprecise regarding constraints, I assumed that keeping
each line in one contiguous piece is not really required.

The placement of the elements of matrix $M$ in the linear array $A$ is
illustrated by the above $3\times 3$ matrix, where each element has
the value of its index in $A$.

This organization is such that the index in $A$ of an element $M(i,j)$
of the matrix $M$ does not depend on the size of $M$, but only on $i$
and $j$. Taking $p=max(i,j)$, the placement in $A$ of the
upper-lefmost submatrix of $M$ of size $p$ is independent of the rest
of the matrix $M$. The element $M(i,j)$ is either on the rightmost
column of that submatrix if $i\leq j$, or on its last line otherwise.
Furthermore, the first $(p-1)^2$ elements of array $A$ are already
used to store the upper-left submatrix of size $p-1$. One uses the
next $2p-1$ elements of the $p^{th}$ row and $p^{th}$ column, which
contain element $M(i,j)$. This can be done in different ways, and the
proposed formula stores these $2p-1$ elements in top-down and
right-to-left order.

Note: the first version of the formulae used $p=max(i,j)$ explicitly to
compute the squares, a remnant of my initial search for a
solution. But @WeaklyTyped remarked rightly that the test comparing
$i$ and $j$ does the job, allowing to replace $p$ by $i$ or $j$,
according to the test result.

Actual use of the representation

One characteristic of this representation is that it preserves random access (access time is constant and independent of indices and
matrix size), which is not usually the case with list
representations. However it does not require
multiplication for indexing the array $A$, since only addition and
integer squares are needed. Integer squares can be memorized in a
linear array, or can be computed with addition only if successive
square values are needed in a loop, for example to read a line or a
column of the matrix, using the formula $(p+1)^2=p^2+2p+1$.

But, as usual, the usefulness of such a representation is highly
dependant on the operations needed and their frequency.

Note: this representation was found independently, but it may have been used before. Pointers to the literature are welcome.

A better solution with pointers

(Added July 1st 2014, after the answer was accepted)

The layer approach described in the previous algorithm seems more
effective than most pointer based representations for two reasons:

-
given $i$ an $j$, it allows access of element $M[i,j]$ in constant
time;

-
it has no overhead in space for storing pointers (not to mention
possibly greater garbage collection costs).

However, the last statement is not completely true. We chose to use an
array $A$ of "sufficient" length because that initially (in the first
version of the question) seemed a given constraint. But, if we relax
that constraint, it is clear that it is a costly solution in space
since the array $A$ must have a size sufficient to store the largest
version of the matrix $M$ that may be used.

Actually, there is something absurd about the solution presented
above, if it is to be more than an intellectual exercise (but the context and
motivations of the

StackExchange Computer Science Q#27627, answer score: 6