CS 333 Programming Languages
Project 5

Due: Thursday, April 9 2026, 11:59 pm

Part I: Polymorphism in C

For this part, develop an example of polymorphism and demonstrate how C can implement polymorphic functions and types.

Tasks

  1. This task is to create a generic linked list class in C. First, create a Node struct that can hold an arbitrary pointer points at the data to be stored in the Node and a next pointer. Then, create a LinkedList struct that has a head pointer. You are free to use single- or doubly-linked lists. Then implement the following functions. Note that the front of the list is closer to the head and the back of the list is the furthest from the head.

    • LinkedList *ll_create() creates a new LinkedList struct, initializes it, and returns it.
    • void ll_push(LinkedList *l, void *data) adds a node to the front of the list, storing the given data in the node.
    • void *ll_pop(Linked List *l) removes the node at the front of the list and returns the associated data.
    • void ll_append(LinkedList *l, void *data) adds a node to the end of the list, storing the given data in the node.
    • void *ll_remove(LinkedList *l, void *target, int (*compfunc)(void *, void *)) removes the first node in the list whose data matches target given the comparison function. The function returns the pointer to the data in the removed node.
    • void *ll_find(LinkedList *l, void *target, int (*compfunc)(void *, void *)) finds the first node in the list whose data matches target given the comparison function. The function returns the pointer to the data in the node. If the target is not in the list, then the function returns NULL.
    • int ll_size(LinkedList *l) returns the size of the list.
    • void ll_clear(LinkedList *l, void (*freefunc)(void *)) removes all of the nodes from the list, freeing the associated data using the given function.
    • void ll_map(LinkedList *l, void (*mapfunc)(void *)) traverses the list and applies the given function to the data at each node.

    Please create the LinkedList described above following the requirements below.

    1. You are expected to have a header file including the Node struct, the LinkedList struct, and all the above function prototypes. Besides, a C file is needed to implement all the above functions.

    2. You can then test your linked list functions using this test file. Compile using:

      gcc -o clltest clltest.c my_linkedlist.c
    3. Extend the above test file so it uses a linked list with a second data type.
    4. In your README, include a screenshot of the output of clltest for both the original and second data types.
    5. In your README, explain why freefunc is a necessary parameter for the ll_clear function. Invent an eample in which there would be a memory leak if the freefunc were incorrectly supplied by the caller or not used by ll_clear.
    6. Download this smaller test file and draw the call stack and the heap at Mark 1. Include an image of this drawing in your README.

Part II: Polymorphism in Selected Languages

Tasks

  1. Implement a LinkedList class in your selected language, making use of some form of polymorphism to implement the data structure. Create the same set of functions as above, but adapt the data types, as necessary. If your language enables templates or generics, use them. Create a test file like the C test file that demonstrates you can create linked lists to store two different types of data.

    Your selected language may have a built-in list data type, similar to Python. Can you create similar functions without using it? If not, then write code that models each of the functions listed for the API and note any additional capabilities the built-in type has. See if you can figure out how the internal data structure is implemented by doing some timing tests and looking at the results. For example, if the built-in structure is a linked list, then searching it should take linear (O(N)) time.

    Include a screenshot of your testing result for the LinkedList in your report.

  2. Generate a Google Sites page that shows the examples in your language. You can use the code snippets of the general sort and LinkedList class as examples. Explain how the language makes use of polymorphism. If your language has generics or templates, explain how it is implemented. These do not need to be long or detailed explanations, but should identify the benefits and drawbacks of the implementation method.

Extensions

  1. Implement more than one method of creating a generic implementation of a data structure in your selected language. Explain how the methods differ and any benefits/drawbacks.
  2. Implement the delete function for your linked list in C that can remove the node at any given position in the list.
  3. Improve clltest.c and make the program memory leak free.

Please note that it is your responsibility to explicitly indicate the extensions you have taken. If you take the extension in C, please indicate explicitly in the codes and README file. If you take the extensions in the selected languages, please indicate explicitly in your Google Sites report or source codes and README.

Submission

The submission of this project has two components:

  1. Create a folder named Project5_<username> Place the required files into it, zip it, and upload it to the Google Classroom.

    Required Files:

    1. Code: Create a fold for each language, including C and your selected language(s). Place all of your C code and selected language programs to corresponding folders. It should be clear which files correspond to which tasks. All these language folders should be placed into the Project5_<username> folder. Note that the quality of your comments counts toward your grade.
    2. README: We use markdown files for README files. Markdown files are files with the .md filename extension. Each project should have a README file along with all your source codes. The README file will contain:
      • Project identifier, your name, and the submission date.
      • The URL of your Google Sites report.
      • The directory layout for your hand-in folder. You can use the Unix tree command to generate this.
      • Your operating system and C compiler (e.g. use gcc --version).
      • For each task, include how to compile your program, how to run your program, known bugs if there is any, and the program output (a screenshot). The screenshot should include the actual output of running the program if the output is no more than 100 lines. Otherwise, give a brief version of the output.
      • Text and images reporting on the C part of the project.
      • A description of each extension you undertook (for the C part of the project).

      You can follow the instructions for the README file from Project 1.

    2. Please do NOT include: Executable files. On Windows, these have the .exe extension. On Mac and Linux, there is no e xtension. We have found that graders often have difficulty downloading submissions if they contain executable files.

  2. Google Sites Report: The report of this project should have the following elements.
    • Title of the project and your name
    • A section for each task of part II. Every section should contain the snapshot of your sample programs, the outputs, and your explanations.
    • If you complete extensions in your selected language, please include a section for each extension, providing sample programs, outputs, and explanations.

    To check whether you've made your report well organized, please follow the Organization part in the Google Sites section in this writing page. Remember to publish all your changes and include the homepage link of your CS333 Google Sites in the README file.

© 2026 Ying Li. Page last modified: .