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} \]

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用