五、假設 L 是一指標（pointer），指向一個雙鏈結串列（doubly linked list），圖示如下。  請設計一個程式（procedure）：當輸入（input）為 x, y 與 L 時（x 為存在於 L 所指的串列內之資料，y 為不存在於 L 所指的串列內之資料），此程式可在 L 所指的串列內增加（insert）y 於 x 之後。增加 y 之後，串列仍必須為雙鏈結結構。（20 分)

四、當輸入（input）為x1, x2, …, xn時，塞入排序（insertion sort）可將此n個輸入值從小到大排列。塞入排序的執行（execution）可簡略表示如下： For i＝2, 3, …,n, insert xi into x1, x2, …, xi−1 such that these i data items are sorted. 例如，當輸入為 7, 5, 1, 4, 3, 2, 6 時，塞入排序的執行如下： i = 2: 5, 7 i = 3: 1, 5, 7 i = 4: 1, 4, 5, 7 i = 5: 1, 3, 4, 5, 7 i = 6: 1, 2, 3, 4, 5, 7 i = 7: 1, 2, 3, 4, 5, 6, 7 若 T(n) 表示執行塞入排序所需的時間複雜度（time complexity），其中 n 表示輸入值的個數。請用 O( f(n)) 的符號估算 T(n) 在最佳情況（best case）與最壞情況（worst case）之值，其中 f(n) 表示 n 的一個函數。（20 分）

其他申論題