4.1.1 Representation

The basic representation of a list requires two factors. First, it needs to represent the value of the first element. Next, it needs to represent the rest of the list. Using an array as a list is possible, we need to use the following data members in a list:

• pointer to an array: this pointer tracks which array actually stores values of this list
• index: this unsigned integer indicates the index of the element in the array that represents the first value of the list

In C, we can define the internal representation of a list as follows:

struct _List
{
  struct ArrayADT *array; // where values are stored
  unsigned index; // index of the first element
};