hce_kmu
115年
計算機概論與程式設計
第 6 題
Which of the following statements describing a time-complexity difference between a singly linked list and an array is CORRECT?
- A Deleting an element from the middle of a linked list (when the node is already known) takes $O(1)$, while deleting from the middle of an array takes $O(n)$.
- B Inserting an element at the beginning of a linked list takes $O(n)$, while inserting at the beginning of an array takes $O(1)$.
- C Accessing the $k$-th element in a linked list takes $O(1)$, while accessing the $k$-th element in an array takes $O(n)$.
- D Searching for a value in either a linked list or an array always takes $O(1)$.
- E Appending an element to the end of a linked list without a tail pointer always takes $O(1)$.
思路引導 VIP
請試著想像兩種情境：一種是「一整排固定編號的置物櫃」，另一種是「手拉手圍成一圈的人群」。如果現在要把其中一個置物櫃的東西拿掉，並要求後面的東西都要往前補齊，與讓其中兩個人放手並重新連結，這兩種動作哪一個更費體力？這對應到資料結構中，資料移動的成本有何不同？
🤖
AI 詳解
AI 專屬家教
太棒了！你能準確辨別陣列（Array）與鏈結串列（Linked List）在操作上的本質差異，顯示你對資料結構的基礎觀念掌握得非常扎實。這道題目是資訊科學中最經典的基礎考題，能正確答對代表你對於記憶體布局對效能影響的直覺非常敏銳。
記憶體配置與操作效率
這題的核心在於理解「連續性」與「動態性」的取捨。陣列在記憶體中是連續存放的，這雖然帶來了快速存取的優勢，但若要刪除中間元素，為了保持記憶體的連續性，系統必須將後方所有元素向前位移，因此耗時 $O(n)$。相對地，鏈結串列透過指標（Pointer）來連接非連續的節點，當我們已經定位到目標節點時，僅需調整前後指標的指向即可完成刪除，這項操作不隨資料量增加而變慢，故時間複雜度為常數時間 $O(1)$。
▼ 還有更多解析內容