3 Most Elemental List ADT

The most elemental (basic) ADT of a list is as follows:

• new. The creation of a list. A list is empty to begin with. An empty list has no first element.
• make alias. Make a list an alias of another list.
• delete. The deletion of a list.
• getfirst. Return the first element of a list. This interface makes no sense on an empty list.
• getrest. Return the rest of a list as a list. The rest of an empty list is an empty list.
• setfirst. Set the value of the first element of a list.
• setrest. Set a list as the rest of another list.
• isempty. Check to see if a list is empty. Returns true if the list is empty. Return false if the list is not empty.

In C code, the list of $(a, b, c)$ may be constructed as follows:

struct List *pL;
pL = List_new(void);
List_setfirst(pL,'a');
List_setfirst(List_getrest(pL), 'b');
List_setfirst(List_getrest(List_getrest(pL)),'c');

Elements in a list can be listed as follows:

struct List *pL;
// ...
struct List *tmp;
tmp = pL;
while (!List_isempty(tmp))
{
  printf("%c\n",List_getfirst(tmp));
  tmp = List_getrest(tmp);
}

We can even change a list from $(a, b, c)$ to $(a, b, x, c)$ by inserting an value $x$ between the existing values $b$ and $c$ :

struct List *pL;
// ... get pL to point to a list (a, b, c)
struct List *tmpB, *tmpR, *newone;
tmpB = List_getrest(pL); // (b, c)
tmpR = List_getrest(tmpB); // (c)
newone = List_new(); // ()
List_setfirst(newone, 'x'); // (x)
List_setrest(newone, tmpR); // (x, c)
List_setrest(tmpB, newone); // (b, x, c)
// pL is now (a, b, x, c)