Question

Part 1: Implement a singly linked list
--------------------------------------

(a)

Your job is to implement a generic singly linked list that can hold
any data type. The interface has been specified and provided to you
in a header file called mylist.h. So your job is to write mylist.c
that implements each function whose prototype is included in mylist.h.
Specifically, you are asked to write the following functions:

struct Node *addFront(struct List *list, void *data)

void traverseList(struct List *list, void (*f)(void *))

void flipSignDouble(void *data)

int compareDouble(const void *data1, const void *data2)

struct Node *findNode(struct List *list, const void *dataSought,
int (*compar)(const void *, const void *))

void *popFront(struct List *list)

void removeAllNodes(struct List *list)

struct Node *addAfter(struct List *list,
struct Node *prevNode, void *data)

void reverseList(struct List *list)

The header file contains detailed comments specifying the behavior of
the functions. Your implementation should follow the specified
behavior.

In addition, I provide you with a test driver program, mylist-test.c, which
produces the following output for a correctly implemented linked list:

testing addFront(): 9.0 8.0 7.0 6.0 5.0 4.0 3.0 2.0 1.0
testing flipSignDouble(): -9.0 -8.0 -7.0 -6.0 -5.0 -4.0 -3.0 -2.0 -1.0
testing flipSignDouble() again: 9.0 8.0 7.0 6.0 5.0 4.0 3.0 2.0 1.0
testing findNode(): OK
popped 9.0, the rest is: [ 8.0 7.0 6.0 5.0 4.0 3.0 2.0 1.0 ]
popped 8.0, the rest is: [ 7.0 6.0 5.0 4.0 3.0 2.0 1.0 ]
popped 7.0, the rest is: [ 6.0 5.0 4.0 3.0 2.0 1.0 ]
popped 6.0, the rest is: [ 5.0 4.0 3.0 2.0 1.0 ]
popped 5.0, the rest is: [ 4.0 3.0 2.0 1.0 ]
popped 4.0, the rest is: [ 3.0 2.0 1.0 ]
popped 3.0, the rest is: [ 2.0 1.0 ]
popped 2.0, the rest is: [ 1.0 ]
popped 1.0, the rest is: [ ]
testing addAfter(): 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0
popped 1.0, and reversed the rest: [ 9.0 8.0 7.0 6.0 5.0 4.0 3.0 2.0 ]
popped 9.0, and reversed the rest: [ 2.0 3.0 4.0 5.0 6.0 7.0 8.0 ]
popped 2.0, and reversed the rest: [ 8.0 7.0 6.0 5.0 4.0 3.0 ]
popped 8.0, and reversed the rest: [ 3.0 4.0 5.0 6.0 7.0 ]
popped 3.0, and reversed the rest: [ 7.0 6.0 5.0 4.0 ]
popped 7.0, and reversed the rest: [ 4.0 5.0 6.0 ]
popped 4.0, and reversed the rest: [ 6.0 5.0 ]
popped 6.0, and reversed the rest: [ 5.0 ]
popped 5.0, and reversed the rest: [ ]

This model output is also provided to you in mylist-test-output.txt.

I recommend you implement the functions in the order listed, and test each
function as you go. You can start by commenting out the code in main() of
mylist-test.c and uncomment the code one block at a time to test each list
function you implemented, comparing your output with that of
mylist-test-output.txt. The 'diff' UNIX command may come in handy.

Note that mylist-test.c may not test every single function. You are still
responsible for correct implementations of all functions.

Don't forget to run valgrind at each step to make sure you don't have a
memory bug, and don't forget to include the valgrind output in your
README.txt when you're done.

(b)

Modify your Makefile to produce a static library named 'libmylist.a'
that contains your linked list object files. Your test program,
mylist-test, must link with the library file, not the mylist.o file.

You can learn how to make a library file here:

http://randu.org/tutorials/c/libraries.php

Note that we are making a static library, not a shared library.

my list.h

#ifndef _MYLIST_H_

#define _MYLIST_H_

/*

* A node in a linked list.

*/

struct Node {

void *data;

struct Node *next;

};

/*

* A linked list.

* 'head' points to the first node in the list.

*/

struct List {

struct Node *head;

};

/*

* Initialize an empty list.

*/

static inline void initList(struct List *list)

{

list->head = 0;

}

/*

* In all functions below, the 'list' parameter is assumed to point to

* a valid List structure.

*/

/*

* Create a node that holds the given data pointer,

* and add the node to the front of the list.

*

* Note that this function does not manage the lifetime of the object

* pointed to by 'data'.

*

* It returns the newly created node on success and NULL on failure.

*/

