Question 13

1. Doubly-Linked List (DLLdel): Each node has pointers to both next and prev. To delete a node given a pointer $p$, we update $p\rightarrow prev\rightarrow next = p\rightarrow next$ and $p\rightarrow next\rightarrow prev = p\rightarrow prev$. This requires no traversal and takes $\Theta(1)$ time in the worst case.
2. Singly-Linked List (SLLdel): Each node only points to next. Although an internal node can be deleted in $O(1)$ by copying the data of $p\rightarrow next$ into $p$ and deleting $p\rightarrow next$, this trick fails when $p$ is the last node of the list. Deleting the last node requires finding its predecessor, which necessitates traversing from the head pointer, taking $\Theta(n)$ time in the worst case.

Thus, SLLdel is $\Theta(n)$ and DLLdel is $\Theta(1)$.