1 Step 1: initialise the list (20 marks) In this section, you will define the structures that represent the nodes of the list and the list as a unit. You will also write four auxiliary functions: allocator, which allocates a single node with malloc and updates an integer counter, deAllocator, which frees a single node with free and updates the same counter, initialiseList, which calls allocator to allocate the list head and tail and initialise them, and freeList, which calls deAllocator to free the head and the tail of the list and set all pointers to NULL. Start by defining a node as struct node \{ int i; struct node next; struct node prev; \}; where i is the integer stored in the node, next is a pointer to the next node, i.e. the right neighbour of the node, and prev is a pointer to the previous node, i.e. the left neighbour of the node. The second structure you need is a list handle, containing all information you need to access the list, e.g. struct list \{ struct node head; 1 2 struct node *tall; struct node *right; struct node *left; int length; \}; where head is a pointer to the list head, i.e. the leftmost node of the list, tail is a pointer to the list tail, i.e. the rightmost node in the list, left is a pointer to the node storing the last-added odd integer, right is a pointer to the node storing the last-added even integer, and length is the number of nodes in the free space. The program in Listing 1 declares a list called myList, allocates the head and tail of the list and connects them, makes myList . left and myList. right point to the head and tail of the list, initialises myList . length to 0 , prints the list and the value of the allocation counter, frees the nodes, set all list pointers to NULL and length to 1, and prints the counter again. Listing 1: Explicit initialisation The auxiliary function printList is defined in Appendix A. After adding all required definitions, compile the code and run it. The output should be The program in Listing 1 is not very readable. Rewrite it as int main() int counter 0; struct list myList; initialiselist (\&myList, \&counter); printlist(\&myList, \&counter); freelist (\&myList, \&counter); printlist (\&myList, \&counter); \} Listing 2: Compact initialisation by defining the following auxiliary functions: void *allocator (int size, int *counter); void deAllocator(void *p, int *counter); void initialiselist(struct list *pList, int *counter); void freelist(struct list *pList, int *counter); Define the functions so that the programs in Listing 1 and Listing 2 have the same output. In particular, - allocator should - allocate size bytes of memory by calling malloc, - check if malloc returned a valid pointer, i.e. a non-null pointer, and, if so, increase the value of the counter by one, and - return the pointer returned by malloc. - deAllocator should - check that the first argument is a valid, i.e. non-null, pointer and, if so, free the memory pointed by the first argument and decrease the counter by one and - return nothing. - initialiselist should - call allocator to allocate the head and the tail of the list, - initialise the members of the list as in Listing 1 , and - return nothing. - freelist should - check that pList->left points to the same node as pList->head, pList->right points to the same node as pList->tail, and pList->length is zero, i.e. that the list does not contain any occupied or free nodes, - if the list is empty, call deAllocator twice to deallocate the head and the tail of the list, and - if the deallocation is successful, set all pointers to NULL and length to 1. Create a C file, step1.c, containing all required headers and definitions and the code in Listing 2. Compile the code and check that it behaves exactly as the program in Listing 1