One: (25 points. 4 points each for first five questions. 5 points for question 6) You textbook listed common functionality that a list should have (refer to Table 2.1.2). However, your book only implemented algorithm for insertAfter and remove. In this problem, you are asking to implement the rest common functionality in table 2.1.2.

1. append: which append the given node after the tail of the list
2. prepend: which insert the given node to the front of the head of the list
3. printList: which print all node data in order as their node in the list
4. sort: Sort the list items in ascend order
5. isEmpty: Return true if the list is empty; false otherwise
6. For printListReversely functionality, if the list is a single linked list, we cannot step through the list reversely. How would you implement this printListReversely algorithm?

Two: (15 points, 5 points each) In problem one, we didnt implement getLength function. This function has some challenge.

1. For getLength function, one implement is that we can step through the list, from head to tail, and count. Write algorithm for this implementation
2. In previous implementation, what is the run time?
3. If I want constant run time for getLength function, what change needs to be made for List data structure? How this change will affect the implementation of other functions such as insertAfter and remove?