Note: here the value is taken as const . So please make the code works like that.

1. Build a doubly linked list given the keyboard inputs or the user provided data file;
2. Perform a insertion-sort (in the ascending order of the value) for the above linked list, and print the list out to the screen. For comparison purpose, please also print the unsorted linked list.

Your doubly linked list node data structure is defined as in the following:

struct mynode { int const value; struct mynode *next; struct mynode *prev; }; 

A pre-prepared data file example is listed at below:

30 20 50 70 10 0 

Given the file above, your program should build a linked list with 5 nodes. Note that 0 indicates the end of the data file and 0 should not be included in the linked list. Given the above 5 data, your unsorted linked list should look like:

30<==>20<==>50<==>70<==>10 

Note that 30 is stored in the head node and the 10 is stored in the tail node. Your program's implementation must include the following features:

• Your program must be compiled from 3 source files:
  • main.c(Handles input and output, as well as top-level program logic.)
  • node.h(Declares the data structure and functioninsertsort, which sorts a given doubly linked list with the ascending order), andprintlist, which prints a linked list to the screen.
  • node.c(Defines the functioninsertsortandprintlist, as declared innode.h.)
• Yournode.hfile must contain the proper preprocessor directives to prevent multiple inclusion.
• The main function must usescanffunction call to read the input data from keybord (note that the input redirection can be used to directly read the data from a data file). The number of data (in the data file) is not pre-determined.
• Since the value field is declared as a constant, its value cannot be updated after it is initialized. The initialization must be done with scanf(). For example, if a struct mynode pointer p is poing to a node, the initialization should be done as "scanf("%d", &(p->value));". Certain version of gcc may report a compiling warning on this statement, it is OK for this assignment.
• The functioninsertsortmust be declared exactly as follows.
  • return value:struct mynode *.
  • argument (only one):struct mynode *, which is the head of the given linked list.
  • Note that you must implement the insertsort() function by yourselves and cannot use any existing implementation from other library. You have to use insertion sort algorithm instead of other sorting algorithm.
• The functionprintlistmust be declared exactly as follows.
  • return value: void.
  • argument (only one):struct mynode *, which is the head of the given linked list.

II. Grading

• Minimum Requirements
  • Correctly read the input data provided either from the keyboard (by default) or from a data file (if input redirection is used). The data entered from keyboard should match exactly to the data file (if provided), i.e., no other cutomized commands (not specified in the description) are allowed.
  • Proper declaration and definition of the functions required.
  • Once a node is created, you cannot change its value. Therefore, when you sort the the linked list, you have to move the node around rather than swap nodes' values. Note: the node's value field is declared as int const so you cannot modify the value anyway.
  • Correctly output the linked list (before and after being sorted) to the screen.
  • Correctly perform the insertsort algorithm (but not any other sorting algorithm).
  • The correct execution of your program without any unexpected errors and unnecessary extra debug messages, including the segmentation fault.
  • Your work must be submitted in files with the following names: main.c node.h node.c
  • These files must compile on a department LINUX machine with the following command: make. Therefore a Makefile has to be provided with your submission.
  • A clean compilation without any error and warning message.
  • In addition, you must provide a README file (in txt format) to decribe the project. Please see the submission instruction for the requirement.