<p>Is there a canonical name for the following data structure for list of lists?</p>

<p>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.</p>

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

<p>$Q = [a_0,\dots,a_n,b_0,\dots,b_m,c_0,\dots,c_o,d_1,\dots ]$</p>

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

<p>An instance of this idea is the compressed sparse rows format for sparse matrices</p>

<p><a href="http://en.wikipedia.org/wiki/Sparse_matrix#Compressed_sparse_row_.28CSR_or_CRS.29" rel="nofollow">http://en.wikipedia.org/wiki/Sparse_matrix#Compressed_sparse_row_.28CSR_or_CRS.29</a></p>

<p>I would like to know a proper for the general idea.</p>

CC BY-SA 3.0
2012-08-07T23:58:09.190Z
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.
Jeffε
CC BY-SA 3.0
2012-08-08T01:05:22.003Z
Well, linked lists are straight-forward, too.
shuhalo
CC BY-SA 3.0
2012-08-08T01:29:15.313Z
List of list could be called a composite/higher order data structure because the list so formed is `composed` of simple lists. But i'm not sure.
A. K.
CC BY-SA 3.0
2012-08-08T02:59:07.463Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-08T05:10:10.453Z
@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.
Neel Krishnaswami
CC BY-SA 3.0
2012-08-08T07:28:44.750Z
@Neel, you can post your comment as an answer. :)
Kaveh
<ds.data-structures><terminology>
Name this list-of-lists data structure
shuhalo
# Name this list-of-lists data structure

(Asked by: username_0 on 2012-08-07)

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.

**Tags:** ds.data-structures, terminology
> **Comments:**
> **username_1**: 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.  
> **username_0**: Well, linked lists are straight-forward, too.  
> **username_2**: List of list could be called a composite/higher order data structure because the list so formed is `composed` of simple lists. But i'm not sure.  
> **username_3**: 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.  
> **username_4**: @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.  
> **username_5**: @Neel, you can post your comment as an answer. :)  

---

## 0 answers

