# 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(n) \\ \hline \end{array}$$