Pointers and arrays in C

The C language provides arrays to store a series of elements of one data type. It also has pointers. Though pointers have been removed out of some modern languages such as Java, it still remains a topic of interest.

Introduction to Arrays

Let us start with an analogy. Suppose that you have a cupboard in your house. You would like to keep books on each shelf of the cupboard. It would be nice to keep Books related to one subject on one rack, books of another subject on another rack. A rack is an array. A rack is used to store books of the same subject. Similarly, an array can store data of the same type.

e.g. Array of 5 integers, array of 10 floating point nos., array of characters.

An array of 5 Numbers

The syntax for declaring an array is :

data_type array_name[size];

int x[5]; /* Array of 5 integers */
float y[6]; /* Array of 6 floating point numbers */
char string[10]; /* Character array of length 10 */

The starting element of the array is called 0th element.
The next element is 1st element.
...
The last element is (n-1)th element, where n is the size of the array.

Array Initialization

Suppose we have an array 'x'.
0th element of x is denoted by x[0]
1st element of x is denoted by x[1]
... (n-1)th element of x is denoted by x[n-1]

When we declare an array, the array is initially empty. The array does not contain any values. We can initialise this array as follows -

int x[5] = {5, 7, 2, 3, 8};

Or we can let the compiler do the work, and initialize it like this -

int x[] = {5, 7, 2, 3, 8};

The compiler will count the number of initializers and create the array with five elements.

More Array Initialization

Let us see a small code snippet that prints the number of days per month.

#include<stdio.h>
#define MONTHS 12

int main(void)
{
  int days[MONTHS] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
  int i;

  for (i = 0; i < MONTHS; i++)
  {
    printf("Month %d has %d days.\n", i+1, days[i]);
  }

  /* indicate success */
  return 0;
}

/*
 * The output looks like this:
 * Month 1 has 31 days.
 * Month 2 has 28 days.
 * Month 3 has 31 days.
 * Month 4 has 30 days.
 * Month 5 has 31 days.
 * Month 6 has 30 days.
 * Month 7 has 31 days.
 * Month 8 has 31 days.
 * Month 9 has 30 days.
 * Month 10 has 31 days.
 * Month 11 has 30 days.
 * Month 12 has 31 days.
 */

It is better to leave it to the compiler to count the elements of the array. So lacking faith in our ability to count correctly, we let the computer give us the size of array.

#include<stdio.h>

int main(void)
{
  int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; /* Use empty brackets */
  int i;

  for (i = 0; i < sizeof days / sizeof (int); i++)
  {
    printf(" Month %d has %d days. \n",i+1,days[i]);
  }

  /* indicate success */
   return 0;
}

Assigning Array Values

We can assign values to array members by using array index.

int x[5];
int i;

for (i = 0; i < 5; i++)
{  
  x[i] = i+1;
}

Thus the array x will contain the elements 1, 2, 3, 4, 5.

Functions and Arrays

Passing Arrays to a Function

Arrays cannot be passed to functions. If an array name is used as an argument in a function call, the address of the first element of the array is passed. The function can access the array through that address.

Suppose we want to write a function that returns the sum of elements of the array.

#include <stdio.h>

/* prototype */
int sum(int a[]);

int main(void) 
{
    int marbles[] = {5, 6, 2, 3, 7};
    int ans;

    ans = sum(marbles);
    printf("The total number of marbles: %d",ans);

    return 0;
}

int sum(int arr[])
{
    int i, s = 0;
    for (i = 0; i < 5; i++)
    {
        s = s + arr[i];
    }
    return s;
}

Note that the array name marbles is used as an argument to the function. The function is expecting an array because its parameter is defined as int arr[]. What is actually passed is the address of marbles[0]. The function then can access the array using the [n] notation.
ans = sum(marbles);
When defining the function we write -
int sum(int arr[])
Since marbles has been passed to the function, arr will refer to the marbles array inside the function.

How Are Arrays Stored in Memory?

When we declare an array
int arr[size]
space is reserved in the memory of the computer for the array. The elements of the array are stored in these memory locations. The important thing about arrays is that array elements are always stored in consecutive memory locations. We can verify this fact by printing the memory addresses of the elements. (Just like every person has a street address, every location in the memory has a memory address, usually a number, by which it can be uniquely identified.)

#include<stdio.h>

int main(void)
{
    int a[] = {1,2,3,4,5,6,7,8,9,10};
    int i;

    /* Print the Addresses */
    for (i = 0; i < 10; i++)
    {
        printf("\nAddress of a[%d] : %p", i, (void *) &a[i]);
    }

    /* indicate success */
    return 0;
}

