Assume we implement a Deque data structure with a Linked List (instead of a Python List). The Linked List implementation is a singly-linked list with a head reference and nodes contain next references to the next item in the Linked List (similar to what we discussed in lecture and the textbook).

In this implementation, assume the rear of the deque is located at the head reference, and the front of the deque is at the end of the Linked List.

State what the O-notation for the following operations are:

• addRear - insert an element at the rear of the deque
• removeRear - remove an element at the rear of the deque
• addFront - insert an element at the front of the deque
• removeFront - remove an element at the front of the deque