2
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 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ε
    Commented Aug 7, 2012 at 23:58
  • 1
    $\begingroup$ Well, linked lists are straight-forward, too. $\endgroup$
    – shuhalo
    Commented Aug 8, 2012 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$
    – Tsuyoshi Ito
    Commented Aug 8, 2012 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$
    – Neel Krishnaswami
    Commented Aug 8, 2012 at 5:10
  • 1
    $\begingroup$ @Neel, you can post your comment as an answer. :) $\endgroup$
    – Kaveh
    Commented Aug 8, 2012 at 7:28

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.