CS2110-Project 5 Linked List Solved

In this assignment, you will be implementing a list data structure whose underlying implementation is a doubly-linked list.

1         Linked List Implementation
We are implementing a doubly-linked list. You are given a list which has a head pointer pointing to the first node in the list. Each node contains a next pointer to the next node in the list, a prev pointer to the previous node in the list and a data pointer to a Process. Refer to the following diagram for a visual representation to help you out when implementing your linked list!

 

2         Instructions
You have been given one C file - list.c in which to implement the data structure. Implement all functions in this file. Each function has a block comment that describes exactly what it should do and there is a synopsis included below.

•    Process *create_Process(char *, int): Takes in a string and an int. Create a new process with name equal to the passed in string, and priority equal to the passed in int. Assign a new PID one higher than the previous PID, with the first one being 0.

•    ListNode *create_node(Process *): Takes in a Process, creates a ListNode containing that Process as its data, and returns the ListNode.

•    List *create_list(): creates an empty list and returns it

•    void push_front(List *, ListNode *): adds a ListNode to the front of the List ( the beginning of the list, so that this node becomes the new head of the list ).

•    void push_back(List *, ListNode *): adds a ListNode to the back of the List ( the end of the list, so that this node becomes the last node in the list )

•    int remove(List *, Process **, int): finds and removes the Process whose PID is equal to the third input. The Process data will be returned via the Process** parameter and the ListNode containing the Process will be removed completely.

•    void destroy_Process(Process *): completely destroys all data in the Process and the Process itself.

•    void destroy(List *): destroys the list itself. This will destroy the list, all nodes within the list, and the Processes within the nodes.

•    int copy_Process(Process *, Process **): creates a deep copy of a Process and returns the deep copy through the Process ** parameter.

•    List *copy_list(List *): creates a deep copy of the list. This includes creating a new list, new nodes, and new Processes in the nodes.

•    int compare_PID(Process *, Process *): Compares the two Processes based off of PID.

•    int compare_name(Process *, Process *): Compares two Processes based on their name

•    int swap_nodes(ListNode *, ListNode *, List *): Swaps the two nodes in the list in place.

•    int sort(List *, int (*compare_func)(Process *, Process *b)): Utilizes the compare function pointer to sort the list (in place) in ascending order.

•    int make_idle(Process *): Append " (idle)" to the end of the name of the passed in process. You must use realloc and any functions you may need from string.h.

•    int make_active(Process *): See if the process name ends with " (idle)" If it does, remove it. You must use realloc and any functions you may need from string.h.

•    int map_inplace(List *, int (*map_func)(Process *)): Calls the map function pointer on each Process in the list.

•    Process **list_to_array(List *, int): Converts the linked list data structure to an array of pointers to Processes while removing the linked list structure itself so that only the process pointers remain.

You should not be leaking memory in any of the functions. For any functions utilizing malloc, if malloc returns null, return either 0 or null (based on the function header) and ensure that no memory is leaked.

Be sure not to modify any other files. Doing so may result in point deductions that the tester will not reflect.