struct Node *addFront(struct List *list, void *data);

/*

* Traverse the list, calling f() with each data item.

*/

void traverseList(struct List *list, void (*f)(void *));

/*

* Traverse the list, comparing each data item with 'dataSought' using

* 'compar' function. ('compar' returns 0 if the data pointed to by

* the two parameters are equal, non-zero value otherwise.)

*

* Returns the first node containing the matching data,

* NULL if not found.

*/

struct Node *findNode(struct List *list, const void *dataSought,

   int (*compar)(const void *, const void *));

/*

* Flip the sign of the double value pointed to by 'data' by

* multiplying -1 to it and putting the result back into the memory

* location.

*/

void flipSignDouble(void *data);

/*

* Compare two double values pointed to by the two pointers.

* Return 0 if they are the same value, 1 otherwise.

*/

int compareDouble(const void *data1, const void *data2);

/*

* Returns 1 if the list is empty, 0 otherwise.

*/

static inline int isEmptyList(struct List *list)

{

return (list->head == 0);

}

/*

* Remove the first node from the list, deallocate the memory for the

* ndoe, and return the 'data' pointer that was stored in the node.

* Returns NULL is the list is empty.

*/

void *popFront(struct List *list);

/*

* Remove all nodes from the list, deallocating the memory for the

* nodes. You can implement this function using popFront().

*/

void removeAllNodes(struct List *list);

/*

* Create a node that holds the given data pointer,

* and add the node right after the node passed in as the 'prevNode'

* parameter. If 'prevNode' is NULL, this function is equivalent to

* addFront().

*

* Note that prevNode, if not NULL, is assumed to be one of the nodes

* in the given list. The behavior of this function is undefined if

* prevNode does not belong in the given list.

*

* Note that this function does not manage the lifetime of the object

* pointed to by 'data'.

*

* It returns the newly created node on success and NULL on failure.

*/

struct Node *addAfter(struct List *list,

   struct Node *prevNode, void *data);

/*

* Reverse the list.

*

* Note that this function reverses the list purely by manipulating

* pointers. It does NOT call malloc directly or indirectly (which

* means that it does not call addFront() or addAfter()).

*

* Implementation hint: keep track of 3 consecutive nodes (previous,

* current, next) and move them along in a while loop. Your function

* should start like this:

struct Node *prv = NULL;

struct Node *cur = list->head;

struct Node *nxt;

while (cur) {

......

* And at the end, prv will end up pointing to the first element of

* the reversed list. Don't forget to assign it to list->head.

*/

void reverseList(struct List *list);

#endif /* #ifndef _MYLIST_H_ */

Answer 1

mylist-test.c

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "mylist.h"

static void printDouble(void *p)
{
    printf("%.1f ", *(double *)p);
}

static void die(const char *message)
{
    perror(message);
    exit(1);
}

int main()
{
    double a[] = { 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0 };
    int n = sizeof(a) / sizeof(a[0]);

    int i;
    double x;
    void *data;
    struct Node *node;

    // initialize list
    struct List list;
    initList(&list);

    // test addFront()
    printf("testing addFront(): ");
    for (i = 0; i < n; i++) {
   if (addFront(&list, a+i) == NULL)
        die("addFront() failed");
    }
    traverseList(&list, &printDouble);
    printf("\n");

    // test flipSignDouble()
    printf("testing flipSignDouble(): ");
    traverseList(&list, &flipSignDouble);
    traverseList(&list, &printDouble);
    printf("\n");
    printf("testing flipSignDouble() again: ");
    traverseList(&list, &flipSignDouble);
    traverseList(&list, &printDouble);
    printf("\n");
  
    // test findNode()
    printf("testing findNode(): ");
    x = 3.5;
    node = findNode(&list, &x, &compareDouble);
    assert(node == NULL);
    x = 1.0;
    node = findNode(&list, &x, &compareDouble);
    assert(node != NULL && *(double *)node->data == x);
    printf("OK\n");

    // test popFront()
    while ((data = popFront(&list)) != NULL) {
   printf("popped %.1f, the rest is: [ ", *(double *)data);
   traverseList(&list, &printDouble);
   printf("]\n");
    }

    // test addAfter()
    printf("testing addAfter(): ");
    node = NULL;
    for (i = 0; i < n; i++) {
   // We keep adding after the previously added node,
   // so we are in effect 'appending' to the list.
   node = addAfter(&list, node, a+i);
   if (node == NULL)
        die("addAfter() failed");
    }
    traverseList(&list, &printDouble);
    printf("\n");

    // test reverseList()
    while ((data = popFront(&list)) != NULL) {
   printf("popped %.1f, and reversed the rest: [ ", *(double *)data);
   reverseList(&list);
   traverseList(&list, &printDouble);
   printf("]\n");
    }

    return 0;
}

