Write a Makefile that builds the program list from a C file list.c$.$ Your Makefile should

use the compiler flags discussed in class, and have the $$all$$ and $$clean$$ targets as shown

previously. You should also include the flag $-$Wextra as discussed in the lab.

Creating a List

Your list nodes will be defined as follows:

struct node $\{$

int value ;

struct node $*$ next ;

$\}$;

We will allocate all variable in our main$()$ function.

As with Assignment $4,$ we will be using an array to allocate storage of our nodes $($we will

create $100$ nodes$).$ struct node nodes$[100]$

Once we have our nodes allocated, we need to employ a method to track which nodes in our

array are in use, and which are free. To do this we will create two pointers. struct node

$*$list head and struct node $*$free list.

Storage Initialization

With these pieces in place we now need to initialize our allocated nodes. Create a func$-$

tion called struct node $*$list init$($struct node nodes$[]).$ This function takes the node

storage and iterates each node, connecting its next pointer to the next node in the array,

and for the last item setting the next pointer to

$0($or NULL$).$ The function should return a pointer to last node in the array. We know that

the start of the array is the first node in our free list.

Strictly speaking at this point we have created our first link$-$list.

$2$

List Operations

Insert

There are different types of insertion to a list $($prepend$,$ append, insert before, and insert

after$).$ In this exercise we will only focus on prepend and append. For this we will need a

third pointer struct node $*$list tail that points to the last node in the list $($which is why

our initialization function returns this$).$

Prepend Prepend adds a node to the beginning of the list. There are four steps for this

operation:

$1.$ Get the node pointed to by the free list

$2.$ Update free list to point at the new node$$s next

$3.$ Update the new node$$s next to point at list head

$4.$ Update list head to point at the new node

Append Append adds a node to the end of the list. There are four steps for this operation:

$1.$ Get the node pointed to by free list

$2.$ Update free list to point at the new node$$s next

$3.$ Update the new node$$s next to point at NULL

$4.$ Update list tail$->$next to point at the new node

Remove

As with insert there are several types of removal operations for a list $($Pop$,$ Pop Back, Remove

before, Remove after$).$ In this exercise we will only focus on pop.

Pop Pop removes a node from the beginning of the list. There are four steps for this

operation:

$1.$ Get the node pointed to by list head

$2.$ Update list head to point at list head$->$next

$3.$ Update the new node$$s next to point at list free

$4.$ Update free list to point at the removed node

$3$

Functions to write

You may have notices that there are several overlapping processes in the above operations.

Specifically, inserts require a pop from the free list, and pop requires a prepend to the free

list. For this reason it makes the most sense to create functions that can provide these

operations and then build up the more complex functionality. These are often called helper

functions

list internal prepend Create a function int list internal prepend$($struct node $**$list$,$

struct node $*$node$)$ which takes a pointer to a pointer list and a pointer to a node and

preforms a simple prepend:

$1.$ Update the new node$$s next to point at $*$list

$2.$ Update $*$list to point at the new node

The function should return an int where $0$ is success, and $-1$ is failure.

list internal pop Create a function int list internal pop$($struct node $**$list$,$ struct

node $**$node$)$ which takes a pointer to a pointer list and a pointer to pointer to a node

preforms a simple pop:

$1.$ Get the node pointed to by $*$list

$2.$ Update $*$list to point at $(*$list$)->$next

$3.$ Update $*$node to point at retrieved node

The function should return an int where $0$ is success, and $-1$ is failure.

list prepend Create a function int list prepend$($struct node $**$list head, struct

node $**$free list, int value$)$ which performs the prepend steps described above using

the helper functions list internal prepend and list internal pop

list append Create a function int list append$($struct node $**$list head, struct node

$**$free list, int value$)$ which performs the append steps described above using the

helper functions list internal prepend and list internal pop

list pop Create a function int list pop$($struct node $**$list head, struct node $**$free list$)$

which performs the pop steps described above using the helper functions list internal prepend

and list internal pop

list print Create a function int list print$($struct node $*$list head$)$ which prints the

current values of the list on a single line as $1->2->3->4...$

$4$

main Create a main function that creates an array of list nodes, and initializes them, stor$-$

ing the struct node $*$list head, struct node $*$free list and struct node $*$list tail

pointers. The function should then run a loop which accepts from stdin a line conta