Programming: Arrays

Arrays

An array is a data structure that stores a consisting collection of elements (values or variables) of same memory size, each identified by at least one index. On a lower level, an array is a contiguous block of memory space, that contains some amount of bytes, that are are understood as a single data type, on a row.

Example

#include <stdio.h>

int main() {
    long l_array[100]; // 32 bits
    int i_array[100];  // 16 bits

    // Each hexadecimal digit represents four bits
    // (binary digits), also known as a nibble
    printf("value of i_array[0]: %d\n", i_array[0]);

    printf("address of i_array[0]: %p\n", (void*)&i_array[0]);
    printf("address of i_array[1]: %p\n", (void*)&i_array[1]);

    printf("address of l_array[0]: %p\n", (void*)&l_array[0]);
    printf("address of l_array[1]: %p\n", (void*)&l_array[1]);

    return 0;
}

$ gcc array.c && ./a.out
value of i_array[0]: 0
address of i_array[0]: 0x7ffca542d680
address of i_array[1]: 0x7ffca542d684
address of l_array[0]: 0x7ffca542d810
address of l_array[1]: 0x7ffca542d818

The computer will just see 0, 1 bits in the memory, that we are above represented as hexadecimal digits. Each value reserves its own memory space, as we see with the 8 hexadecimal digits, representing 32 bits, for the long array, in a consecutive memory space.

We can get, set and unset the values of the array, by using the index of the element (starting with 0). We are not actually deleting/inserting a value, since the memory is already reserved, but we are just changing the value of the element, which is 0 in C, and NULL in other languages.

• The size of the array is fixed, and cannot be changed, but you can realocate the memory space, and copy the values to the new array.
• javascrit and java don’t have traditional arrays.

How to access an element

To go to a an index, the cpu just needs to do this operation: address of array[0] + type size * index. This is called random/direct access, and is the reason why arrays are so fast. A typical illustration of random access is a book - each page of the book can be open independently of others.

The Big O of going to an element is O(1), instant, since we can easily calculate address of any element.