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


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

  • 3
    $\begingroup$ 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. $\endgroup$
    – Jeffε
    Aug 7 '12 at 23:58
  • 1
    $\begingroup$ Well, linked lists are straight-forward, too. $\endgroup$
    – shuhalo
    Aug 8 '12 at 1:05
  • 2
    $\begingroup$ I would not be surprised if this data structure does not have any standard name. It is straightforward as JɛffE said, and it is not super-important like linked lists. $\endgroup$ Aug 8 '12 at 2:59
  • 3
    $\begingroup$ @JɛffE: "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. $\endgroup$ Aug 8 '12 at 5:10
  • 1
    $\begingroup$ @Neel, you can post your comment as an answer. :) $\endgroup$
    – Kaveh
    Aug 8 '12 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.