CSC270: C pointers, Part II

Linked List Example
[ King 17.5 ]

A linked list has a pointer to its first node, which is initialized to
NULL.  `NULL' is usually defined in stdlib.h.

    typedef struct ll_node {
      int data;
      struct ll_node *next;
    } LL_NODE;

    LL_NODE *head;

    head = NULL;

A new node is created with malloc.

    LL_NODE *p;

    p = (LL_NODE *) malloc( sizeof( LL_NODE ) );

The fields of the structure would normally be referenced with the
`dot' operator, as in struct.data and struct.next.  BUT ... since p is
a POINTER to the structure, we use another operator, the `arrow'.  The
following initializes the new structure and adds it to the head of the
list.

    p->data = 0;
    p->next = NULL;

    head = p;

The notation p->data is exactly equivalent to (*p).data.

The following creates a list of nodes storing 5,4,3,2,1,0 in that
order.  Nodes are successively added to the *head* of the list as the
index i increases.

    LL_NODE *head, *p;
    int i;

    head = NULL;

    for (i=0; i < 6; i++) {
      p = (LL_NODE *) malloc( sizeof( LL_NODE ) );
      p->data = i;
      p->next = head;
      head = p;
    }

Trace it.

The following prints every piece of data on a linked list.  Note that
the last node on the list points to NULL:

    p = head;

    while (p != NULL) {
      printf( "%d\n", p->data );
      p = p->next;
    }

Trace it.

When you no longer need something that you allocated with `malloc',
be sure to RETURN THE MEMORY to the operating system:

   free( p );

Above, p is a pointer that was returned from some call to malloc.

Pointers and Arrays
[ King 12.1, 12.2, 12.3 ]

In C, an array variable is usually a pointer to the first element of
the array!

This means that you can pass array into functions without incurring
the cost of copying the whole array.  For example, suppose f() takes
an array of integers as an argument.  The following works because
arrays are represented with pointers.

    void f( int *a, int size )  

    {
      int i;

      for (i=0; i < size; i++)
        printf( "a[%d] = %d\n", i, a[i] );
    }

    main() 

    {
      int x[10];

      f( x, 10 );
    }

In passing `x' in to the function, we're really passing a pointer to the
first element of the array.  We could just as well have done

    f( &(x[0]), 10 );

since this also passes in the address of the first element.  Or, we could
have passed in only the middle four elements of the array:

    f( &(x[3]), 4 );

This passes in a pointer to element x[3] and tells f() that there are
four elements in the array that starts at that address:

               &(x[3])
                  |
                  v
    +---+---+---+---+---+---+---+---+---+---+
  x |   |   |   |   |   |   |   |   |   |   |
    +---+---+---+---+---+---+---+---+---+---+
      0   1   2   3   4   5   6   7   8   9

f() thinks it has the following array:

                +---+---+---+---+
             a  |   |   |   |   |
                +---+---+---+---+
                  0   1   2   3  

Dynamic Array Allocation
[ King 17.3 ]

Since arrays are represented with pointers, we can allocate them
dynamically.  The following allocates an array of 100 integers and
sets all entries to zero.

    int *a, i;

    a = (int *) malloc( 100 * sizeof( int ) );

    for (i=0; i < 100; i++)
      a[i] = 0;

We could just as well have used a pointer to move through the array:

    int *a, *p;

    a = (int *) malloc( 100 * sizeof( int ) );

    p = a;
    for (i=99; i>=; i--) {
      *p = 0;
      p++;
    }

The statement `p++' means `increment p'.  When applied to pointers,
this means `increment the address in p by the size of the thing p
points to'.  In other words (in this case), `point p to the next
integer following it in memory'.

Multidimensional Arrays
Pointers and multidimensional arrays are slightly more involved.  See
[ King 12.4 ], although that doesn't go into very much detail.

Static Multidimensional Arrays
Static arrays have known size at compile-time.  Example
declarations for static arrays are (for one, two, and three
dimensions):

    int a[100];
    int b[10][20];
    int c[3][10][4];

Accessing elements of these arrays is easy.  Here's code that sets
every element of b to zero:

    int i, j;
 
    for (i=0; i<10; i++)
      for (j=0; j<20; j++)
        b[i][j] = 0;