and removed from both the front and the rear. Write either an array$-$based

$($modify Fig $4\mathrm{.}9$ in the eBook$)$ or linked implementation $($modify Fig $4\mathrm{.}10$ in the

eBook$)$ for the deque.

Notes:

You need to submit each program with a picture of its output

Figure $4\mathrm{.}9$ The linked list insertion process. $($a$)$ The linked list before insertion.

$($b$)$ The linked list after insertion. marks the element field of the new link

node. $2$ marks the next field of the new link node, which is set to point to what

used to be the first node in the right partition $($the node with value $12).$ marks

the next field of the last node in the left partition. It used to point to the node

containing $12$; now it points to the new node containing $10.$

Figure $4\mathrm{.}10$ The linked list removal process. $($a$)$ The linked list before removing

the node with value $10.($b$)$ The linked list after removal. $1$ marks the list node

being removed. it is set to point to the element. $2$ marks the next field of

the preceding list node, which is set to point to the node following the one being

deleted.