Lab #3: Linear List

Introduction

This lab is split into three parts. The first part concentrates on getting familiarized with extensible array-based linear list implementation. The second part deals with linked list. And the third part presents some typical applications of linear list.

1. Array-based Linear List

Your job in this problem is to implement the array-based linear list as we discussed in the class. That is, you may use the extensible array-based concrete representation, and your code should at least satisfy this interface:

  #ifndef ARRAY_LIST_H
  #define ARRAY_LIST_H
  
  typedef void *poly;
  typedef struct arrayListStruct *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; if none exists, return false
  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

Also note that you should use the polymorphic programming style as we discussed in lab #2. (Or you may also want to try the object-oriented style.)

(Optional) Question #1: How to implement the above function delete in order to make use of memory more efficiently? That is, after some delete operations, if there is "few" elements left in the array, then the array should shrink. To what value, the shrink factor should be set?

2. Linked List

Design and implement a linked list-based representation of linear list as we discussed in class, and your code should at least satisfy this interface:

  #ifndef LINKED_LIST_H
  #define LINKED_LIST_H
  
  typedef void *poly;
  typedef struct linkedListStruct *linkedList;
  struct linkedListStruct
  {
    poly data;
    linkedList next;
  };  
  
  linkedList newLinkedList ();
  void insert (linkedList l, poly x, int i);
  poly delete (linkedList l, int i);
  int length (linkedList l);
  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

Note that we use a CDT rather than an ADT. (Why?)

3. Applications of Linear List

Assignment #1: Implement the polynomial ADT "polyn" as we discussed in class.

Assignment #2: A set

S = {e_1, e_2, ..., e_n} is a collection of data elements, 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.

Assignment #3: An association list is an implementation of the dictionary-like data structures based on linear list. An association list takes the form (<k_1, v_1>, ..., <k_n, v_n>), where <k_i, v_i> is a tuple in which k_i and v_i (1<=i<=n) are key and value respectively, with all k_i distinct. Your job is to design an ADT dict and present an implementation of it. Your interface should satisfy this interface:

  typedef struct dictStruct *dict;
  
  dict newDict ();
  void insert (poly key, poly value);
  poly lookup (poly key);

You may want to make use of either the array-based or linked list-based representation.