Q1 (20 pts) a. [5 pts] Given an array as a Write and test function Rearrange to rearrange the array elements all even numbers appear before all the odd numbers in the modified array If the array was 17 15 18 12 10 5 4 1 7 6 Then after calling function Rearrange Array elements are: 8 12 10 6 17 15 7 b. 19 pts) Given a single linked list of integers, write and text function Rearrange to modify the linked list such that all even numbers appear before all the odd numbers in the modified linked list. Also keep the order of even and odd numbers same. Examples: Input: 17->15->8->12-10->5-54->1->7>>NULL Output: 8->12->10->4->->17->15->5>>7->NULL Example 2: Input: 8->12->10->5->->->6->NULL Output 8->12-10-4-6- >> NULL [6 pts] After implementing and testing the above functions, answer the following: 1. What is the space complexity of each data structure (array and linked list)? 2 Compare the time complexity to build insert a new item at the end of the data structure, delete antem, and find an item in each data structure 3. Which data structure would you prefer to use and why? 03. [10 pts] Write an algorithm to test if double linked list is Palindrome. Using the following format for an algorithm Algorithm Title: Input Output Algorithm steps: 2 CpE 207 Data Structures Fall 2020 2021 Important Note: Test all function show output 2 Your program should be well-structures and well-documented 3. Indicate the expected time complexity of each function 4 You should submit your own code.ie. you are not allowed to copy from the internet, any other person or references