Linked List

One of the first questions to arise will be “What is this a linked list of? Integers? Strings? More lists?” The catch is that you’ll be storing lists created in Scheme, which can contain values of a whole variety of types. You might think: “Ah! I’ll have a Value class, with subclasses for IntValue, StringValue, etc.” And that would be totally awesome, if you were implementing this list using an OOP (object-oriented programming) language. Oops.

In C, one way to handle this type of typing issue is to use union types. (See our online C reference that I assigned or other online tutorials.) These types allow you to have a single datatype that sometimes includes an int, sometimes a char *, etc.) Every such value should also include a tag telling you what kind of data you’re storing.

typedef enum {INT_TYPE, DOUBLE_TYPE, STR_TYPE,...} valueType;

struct Value {
    valueType type;
    union {
        int i;
        double d;
        char *s;
        ...
    };
};

typedef struct Value Value;

The names INT_TYPE, DOUBLE_TYPE, etc., represent types of Values. The Value struct includes a field (type) containing one of these tags, as well as a union of various possible fields. For example, you could create a value containing the integer 5 as follows:

Value myInt;
myInt.type = INT_TYPE;
myInt.i = 5;

If you have a Value and want to determine its type, you might choose to use a switch statement:

switch (val.type) {
case INT_TYPE:
    // do something with val.i
    break;
case DOUBLE_TYPE:
    // do something with val.d
    break;
...
}

You will thus want to make some sort of linked list implementation where the nodes contain Values. There are many different ways that one can construct a linked list. The most common approach you have likely seen is one that consists of nodes, where each node is a struct containing two items: a pointer to a value, and a pointer to another node.

Don’t do it this way for the assignment. There’s a better way that will save you much pain later.

Because you will eventually be using your linked list to represent Scheme S-expressions, you will have a much easier time if your linked list actually resembles a Scheme linked list. Specifically, each node should be a “cons cell” with two pointers within, and it should not be strictly typed.

Here is an abbreviation of the technique that you will use:

struct Value {
    valueType type; // type will also have a CONS_TYPE as an option
    union {
        int i;
        double d;
        /* .... */
        struct ConsCell {
            struct Value *car;
            struct Value *cdr;
        } c;       
    };
};


typedef struct Value Value;

The “head” pointer for your linked list, whatever you choose to call it, should be of type Value*. It should be NULL_TYPE if the list is empty, or point to a Value. That Value should be one that holds a cons cell. The car of that cell should point to the first item in your linked list; the cdr should point to another Value. And so on. At the end of the linked list, the cdr of that Value should point to a NULL_TYPE Value.

And finally: if you insert tokens at the beginning of the list, which is the simplest way, your tokens will be represented in backwards order from what you typically want. One could handle this efficiently by writing code to add at the tail of the linked list instead of the head. Instead, we’ll make things simpler by writing an additional function to reverse a linked list. Is this less efficient? Yeah. This project is large enough; we won’t focus very much on efficiency, though you might think about tracking places to make it more efficient if you want to improve it at the end.

You can feel free to leverage any linked list code that we may or may not have written in class, though bear in mind that it might not fit this framework.

After you clone your repository, you should be able to see that you get the following starting files:

• value.h: this defines the Value structure, described above
• linkedlist.h: this defines all of the functions that you will need to write
• main.c: this is a tester function that makes some nodes, puts them into a linked list, displays them, and cleans up memory afterwards
• Makefile: contains instructions for the command make, which will compile and test your code
• test-e and test-m: usual
• test_utilities.py: helper utilities used by test-e and test-m

The missing file here is linkedlist.c, which you’ll need to create yourself in order to implement everything in linkedlist.h. To compile your code, issue the command make at the command prompt. This will follow the instructions in the Makefile for building your project in order to produce an executable called linkedlist. At first, it won’t build at all because your linkedlist.c file isn’t there. Create the file and for now, create every function that you need with no code inside it so that you can get everything to build. Once you have done that, you can begin implementing your functions, and testing appropriately.

The tester code creates an executable that you can run by typing ./linkedlist, which takes parameters depending on whether or not it should run the exemplary tests. The easiest way to run the tests is to use ./test-m and ./test-e, as usual, which will automatically compile all of your code and run the ./linkedlist executable for you.

Your code should have no memory errors when running on any input (correct or incorrect) using valgrind. The testing scripts will automatically run valgrind on your code, and show you if there are memory errors.

Work in this section is 100% optional, and doesn’t contribute towards your grade. Nonetheless, if you’re looking for an extra challenge, these are fun additional exercises to try.

You’ve already implemented some Scheme functions: car, cdr, and cons. In the same spirit, add new functions titled append, and list that are analogs to the functions of the same name in Scheme. You’ve got more flexibility in how you go about this; we won’t stress test these in quite the same way as the rest, so make sure to indicate in your comment and in your tests what you’ve done.

Make sure that you have added linkedlist.c correctly, then push to GitHub. (You can leave out your compiled executables as well as the .o object files if you wish.) All of your work should be in linkedlist.c, so all you should really need to add is linkedlist.c.

The graders and I need to know which commit is the one that we should use for grading. As usual, label it as SUBMITTED with a commit message, and prepend with M: or E: to run tests. Remember to only push with an M: or an E: after you have verified that your tests run correctly, so we can save minutes of time on GitHub.

Good luck, and have fun!

This assignment was originally created by David Liben-Nowell and has since been updated by Dave Musicant and Laura Effinger-Dean.