mylist.c

#include <stdio.h>
#include <stdlib.h>
#include "mylist.h"

// adds node to front of list
struct Node *addFront(struct List *list, void *data)
{
    //creates new node
    struct Node *front = (struct Node *)malloc(sizeof(struct Node));
    if (front == NULL) {
        perror("malloc returned NULL");
        exit(1);
    }
  
    //adds to front
    front->data = data;
    front->next = list->head;
    list->head = front;
    return front;
}

//calls f() on each element of the list
void traverseList(struct List *list, void (*f)(void *))
{
   struct Node *linkedList = list->head;
   //traverses until list is null
   while (linkedList) {
       f(linkedList->data);
       linkedList = linkedList->next;
   }
}

//takes given data point and makes it negative
void flipSignDouble(void *data)
{
    double *nodeData = (double *) data;
    *nodeData = *nodeData * -1;

}

// if given data are equal, returns 0 and 1 otherwise
int compareDouble(const void *data1, const void *data2)
{
    double *double1 = (double *) data1;
    double *double2 = (double *) data2;
    int result;
    if (*double1 == *double2) {
        result = 0;
    } else {
        result = 1;
    }
    return result;
}

// uses compar function to find given data in list
struct Node *findNode(struct List *list, const void *dataSought,
        int (*compar)(const void *, const void *))
{
    struct Node *linkedList = list->head;
    struct Node *nodeFound = NULL;

    while (linkedList) {
        // sets nodeFound = 0 if data are equal
        if(compar(dataSought, linkedList->data) == 0) {
            nodeFound = linkedList;
        }
        linkedList = linkedList->next;
    }
    return nodeFound;
}

// removes first node in list and returns pointer to data
void *popFront(struct List *list)
{
    if (isEmptyList(list)) {
        return NULL;
    }
    struct Node *firstnode = list->head;
    void *returndata = firstnode->data;
  
    //removes front node
    list->head = firstnode->next;
    free(firstnode);
    return returndata;
}

// removes all nodes
void removeAllNodes(struct List *list)
{
    // only checks if list is not empty
    while(!isEmptyList(list)) {
        popFront(list);
    }
}

//adds new node with data after given node
struct Node *addAfter(struct List *list,
        struct Node *prevNode, void *data)
{
    if (prevNode == NULL) {
        return addFront(list, data);
    } else {
        // creates new node to add to list
        struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
        if (newNode == NULL) {
            perror("malloc returned null");
            exit(1);
        }
        newNode->data = data;
        newNode->next = prevNode->next;
        prevNode->next = newNode;
        return newNode;
    }
}

// reverses the list
void reverseList(struct List *list)
{
    struct Node *prev = NULL;          
    struct Node *curr = list->head;                
    struct Node *next;

    // reverses list
    while (curr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    // sets head to back of list
    list->head = prev;
      
}

mylist.h

#ifndef _MYLIST_H_
#define _MYLIST_H_

/*
* A node in a linked list.
*/
struct Node {
    void *data;
    struct Node *next;
};

/*
* A linked list.
* 'head' points to the first node in the list.
*/
struct List {
    struct Node *head;
};

/*
* Initialize an empty list.
*/
static inline void initList(struct List *list)
{
    list->head = 0;
}

struct Node *addFront(struct List *list, void *data);

/*
* Traverse the list, calling f() with each data item.
*/
void traverseList(struct List *list, void (*f)(void *));

struct Node *findNode(struct List *list, const void *dataSought,
   int (*compar)(const void *, const void *));

/*
* Flip the sign of the double value pointed to by 'data' by
* multiplying -1 to it and putting the result back into the memory
* location.
*/
void flipSignDouble(void *data);

/*
* Compare two double values pointed to by the two pointers.
* Return 0 if they are the same value, 1 otherwise.
*/
int compareDouble(const void *data1, const void *data2);

/*
* Returns 1 if the list is empty, 0 otherwise.
*/
static inline int isEmptyList(struct List *list)
{
    return (list->head == 0);
}

void *popFront(struct List *list);

/*
* Remove all nodes from the list, deallocating the memory for the
* nodes. You can implement this function using popFront().
*/
void removeAllNodes(struct List *list);

struct Node *addAfter(struct List *list,
   struct Node *prevNode, void *data);

void reverseList(struct List *list);

#endif /* #ifndef _MYLIST_H_ */