Are "array" element values stored in one location or in separate locations?

Question

Since there's no such thing as an array in the C language, is the following all stored in one memory location, or is each element's value stored in an "array" of memory locations?

int array[] = {11, 13, 17, 19};

• Scenario 1

  {11, 13, 17, 19} --> location A
  

• Scenario 2

  {
      11 --> location A
      13 --> location B
      17 --> location C
      19 --> location D
  }
  

Which one is the valid memory layout?

Answer 1

C explicitly defines "array" as a type.

Quoting C11, chapter §6.2.5, Types (emphasis mine)

An array type describes a contiguously allocated nonempty set of objects with a particular member object type, called the element type. The element type shall be complete whenever the array type is specified. Array types are characterized by their element type and by the number of elements in the array. An array type is said to be derived from its element type, and if its element type is T, the array type is sometimes called ‘‘array of T’’. The construction of an array type from an element type is called ‘‘array type derivation’’.

In a nutshell, the answer is, array elements are stored in separate but contiguous locations.

Let's suppose we have declared an array of 5 int:

int arr[5];

Then, on a platform where the size of an integer is 2 bytes (szeof(int) ==2), the array will have its elements organized like this:

On a different platform, where sizeof(int) == 4, it could be:

So the representation

{
    11 --> location A
    13 --> location B
    17 --> location C
    19 --> location D
}

is valid, considering B == A + 1, C == B + 1 and so on.

Here, please note, the pointer arithmetic regards the data type, so A+1 will not result in an address with 1 byte increment, rather the increment is by one element. In other words, the difference between the address of two consecutive element will be the same as the size of the datatype (sizeof (datatype)).

Answer 2

The elements would be in contiguous memory location.

Let array[0] is at location B and the size of each element of the array, i.e. sizeof(int), is S. Then we have this

array[0] at B
array[1] at B + S
array[2] at B + 2S
..
array[n] at B + n*S

Answer 3

The compiler allocates the array in specific, contiguous locations.

You can also check it up with the next code:

#include <stdio.h>

void main()
{
    int array[] = {11, 13, 17, 19};
    for (int i = 0; i < 4; i++)
        printf("0x%p ", &array[i]);
}

That gives the hexadecimal addresses

0x14fee0 0x14fee4 0x14fee8 0x14feec

with the margin of 4 bytes per element, the size of int.

---

Generally, you can take the pointer to one element of the array, say index m, and add it n as a number of elements, and get the pointer to the n+m index in the array.

*(array + n) == array[n]

Answer 4

C does have an array type. Just because you can access arrays via pointers doesn't mean they don't exist.

Array elements are stored in contiguous memory locations starting from the address "array" (i.e. the base address of array which is also the address of the first element of the array) and each element of the array is addressable separately.

Assuming 4 byte ints, the array int array[] = {11, 13, 17, 19}; would look like:

+-----+-----+-----+-----+
|  11 |  13 |  17 |  19 |
+-----+-----+-----+-----+
  ^     ^     ^      ^
0x100 0x104  0x108  0x112

You can probably understand better with a simple program:

#include <stdio.h>

int main(void)
{
int array[] = {11, 13, 17, 19};

/* all will print the same value */
printf("Base address of array: %p, %p, %p\n", (void*)array, (void*)&array[0], (void*)array);

for (size_t i = 0; i < sizeof array/sizeof array[0]; i++) {
      printf("address of array[%d]: %p\n", i, (void*)&array[i]);
}

return 0;
}

One important detail is that though the addresses &array[0] and &array are the same value, their types are different. &array[0] is of type int* (pointer to an int) whereas &array is of type int(*)[4] (pointer to an array of 4 ints).

Answer 5

Since there's no such thing as an array in the C language

There is totally such a thing as an array in the C language. All of your examples are C arrays.

The difference you are describing is the difference between a list and an array.

Arrays in C, as indeed in most languages, are like your Scenerio 1.

You could certainly accomplish your Scenerio 2 with an array of pointers to values. for example

int array1[] = {11, 14, 17, 19};
// vs 
int* array2[] = {
    &array1[0],
    &array1[1],
    &array1[2],
    &array1[3]
};

A list however is quite different in organization.

struct list_node{
    int value;
    struct list_node * next;
};

struct int_list {
    int length;
    struct list_node * first;
};

int main(){
    int i;
    struct list_node nodes[4];
    struct int_list list1 = {.length = 4, .first=&nodes[0]};
    for (i = 0; i < 4; i++){
        nodes[i].value = array1[i];
        if (i != 3){
            nodes[i].next = &nodes[i+1];
        } else {
            nodes[i].next = NULL;
        }
    }

    // traverse the list.
    struct list_node * n = list1.first;
    while(n != NULL){
        printf("%d\n", n->value);
        n = n->next;
    }
}