Can you implement the dynamic-set operation insert on a singly linked list in $O(1)$ time? How about DELETE?

SINGLY-LINKED-LIST-INSERT(L, x)

1 x.next = L.head

2 L.head = x

SINGLY-LINKED-LIST-DELETE(L, x)

1 if x.next == NIL:

2     findTail = head

3     while findTail.next ≠ x:

4         findTail = findTail.next

5     findTail.next = NIL

6 else:

7     x.key = x.next.key

8     x.next = x.next.next

SINGLY-LINKED-LIST-INSERT runs in $\Theta(1)$ constant time. SINGLY-LINKED-LIST-DELETE runs in constant time for all cases except when the given value of $x$ is the tail of list $L$ in which case we must find $x$’s previous element which means this operation takes $\Theta(n)$ linear time. (Note that by the text’s definition, the tail must have a next value of NIL, so setting $x$’s key value to NIL is not sufficient to correctly delete the $x$ node)