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_ */