Implement a String Deque with a Doubly Linked List

Problem: Implement a String Deque from Scratch Implement a double-ended queue Deque that stores strings only. It must support the following operations: addFirst(data): insert string data at the front. addLast(data): insert string data at the back. removeFirst(): remove and return the front element; return null if the deque is empty. removeLast(): remove and return the back element; return null if the deque is empty. peekFirst(): return the front element without removing it; return null if empty. peekLast(): return the back element without removing it; return null if empty. getSize(): return the number of elements currently in the deque. Requirements: A doubly linked list implementation is recommended. Every operation must run in O(1) time. Do not use operations such as Python list.insert(0, x), because front insertion would be O(n). Input Format The first line contains an integer q, the number of operations. The next q lines each contain one operation: addFirst value addLast value removeFirst removeLast peekFirst peekLast getSize value is a string without spaces. Output Format Print one line for each operation that returns a value: removeFirst removeLast peekFirst peekLast getSize If the return value is empty, print null. Constraints 1 <= q <= 100000 1 <= len(value) <= 100 Strings contain printable non-whitespace characters only. Example Input: 10 addFirst b addFirst a addLast c peekFirst peekLast getSize removeFirst removeLast removeLast removeFirst Output: a c 3 a c b null Example Input 10 addFirst b addFirst a addLast c peekFirst peekLast getSize removeFirst removeLast removeLast removeFirst Output a c 3 a c b null