Overview
This practical will once again test your knowledge on linked list, with an emphasize on computational complexity.
Specification
Create a singly linked list for storing positive integers. Each node will store one integer.
For example, 12->3->5->777->111 is such a list. There are hive nodes in this list. 12 is the head node and 111 is the tail node. (111 points to NULL.)
Your linked list starts empty. It should support the following three operations:
- Add x to tail: Create a new node whose data field contains x. Append this node at the end of the list.
For example, for the list 12->3->5->777->111, if we add 2 to the tail, then the list becomes 12->3->5->777->111->2. - Remove from head: If the list is empty, then do nothing. Otherwise, remove the head node from the list.
For example, for the list 12->3->5->777->111, if we remove a node from its head, then it becomes 3->5->777->111. - Find middle node: Find the middle node(s) from the list and returns the corresponding data field(s).
If the number of nodes is odd, then the middle node is just the one in the middle of the list. For the list 12->3->5->777->111, there are ve nodes, the middle node’s data field contains 5.
If the number of nodes is even, then the middle nodes are the two nodes in the middle of the list. For the list 12->3->5->777->111->2, there are six nodes, the middle nodes’ data fields contain 5 and 777.
If the number of nodes is zero, then return 0.
Your implementation should satisfy that all the above three operations take O(1) (constant) time.
Create a main function that takes in one line. The line contains a list of operations. An operation is either of the form “Aint” (e.g., A123, A23, A111) or of the form “R”. A123 means add 123 to the tail. R means remove a node from head. Your output should be the status of the list after all the operations (use the form int1->int2->int3 if there are multiple nodes in the list; use the form int1 if there is only one node in the list; output “empty” if the list is empty). Your output should be followed by the middle value(s).
Please separate your results by space.
1 | Sample input: A888 A111 R A777 A5 A3 |