2. (20 points) Consider an array-based implementation of singly and doubly linked list(s). Assume that each node in the linked list has the following structure: typedef structgeneric_node int info struct -generic_node next; struct -generic_node *prev; generic_node An array of genericnode was allocated and initialized as follows: generic_node array -(generic_node *)malloc (sizeof (generic_node)* generic-node *unused-list &(array[0]); int i; for (i = 0; i next ; return (void )node; void myfree (void *node) t generic node gnode gnode->next = unused-list ; unused-list = gnode; gnode -(generic_node *)node (b) (4 points) The generic.node will be used to implement a priority queue using a circular doubly linked list through typecasting. The structure used for the priority queue is defined as follows: typedef struct _lnode int info; struct _1node next; struct _1node *prev; 1node In the main function, the following two lines are executed: lnode *dummy_header(node *)mymalloc); dummy-header->next -dummy-header->prev dummy-header ; Show how the contents of the array in (a) would change in the following table. Also, show the contents of dummy header and unu sed list. index info next prev dummy header: unused_list (c) (10 points) The following function implements the dequeue operation from a circular doubly linked list. Note that it dequeues the node next to dummy header lnode 1node_dequeue (lnode *dummy_header) inode *curr = dummy-header->next; /* curr is the node next to dummy-header */ if (curr = dummy-header) { /* empty priority queue / return NULL (curr->next)->prev-curr->prev curr->prev)->next-curr->next; non-empty priority queue return curr /* remove curr from After running the program for a while, we have the following contents in array, dummy header, and unused list index infonext|prev 109 107 0 0 3 103 7 1 10 2 2006 dummy_header: 5 unused.list: 1 (i) (4 points) Draw the doubly linked list, clearly indicating the dummy header. For each node, clearly indicate the fields info, next, and prev (ii) (6 points) Suppose we execute the following statements in the main function: lnode *nodelnode_dequeue (dummy_header); myfree(node) nodelnode_dequeue(dummy_header); myfree (node) Update the preceding table and the pointers dummy header and unused.list to reflect the effects of those statements 2. (20 points) Consider an array-based implementation of singly and doubly linked list(s). Assume that each node in the linked list has the following structure: typedef structgeneric_node int info struct -generic_node next; struct -generic_node *prev; generic_node An array of genericnode was allocated and initialized as follows: generic_node array -(generic_node *)malloc (sizeof (generic_node)* generic-node *unused-list &(array[0]); int i; for (i = 0; i next ; return (void )node; void myfree (void *node) t generic node gnode gnode->next = unused-list ; unused-list = gnode; gnode -(generic_node *)node (b) (4 points) The generic.node will be used to implement a priority queue using a circular doubly linked list through typecasting. The structure used for the priority queue is defined as follows: typedef struct _lnode int info; struct _1node next; struct _1node *prev; 1node In the main function, the following two lines are executed: lnode *dummy_header(node *)mymalloc); dummy-header->next -dummy-header->prev dummy-header ; Show how the contents of the array in (a) would change in the following table. Also, show the contents of dummy header and unu sed list. index info next prev dummy header: unused_list (c) (10 points) The following function implements the dequeue operation from a circular doubly linked list. Note that it dequeues the node next to dummy header lnode 1node_dequeue (lnode *dummy_header) inode *curr = dummy-header->next; /* curr is the node next to dummy-header */ if (curr = dummy-header) { /* empty priority queue / return NULL (curr->next)->prev-curr->prev curr->prev)->next-curr->next; non-empty priority queue return curr /* remove curr from After running the program for a while, we have the following contents in array, dummy header, and unused list index infonext|prev 109 107 0 0 3 103 7 1 10 2 2006 dummy_header: 5 unused.list: 1 (i) (4 points) Draw the doubly linked list, clearly indicating the dummy header. For each node, clearly indicate the fields info, next, and prev (ii) (6 points) Suppose we execute the following statements in the main function: lnode *nodelnode_dequeue (dummy_header); myfree(node) nodelnode_dequeue(dummy_header); myfree (node) Update the preceding table and the pointers dummy header and unused.list to reflect the effects of those statements