Need Questions 2-6 answered, please

Tasks: 1. Using your favorite programming language, implement a singly linked list with the following operations: addFirst, removeFirst, addLast, removeLast, getFirst, getLast, size. 2. [2 bonus marks*] Write and implement a recursive algorithm that shows all the elements of the single linked list, starting from the head. Explain the worst-case running time of your algorithm. 3. Implement a stack on the singly linked list with the operations of Lab Assignment 1. Hint: Using the same Stack class you implemented, change the array to an object of the singly linked list class. The functionality of push and pop is now based on the methods of the linked list class. 4. Practical application 1: Balanced parentheses. (a) Implement the balanced-bracket checker algorithm of Lab Assignment 1 using the singly linked list implementation of the stack. (6) Explain how your algorithm checks for balanced parenthesis in O(n), when the input is a string of length n. 5. Implement a queue on the singly linked list of Item #1, with the following operations: enqueue, dequeue, front, size, isEmpty. Note: both operations, enqueue and dequeue, must run in O(1). 6. Practical application 2: The merge problem. Given two sorted lists of integers, A and B, the aim is to merge A and B, producing a sorted list S. (a) Write an algorithm that stores A and B in two queues (one in each queue), merges A and B, and outputs a sorted list S in O(n) worst-case time. Note: your algorithm must use queues for A, B and S. (b) Implement your algorithm in your favorite programming language. (c) Explain how your algorithm runs in O(n), where n is the length of S. (d) [2 bonus marks *] Run your algorithm on randomly generated sorted lists A and B of different sizes: 100, 200, 300, ..., 2000 and record the CPU time taken by the algorithm. Create a table (or a plot) and explain how your algorithm runs in O(n) by inspecting your results. * Maximum 2 bonus marks. Tasks: 1. Using your favorite programming language, implement a singly linked list with the following operations: addFirst, removeFirst, addLast, removeLast, getFirst, getLast, size. 2. [2 bonus marks*] Write and implement a recursive algorithm that shows all the elements of the single linked list, starting from the head. Explain the worst-case running time of your algorithm. 3. Implement a stack on the singly linked list with the operations of Lab Assignment 1. Hint: Using the same Stack class you implemented, change the array to an object of the singly linked list class. The functionality of push and pop is now based on the methods of the linked list class. 4. Practical application 1: Balanced parentheses. (a) Implement the balanced-bracket checker algorithm of Lab Assignment 1 using the singly linked list implementation of the stack. (6) Explain how your algorithm checks for balanced parenthesis in O(n), when the input is a string of length n. 5. Implement a queue on the singly linked list of Item #1, with the following operations: enqueue, dequeue, front, size, isEmpty. Note: both operations, enqueue and dequeue, must run in O(1). 6. Practical application 2: The merge problem. Given two sorted lists of integers, A and B, the aim is to merge A and B, producing a sorted list S. (a) Write an algorithm that stores A and B in two queues (one in each queue), merges A and B, and outputs a sorted list S in O(n) worst-case time. Note: your algorithm must use queues for A, B and S. (b) Implement your algorithm in your favorite programming language. (c) Explain how your algorithm runs in O(n), where n is the length of S. (d) [2 bonus marks *] Run your algorithm on randomly generated sorted lists A and B of different sizes: 100, 200, 300, ..., 2000 and record the CPU time taken by the algorithm. Create a table (or a plot) and explain how your algorithm runs in O(n) by inspecting your results. * Maximum 2 bonus marks