Programming Assignment #3: Linear List

• Use the extensible array-based concrete representation, and your code should at least satisfies this interface:

    #ifndef ARRAY_LIST_H
    #define ARRAY_LIST_H
    
    typedef void *poly;
    typedef struct arrayList *arrayList;
    
    arrayList newArrayList ();
    void insert (arrayList l, poly x, int i);
    poly delete (arrayList l, int i);
    void rev (arrayList l);            // reverse the list l in place
    // return the first element x in list l, such that pred(x) evaluates to true (1); return false (0), if none exists
    poly exists (arrayList l, int (*pred) (poly));
    // apply function "f" to every element in list "l" to obtain a new list and return it
    arrayList map (arrayList l, poly (*f) (poly));
    void foreach (arrayList l, void (*f)(poly));
    
    #endif
  

• Study how to implement the above function delete to use memory more efficiently, that is, after some delete operations, if there is "few" elements left in the array, then the array should shrink. Pay special attention to the shrink factor.
• Design and implement a linked list-based concrete representation of linear list and, your code should at least satisfy this interface:

    #ifndef LINKED_LIST_H
    #define LINKED_LIST_H
    
    typedef void *poly;
    typedef struct linkedList *linkedList;
    
    linkedList newLinkedList ();
    void insert (linkedList l, poly x, int i);
    poly delete (linkedList l, int i);
    void rev (linkedList l);            // reverse the list l in place
    // return the first element x in list l, such that pred(x) evaluates to true (1); return false (0), if none exists
    poly exists (linkedList l, int (*pred) (poly));
    // apply function "f" to every element in list "l" to obtain a new list and return it
    linkedList map (linkedList , poly (*f) (poly));
    void foreach (linkedList l, void (*f)(poly));
    
    #endif
  

2. Implement the "polyn" ADT as we discussed in class.

3. A set S = {e_1, e_2, ..., e_n} is a collection of data items and all elements e_i (1<=i<=n) are of the same type but have pair-wise distinct values. Design and implement an ADT called "set" to represent this mathematical concept. Your "set" ADT should support typical set operations such as: newSet, setSize, isEmpty, insert, delete, union, intersection and so on.

4. An association list is an implementation of the dictionary-like data structures based on linear list. An association list takes the form (< k1, v1 >, ..., < kn, vn >) where < key, value > is a tuple in which ki and vi (1<=i<=n) are keys and values respectively, with all ki distinct. Your job is to give an interface and implementation of association list, making use of both the array-based and linked list-based representations.

5. (Optional, extra credit.) A property list is a list (a1, ..., an) in which every element ai (1<=i<=n) may have arbitrary type, i.e. the element types may be different. For instance, the list ("hello", 8, 3.14) is a property list. Operations on property list include: new (); insert(l, a); lookup (l) , where new() creates a new and empty property list and insert, lookup inserts and lookups elements in property list separately. Your job is to design an ADT called "plist" by defining its interface and giving an implementation. (Hint: for the insert and lookup to work, you should associate a tag with every list element, so the prototypes of insert and lookup read: insert (l, a, tag); lookup (l, tag).)

6. (Optional, extra credit.) A functional list is a list which never changes once created. Functional list satisfies the interface in problem 2 and its typical representation may look like this:

  struct list
  {
    enum {NIL, CONS} kind;
    union
    {
      int nil;
      struct
      {
        poly data;
        list next;
      } cons;      
    } u;
  };