A linked list is a container that can be defined in terms of a chain of list nodes. Each list node contains data and a pointer to the next node in the list. One must (minimally) keep a pointer to the first node in the list, which is typically termed: the head pointer. For this exercise all adds are preformed by dynamically allocating a new node, setting its data, and then inserting it at the front of the list (there is no notion of a full list). Removes are not supported. An empty list is one whose head pointer has the value NULL.

First, you are given the contents of the file list.h (which may not be modified):

// a recursive data type definition

// serves as the nodes of a list

typedef struct node

{

int data;

struct node* next;

} node;

// create an empty list - set *node = NULL

void create_list(node** head);

// add a new node to the end of the list

void add(node** head, node* new_node);

// remove the node at the head of the list (if there is one)

node* remove(node** head, node* new_node);

// return the number of nodes in the list

int list_len(const node* head);

and the contents of the file main.c (which also may not be modified):

#include

#include

#include "list.h"

int main(int args, char* argv[])

{

node* head;

node* new_node;

create_list(&head);

int i;

for (i = 1; i

{

// create a new node

new_node = (node*)malloc(sizeof(node));

// set its data field

new_node->data = 2 * i;

// its next field is set in the add function

// as well as adjusting the head pointer

add(&head, new_node);

}

int len = list_len(head);

printf(" List length = %d ", len);

// make copy of head for traversal

node* my_head = head;

// cheap print list

while (my_head)

{

printf("data = %d ", my_head->data);

my_head = my_head->next;

}

// think: how would you free all of the node? ...

// free(head); ?

return 0;

}

You will need to create the files :

list.c

Makefile

Such that when all the files are in one directory (in UNIX) typing

make

followed by

./main

Will produce the following output:

$ make

gcc -Wall -c list.c

gcc -Wall -c main.c

gcc list.o main.o -o main

$ ./main

List length = 9

data = 18

data = 16

data = 14

data = 12

data = 10

data = 8

data = 6

data = 4

data = 2