Take the 2-minute tour ×

If I declare a List of char arrays, are they allocated in contiguous memory, or does .NET create a linked list instead?

If it's not contiguous, is there a way I can declare a contiguous list of char arrays? The size of the char arrays is know ahead of time and is fixed (they are all the same size).

share|improve this question
I guess I could declare a List<char> and just manually keep track of the boundary. That would be stored in contiguous memory, right? –  David Sep 8 '13 at 3:37
Yup, that's what I suggested. That's the only way to so this. Just curious; why do you need them to be contiguous and act like one large array in the first place? My thinking is that the jump between arrays won't matter much as it will happen infrequently when compared to the number of jumps occurring between elements when iterating the individual arrays. –  Ed S. Sep 8 '13 at 3:41
It's for an AI class. Non-contiguous data will effect the execution time of the algorithm, and hurt my grade :) –  David Sep 8 '13 at 3:43
I'm going to be hitting the char arrays frequently enough that the performance hit will probably be noticeable. –  David Sep 8 '13 at 3:44
Ok. It just seems like you would lose cache coherence infrequently (in the outer loop) and maintain it most of the time (the inner loop). It depends on the size of the inner arrays, but if they are at all large I bet it wouldn't be noticeable. I would at least test it before complicating your code by using one large array. In fact, if it proves to be a non-issue, I would show your teacher the performance difference. May even get extra credit (I would give it to you, but I'm not your teacher :D ) –  Ed S. Sep 8 '13 at 3:44
show 9 more comments

2 Answers

up vote 9 down vote accepted

Yes, but not in the way that you want. List<T> guarantees that its elements are stored contiguously.

Arrays are a reference type, so the references are stored cotiguously as List<T> guarantees. However, the arrays themselves are allocated separately and where they are stored has nothing to do with the list. It is only concerned with its elements, the references.

If you require that then you should simply use one large array and maintain boundary data.

EDIT: Per your comment:

The inner arrays are always 9 chars.

So, in this case, cache coherency may be an issue because the sub-arrays are so small. You'll be jumping around a lot in memory getting from one array to the next, and I'll just take you on your word about the performance sensitivity of this code.

Just use a multi-dimensional if you can. This of course assumes you know the size or that you can impose a maximum size on it.

Is it possible to trade some memory to reduce complexity/time and just set a max size for N? Using a multi-dimensional array (but don't use the latter) is the only way you can guarantee contiguous allocation.


Trying to keep the answer in sync with the comments. You say that the max size of the first dimension is 9! and, as before, the size of the second dimension is 9.

Allocate it all up front. You're trading some memory for time. 9! * 9 * 2 / 1024 / 1024 == ~6.22MB.

As you say, the List may grow to that size anyway, so worst case you waste a few MB of memory. I don't think it's going to be an issue unless you plan on running this code in a toaster oven. Just allocate the buffer as one array up front and you're good.

share|improve this answer
oh, right. Duh. Thanks –  David Sep 8 '13 at 3:39
Whether jagged arrays are faster or slower than multidimensional arrays probably depends on your access pattern. Multidimensional arrays are contiguous, so the CPU can prefetch data from it quite easily. If your code performs linear scans through the array I expect it would be faster on multidimensional arrays than on jagged arrays (if the arrays are large enough). –  Mehrdad Sep 8 '13 at 4:59
@Mehrdad: Yeah, I actually meant to remove that bit after the OP gave me more info. Thanks –  Ed S. Sep 8 '13 at 10:42
add comment

List functions as a dynamic array, not a linked list, but this is beside the point. No memory will be allocated for the char[]s until they themselves are instantiated. The List is merely responsible for holding references to char[]s, of which it will contain none when first created.


No, but you could instantiate a 2-dimensional array of chars, if you also know how many char arrays there would have been:

char[,] array = new char[x, y];
share|improve this answer
I thought List created a linked list if the data type is a reference? –  David Sep 8 '13 at 3:40
@David: No. List<T> has the semantics of an array, never a linked list. For example, you can index into it. That would be a nasty trick if the index was O(n) in time (as it would be for a LL) –  Ed S. Sep 8 '13 at 3:42
Good to know. Thanks. –  David Sep 8 '13 at 3:45
add comment

Your Answer


