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)