$(3$ pts$)$ Write an algorithm for the implementation of the method swap$\_$ends$()$ of

the DLLDeque data structure below. DLLDeque implements the Deque

interface using a doubly$-$linked list. The method swap$\_$ends$()$ swaps the node

$($not just the data$)$ at the head of the list with the node at the tail of the list.

$1$ from Interfaces import Deque

$3$ class DLLDeque$($Deque$)$:

$4$ class Node:

$5$def$\_\_$inif $($self$,$ x: object$)$:

$6$self. $\}$x$=$

$7$self.next $=$ None

$8$self.prev $=$ None

$10$def nit $($self$)$:

$11$ self.dummy $=$ DLList.Node$($None$)$

$12$self.dummy.next $=$ dummy

$13$ self.dummy.prev $=$ dummy

$14\}\backslash$mathrm$\{$ self.n$=0$

$15$ return

$16$

$17...$

$19$ def swap$\_$ends$($self$)$:

$20$# todo

$21$ return