/* OUTPUT

Address of a[0] : ffe2
Address of a[1] : ffe4
Address of a[2] : ffe6
Address of a[3] : ffe8
Address of a[4] : ffea
Address of a[5] : ffec
Address of a[6] : ffee
Address of a[7] : fff0
Address of a[8] : fff2
Address of a[9] : fff4

*/

As we can see from my implementation, the elements are stored as ffe2, ffe4, ffe6,... But you might wonder why they are not consecutive. The reason is very simple. The size of the int data type in C is at least 2 bytes (depending on the implementation). In this example it is 2 bytes wide, so a[0] will be stored at ffe2, ffe3, a[1] will be stored at ffe4, ffe5, a[2] will be stored at ffe6, ffe7 and so on. Note that the way the %p conversion specification displays values is implementation-dependent, so the values as well as being different, may be also displayed differently on your system.

In place of int, if we use an array of type float and each float uses 4 bytes, we will find a[0] will be stored at ffe2, ffe3, ffe4, ffe5, a[1] will be stored at ffe6, ffe7, ffe8, ffe9 and so on.

Pointers

Introduction to Pointers

Pointers refer to memory addresses, as opposed to specific values. They are denoted by the use of an asterisk (*). Consider the following piece of code:

int i = 1;
int *k = &i;
int m = i;
printf("i (%p): %d\n", &i, i);
printf("k (%p): %d\n", k, *k);
printf("m (%p): %d\n\n", &m, m);
i++;
printf("i (%p): %d\n", &i, i);
printf("k (%p): %d\n", k, *k);
printf("m (%p): %d\n", &m, m);

/* OUTPUT

i (0x7fff62b5fa54): 1
k (0x7fff62b5fa54): 1
m (0x7fff62b5fa50): 1

i (0x7fff62b5fa54): 2
k (0x7fff62b5fa54): 2
m (0x7fff62b5fa50): 1

*/

In this code, k is set to the address of i, where m is set to the value of i. When i is incremented, the change is shown in k, since they both refer to the same memory address. m stays the same, however, since it took the value once, and stored it in a separate memory location.

In the brackets can also be seen the memory address of the variable, which shows that i and k refer to the same memory address, while m refers to a different memory address. Note that in the example, the following are true:

• We used int * to declare a pointer to an integer
• We used &i to get the memory address of i
• We used *k to get the value stored in the address referred to by the pointer k

Pointers as Array Iterators

Pointers can be incremented, which make them a natural choice for iterating an array. Consider the following piece of code:

int a[5] = {0,2,5,8,11};
int *ptr = &a[0];
for (int i = 0; i < 5; i++) {
        printf("%p: %d\n", ptr, *ptr);
        ptr++;
}

/* OUTPUT

0x7fff645ffa40: 0
0x7fff645ffa44: 2
0x7fff645ffa48: 5
0x7fff645ffa4c: 8
0x7fff645ffa50: 11

*/

ptr initially refers to the first item in the array, a[0]. When ptr is incremented, the memory address is in fact incremented by sizeof(int). The value at the address referred to by ptr is therefore then the next value in the array, accessed by *ptr.

Special Application: Linked Lists

A linked list is a list of data, comprised of nodes which specify their data, and the address of the next node, or NULL to specify the last node. Consider the following code:

#include <stdio.h>
#include <stdlib.h>

struct Node {
        int data;
        struct Node * next;
};

int main() {
        struct Node * head = malloc(sizeof(struct Node));
        head->data = 0;
        struct Node * curr = head;
        for (int i = 1; i < 5; i++) {
                struct Node * new = malloc(sizeof(struct Node));
                new->data = 5*i;
                curr->next = new;
                curr = curr->next;
        }
        curr = head;
        while (curr != NULL) {
                printf("%d\n", curr->data);
                curr = curr->next;
        }
        return 0;
}

In this code, we defined a struct for a node in the linked list. We initialize the first node, and then add some data, by creating a new node, setting it to be after the current node, and then moving the current node to the next place. We do a similar process to iterate through the list.

A linked list is a good visualisation of pointers, but is also an effective data type for Last in First Out structures, such as stacks. Adding to a linked list is simply a matter of creating a new node, and setting its next to be the head. Removing is equally simple, get the value, deallocate the memory, and set the second node to be the head.

Special Application: Function Pointers

In addition to other ways that pointers can be used, they can also reference a function. While this may not seem very useful at first, it can be used to either embed a function in to a struct that uses it exclusively, or to allow a function to return a function or use a function as input to another function.

This is a very complex sub-topic and can create a lot of bugs in your program if poorly implemented.