[理工] [資結] 98台大醫工

[iamhebe ( bbb)]

6. For the following statements about linked-list,
   which of the following statement(s) is(are) true?
(A) The operation of inserting or deleting a node of a
    singly-linked-list has the complexity O(1).
(B) If a singly-linked-list is used to implement a stack,it is more
    efficient to have the top of the stack at the tail of the list.
(C) If a singly-linked-list is used to implement a queue, it is more
    efficient to have the front of the queue to be at the head of the
    linked list, and the rear of the linked list to be at the tail of
    the list.
(D) Given the pointer to the node to be deleted, the node deleting
    operation if a doubly-linked-list has lower complexity than that
    of a singly-linked-list.
(E) One of the advantages of circular linked list is that it is able to
    traverse the list starting at any point.

答案是(C)(D)(E)

但我寫(B)(C)(E)
想問(B)為什麼是false?

另外(D)在給定要刪節點的指標下，
double 不是比 single 來的複雜嗎？
因為 double 不是有兩個指標要變更
而 single 只要變更一個指標就好

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 111.248.213.75
→ ybite:(B)我是覺得不一定。因為假如他沒有記錄Tail的Pointer的話，
→ ybite:光要找到Tail就要O(n)的時間，這時放在Head還比較經濟。
→ ybite:(D)再複雜都是O(n)找+O(1)砍，應該還相同Time Complexity?
→ shmna7068:(D)已經給了node指標 但是只有double linked list找的到
→ shmna7068:前後node，single必須有一邊要從頭找起