Double$-$Ended Queue

While a stack allows the insertion and extraction of elements at only one end, and a queue allows insertion at one end and extraction at the other end, a double$-$ended queue $($deque$)$ enables the insertion and extraction of elements at both ends.

Using linked lists, describe the insertion and deletion operation at each end with a time complexity of O$(1).$

You should explicitly:

$1.$ Describe the data structure, specifying the type of linked list.

$2.$ Explain the PUSH$-$FRONT$($Q$,$ x$)$ operation, which inserts the element x at the front end of the queue Q$.$

$3.$ Explain the POP$-$FRONT$($Q$)$ operation, which extracts the element at the front end of the queue Q$.$

$4.$ Explain the PUSH$-$BACK$($Q$,$ x$)$ operation, which inserts the element x at the back end of the queue Q$.$

$5.$ Explain the POP$-$BACK$($Q$)$ operation, which extracts the element at the back end of the queue Q$.$