10-1 Comparisons among lists

For each of the four types of lists in the following table, what is the asymptotic worst-case running time for each dynamic-set operation listed?

$$ \begin{array}{l|c|c|c|c|} & \text{unsorted, singly linked} & \text{sorted, singly linked} & \text{unsorted, doubly linked} & \text{sorted, doubly linked} \\ \hline \text{SEARCH($L, k$)} & & & & \\ \hline \text{INSERT($L, x$)} & & & & \\ \hline \text{DELETE($L, x$)} & & & & \\ \hline \text{SUCCESSOR($L, x$)} & & & & \\ \hline \text{PREDECESSOR($L, x$)} & & & & \\ \hline \text{MINIMUM($L$)} & & & & \\ \hline \text{MAXIMUM($L$)} & & & & \\ \hline \end{array} $$

$$ \begin{array}{l|c|c|c|c|} & \text{unsorted, singly linked} & \text{sorted, singly linked} & \text{unsorted, doubly linked} & \text{sorted, doubly linked} \\ \hline \text{SEARCH($L, k$)} & \Theta(n) & \Theta(n) & \Theta(n) & \Theta(n) \\ \hline \text{INSERT($L, x$)} & \Theta(1) & \Theta(n) & \Theta(1) & \Theta(n) \\ \hline \text{DELETE($L, x$)} & \Theta(n) & \Theta(n) & \Theta(1) & \Theta(1) \\ \hline \text{SUCCESSOR($L, x$)} & \Theta(n) & \Theta(1) & \Theta(n) & \Theta(1) \\ \hline \text{PREDECESSOR($L, x$)} & \Theta(n) & \Theta(n) & \Theta(n) & \Theta(1) \\ \hline \text{MINIMUM($L$)} & \Theta(n) & \Theta(1) & \Theta(n) & \Theta(1) \\ \hline \text{MAXIMUM($L$)} & \Theta(n) & \Theta(n) & \Theta(n) & \Theta(1) \\ \hline \end{array} $$