# Name this list-of-lists data structure

Is there a canonical name for the following data structure for list of lists?

Suppose we have got a list of length $Z$ of finite lists $[a_0,\dots,a_n], [b_0,\dots,b_m], [c_0,\dots,c_o], \dots$ of the same data type, but with variable length. Then we can represent them in the following way in one single data strucutre.

Let $P = [0,p_1,p_2,\dots,p_Z]$ be a list of integers, and let

$Q = [a_0,\dots,a_n,b_0,\dots,b_m,c_0,\dots,c_o,d_1,\dots ]$

be the concatenation of all list entries. We demand that for all indices $0 \leq z < Z$ we have that the $z$-th list is given by the entries of Q with indices $q$, $P[z] \leq q < P[z+1]$. Note that $P[Z]$ is the total number of elements listed.

An instance of this idea is the compressed sparse rows format for sparse matrices

http://en.wikipedia.org/wiki/Sparse_matrix#Compressed_sparse_row_.28CSR_or_CRS.29

I would like to know a proper for the general idea.

• This data structure is too straightforward to have its own Proper Name. I would probably call it a "flattened array of arrays", but I literally just made that up. Aug 7 '12 at 23:58
• Well, linked lists are straight-forward, too. Aug 8 '12 at 1:05
• I would not be surprised if this data structure does not have any standard name. It is straightforward as JɛﬀE said, and it is not super-important like linked lists. Aug 8 '12 at 2:59
• @JɛﬀE: "flattened arrays" is actually the standard name for it, and they are important. They come up a lot in the theory of nested data-parallel languages -- when automatically parallelizing a program, it's very useful to get rid of indirections (both to improve cache behavior, and to make dividing the work easier). So there's a whole line of work on "flattening transformations" -- taking programs written with nested or recursive data structures and replacing them with flat data structures. Aug 8 '12 at 5:10
• @Neel, you can post your comment as an answer. :) Aug 8 '12 at 7:28