Data Structure List


Recall the traditional list code snippets, as given in class:

The list type:

struct AList {
int first;
struct AList * rest;
typedef struct AList * List;

My style of hiding the fact that
List is pointer is based on what you're familiar with from Scheme and Java. Others prefer something like typedef struct AList Cons; In your own code, you may do what you wish.

To create a list:

List make_empty()
return NULL;

List make_cons(int first, List rest)
List list = (List) malloc(sizeof(struct AList));
if (list == NULL) {
fprintf(stderr,"Out of memory.\n");

list->first = first;
list->rest = rest;
return list;

To access a list:

List list = ...;

if (list == NULL) {
else {
...list->first ... list->rest ...

Better yet, you could package such code in accessor functions, as you've seen in COMP 212, and as in the exercises below.

  1. List access details should be packaged into predicate and selector functions. Write functions of the following types. Use any appropriate error-checking. The following function names are just suggestions, but should be self-explanatory.

              #include <stdbool.h>

    bool is_empty(List);
    bool is_cons(List);
    int cons_first(List);
    List cons_rest(List);
  2. Using these constructors, write code to create one specific list, such as the following:

              3 7 9 2 8
  3. Write a function (using the constructors, predicates, and selectors) which returns the reversal of an arbitrary List. For simplicity, use the functional accumulator-based strategy described in COMP 210.

  4. Write a function which prints an arbitrary value of type List.

  5. Combine these pieces into a whole program to compute and print the reversal of the example list.

  6. free all malloc-ed data. (This is good practice even at the end of a program, since you might be using a faulty OS which doesn't release all your process' data upon process termination.)

Solutions Here

A Part Of Thiyagaraaj Websites