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}$$UpdateThe 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.
Algorithm: Dimension increase in 1D representation of Square Matrix
algorithms;matrices
There is a simple solution, but it requires a different 1Drepresentation of your matrix $M$. You suppose it is stored in anarbitrarily 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]$ isstored 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 increasedmatrix 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 newlayer at the end, i.e. add the representation of the last row and last columnat the end of the used part of array $A$. The cost is linear in $m$.ExplanationThe initial version of the question asked for a linear data structure,without explicitly allowing for linked-lists, which I do not considermore linear than anything else, the memory having generally a linearaddress space. Hence I assumed the idea was to use, as efficiently aspossible, a one dimensional array $A$, without trying to mimic pointers.I started looking for an efficient way to store (and retrieve) theelements $M(i,j)$ of the matrix $M$ in $A$, so that extending thematrix with an extra dimensional layer for the highest values of theindices, could be done cheaply ... the cheapest being to add the newlayer right at the end of the existing matrix, so that the cost wouldbe no more than the number of elements to be copied.To do that, while keeping a uniform indexing scheme requires to havedone it uniformly, starting from the $1\times 1$ matrix. The questionbeing somewhat imprecise regarding constraints, I assumed that keepingeach line in one contiguous piece is not really required.The placement of the elements of matrix $M$ in the linear array $A$ isillustrated by the above $3\times 3$ matrix, where each element hasthe 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 theupper-lefmost submatrix of $M$ of size $p$ is independent of the restof the matrix $M$. The element $M(i,j)$ is either on the rightmostcolumn of that submatrix if $i\leq j$, or on its last line otherwise.Furthermore, the first $(p-1)^2$ elements of array $A$ are alreadyused to store the upper-left submatrix of size $p-1$. One uses thenext $2p-1$ elements of the $p^{th}$ row and $p^{th}$ column, whichcontain element $M(i,j)$. This can be done in different ways, and theproposed formula stores these $2p-1$ elements in top-down andright-to-left order.Note: the first version of the formulae used $p=max(i,j)$ explicitly tocompute the squares, a remnant of my initial search for asolution. 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 representationOne characteristic of this representation is that it preserves random access (access time is constant and independent of indices andmatrix size), which is not usually the case with listrepresentations. However it does not requiremultiplication for indexing the array $A$, since only addition andinteger squares are needed. Integer squares can be memorized in alinear array, or can be computed with addition only if successivesquare values are needed in a loop, for example to read a line or acolumn of the matrix, using the formula $(p+1)^2=p^2+2p+1$.But, as usual, the usefulness of such a representation is highlydependant 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 moreeffective than most pointer based representations for two reasons:given $i$ an $j$, it allows access of element $M[i,j]$ in constanttime;it has no overhead in space for storing pointers (not to mentionpossibly greater garbage collection costs).However, the last statement is not completely true. We chose to use anarray $A$ of sufficient length because that initially (in the firstversion of the question) seemed a given constraint. But, if we relaxthat constraint, it is clear that it is a costly solution in spacesince the array $A$ must have a size sufficient to store the largestversion of the matrix $M$ that may be used.Actually, there is something absurd about the solution presentedabove, if it is to be more than an intellectual exercise (but the context andmotivations of the question were not given). If the array$A$ has the maximum size that will ever be needed, why not simply codethe maximum sized matrix in it, and use at any time only the indicesthat are actually needed, given the current matrix size $m$?Since pointers are (now) allowed, this is a good motivation forattempting to get the benefits of the solution presented above, without itsabsurd drawback.The idea is quite simple: keep the layer structure presented above,but store the layers separately, rather than contiguously in the samearray.So a matrix $M$ of size $m$ is implemented as $m$ arrays $L_p$ with $1\leqp\leq m$, each $L_p$ having $2p-1$ elements corresponding to theelements $M[i,j]$ of $M$ such that $max(i,j)=p$.In order to access $M[i,j]$, one only has to compute $p=max(i,j)$ tolocate $L_p$, and then index appropriately with $i$ or $j$ inside$L_p$ to get the right element. Actually, as in the first algorithmabove, it may be faster just to have two cases based on a comparisonbetween $i$ and $j$.  I do not get into the detailed formulae, thatare somewhat obvious to work out.However this require an extra structure to find a pointer to $L_p$when $p$ is known.Three obvious ideas come to mind:The first idea is to use an array of links to the $L_p$ layers,which is indexed by $p$. The drawback is that the size of the array must bethe maximum possible value for $m$, but that is not as bad as themaximum values for $m^2$. The advantage is that accessing anyelement $M[i,j]$ will still be in constant time.The second idea is to use a linked list, which avoids the constantsize array. However, the list has to be followed sequentially to getthe right layer $L_p$. Hence accessing any element $M[i,j]$ will onthe average be in linear time with respect to the current size$m$. Note that, with this solution, it is better to access the listfrom the end corresponding to the largest value of $p$. Firstly, thatis where layers are added or removed. Secondly, assuming that allelements of $M$ have equal chance of beeing accessed, theprobability of finding an element in layer $L_p$ is proportional to$(2p-1)/m^2)$, hence a higher probability for higher values of $p$.Indeed, accessing the list from the higher value of $p$ is onaverage twice as fast as accessing from the lower values of $p$(proof left as an exercise). But access is linear in $m$ in bothcases.In order to reduce access time, the accessing structure can be abalanced tree. The size of the tree is linear in $m$, as it is witha simple list, but the time complexity of finding the right $L_p$ isnow logarithmic in $m$, hence also for accessing an element$M[i,j]$. While building this balanced tree, it is better to give toeach $L_p$ a weight proportional to $2p-1$ to account for itsprobability of being the right layer. However, I have not checkedhow much of a difference it makes.But actually, trying to build a sophisticated balanced tree isprobably self-defeating sophistication, because it may have to bemaintained, and it may require more computation to be explored.  Abetter solution is probably a widely branching tree that is walkedvery simply by indexation.Using a tree of indexing arrays(I have no idea whether this has an official name in textbooks)The nodes of the tree are arrays of length $2^d$, so that we can builda balanced tree with nodes of degree $2^d$. The leaf nodes are arraysof pointers to matrix layers, and the other nodes are arrays ofpointers to other arrays (or nothing).  Without going into details,given a layer number $p$, The binary representation of $p$ is cut intochunks of size $d$ which are used as indices for the arrays whilewalking down the tree to find the layer $L_p$. With a value for $d$ of3 or 4, this should give simple and fast access for matrices ofsignificant size.