C: Singly Linked Lists

Review

  1. Reminder: Functions to allocate and free memory at part of the standard library that is included thus:
    #include <stdlib.h

  2. The size given to malloc is always in bytes; the sizeof operator allows us to get the size in bytes of any type:
    double *pd ;
    pd = malloc(100 * sizeof(double)) ; // can hold up to 100 double precision numbers.

  3. sizeof can also be called with a variable name, in which case the variable's type is used:
    double *pd ;
    double pi = 3.14159 ;
    pd = malloc(100 * sizeof(pi)) ;     // also can hold up to 100 double precision numbers.

  4. The size of a global or local array is the number of bytes needed to hold the array:
    double x ;                                  // size(x) = size(double) = 8 bytes
    double values[10] ;                         // sizeof(values) = 8 * 10 = 80 bytes
    double constants[] = {3.14159, 6.023e24} ;      // sizeof(constants) 8 * 2 = 16 bytes

  5. All pointers have the same size: 4 bytes on 32-bit machines and 8 bytes on 64-bit machines.

  6. Array arguments to functions are really pointers, even if you explicitly declare the array size. Thus the size of an array argument is the size of a pointer.

  7. BE CAREFUL: If p is a pointer, then sizeof(p) is the number of bytes to hold a pointer, not what p points to!:
    int *ip ;
    ip = malloc( sizeof(ip) ) ;   // WRONG! allocate space for an integer pointer.
    ip = malloc( sizeof(*ip) ) ;  // CORRECT! allocate space for an integer that ip references.
    ip = malloc( sizeof(int) ) ;  // ALSO CORRECT: take the size of the type.

  8. For structs, the size is the minimum number of bytes needed to hold the struct (while properly aligning values of multi-byte types like int and double):
    typedef struct _node {
        int contents ;
        struct _node *next ;
    } node
    On a 64-bit computer, sizeof(node) is 16 (4 bytes for contents, 4 bytes of padding to properly align the next pointer on an 8-byte boundary, and 8 bytes for next).

  9. Allocating space for a new node and assigning values to the fields:
    node *np ;
    np = malloc( sizeof(node) ) ;
    np->contents = 42 ;
    np->next = NULL ;

Setup

For this activity you will implement 8 functions related to allocating and freeing space for linked list nodes and manipulating linked lists.

  1. Create a directory Linked at the top level of your git repository. Download the file linked.zip into this directory, extract the archive contents, and remove the zip file:
    unzip linked.zip
    rm linked.zip

  2. At this point the directory should contain the following files:
    ActivityJournal.txt
    Makefile
    assert.h
    assert.c
    linked.h
    linked.c
    memory.h
    memory.c
    sizeof_example.c
    test_linked.c

  3. The sizeof operator can be confusing. The program in sizeof_example.c declares some variables and functions and prints out sizes and associated information.
    Read the source file to see what the program does and then compile and execute it:
    make sizeof_example
    ./sizeof_example
    Be sure you understand the output produced, or ask questions if you do not.

  4. Two support modules, assert and memory, are provided to help in testing the code you will write in linked.c.

    1. Assert (assert.h & assert.c) provides rudimentary assertion support such as found in the unit test framework used with Ruby.
    2. Memory (memory.h & memory.c) is a simplified implementation of malloc and free that uses assertions to detect a variety of malloc/free errors and provides functions querying the memory system state that are useful in unit tests.
You need not do anything with respect to these modules; if you use make as outlined below they will be compiled and linked with the test code and your linked list implementation. On the other hand, if you are curious as to how the modules work, feel free to look inside (but don't change anything!).

  1. Make the executable test_linked (the default target of the Makefile) and execute the result:
    make
    ./test_linked

  2. Obviously most of the assertions will fail as the bodies of the functions in linked.c are all skeletons, but if you see the following output you'll know that you downloaded, compiled, and linked the skeleton successfully:

    *** Test making & freeing nodes np1 & np2 ***

    Allocate two nodes
        Make a node for np1
    Assertion failure (test_linked.c@37): np1 != NULL
        Make a node for np2
    Assertion failure (test_linked.c@41): np2 != NULL
        Should have two areas allocated
    Assertion failure (test_linked.c@44): allocated_area_count() == 2

    Check the nodes for correct contents and next links
       np1: contents == 0 and next == NULL
    Segmentation fault (core dumped)

  3. At this point, use git to add, commit, and push the skeleton. This will show that you at least were able to initialize the project.

Activities

Overview

File linked.h declares the interfaces for 8 functions in the module, as well as defining (via typedef) a type node that is the struct from which linked lists are constructed. Most of the time you'll be using pointers to nodes (node *) and referencing the structure fields with the -> syntax. The 8 functions are tested by 4 tests in test_linked:

node *make_node(int value)
Allocate space for a new node, set the node's contents field to value, set the node's next link to NULL, and return a pointer to the node.

void free_node(node *p_node)
Free the space allocated for the node that p_node points to. After this, neither p_node nor any other pointer to this space are valid.

int list_length(node *p_head)
Return the length of the list whose initial node (if any) is pointed to by p_head. Note that a 0 length list is perfectly valid.
node *list_put_at_head(node *p_head, int value)
Place a node with value at the head (initial position) of the list whose head is pointed to by p_head and return a pointer to the head of the resulting list (remember: the list may be empty).
Typically the function is used as follows:
p_head = list_put_at_head(p_head, value) ;

node *list_put_at_tail(node *p_head, int value)
Place a node with value at the end (last position) of the list whose head is pointed to by p_head and return a pointer to the head of the resulting list (remember: the list may be empty).

node *list_put_at_pos(node *p_head, int value, int pos)
Place a node with value in front of the node at position pos in the list whose head is pointed to by p_head and return a pointer to the head of the resulting list. Nodes in the list are numbered from zero (as with array indices).
If pos < 0 treat it as zero; if pos >= list_length(p_head) place the new node at the tail; in either instance, try not to treat these boundary conditions as "special cases." Remember: the list may be empty.
int list_find(node *p_head, int value)
Return the position of the first node holding value in the list whose head is pointed to by p_head (nodes are numbered from zero). If there is no such node, return -1. Remember: the list may be empty.
node *list_remove(node *p_head, int value)
Remove the  first node with value from the list whose head is pointed to by p_head, returning a pointer to the head of the resulting list; any nodes following the one removed must remain on the list! The node removed, if any, must have its space freed. Remember: the list may be empty.

Implementation and Testing

  1. The unit tests in test_linked.c exercise the eight functions in linked.c in the order given in the Overview above.
  2. If an assertion within any tests fails, then no following tests will be run.
  3. For this reason, you should implement, test, debug, and fix the functions in the order given.
  4. Use the make command to build your executable test_linked program:
    make
             Creates and up-to-date version of test_linked, including the assert and memory modules.
    make clean
             Removes out any cruft (backup files, object files, executable, etc.)
  5. Execute the tests:
    ./test_linked
  6. After you have a version of a function that passes the tests, do a git add / commit / push before going on to the next function. This will ensure you receive credit for all the functions you are able to complete.
  7. Do NOT push any version of linked.c that does not compile - the penalty for this is severe (see Assessment).

Activity Journal

As always, complete the Activity Journal, including your estimated time, your plan, your actual time, and observations.

Assessment (100 points)

We will pull your repository after the due date; the assessment is in terms of this pulled information. We will compile and link your program using the simple command:
    make
If this does not create a program test_linked without syntax or linking errors you cannot receive a grade above 30, and your grade will almost certainly be less than this. For this reason, it is best to push only versions of linked.c that compile, even if this means completing only a subset of the functions.