雙向鏈結串列

說明

使用 unsafe Rust 撰寫一個雙向鏈結串列，其中包含可走訪整個串列的迭代器，以及一個能有效率地修改串列的游標。

雙向鏈結串列是電腦科學中一種基礎的資料結構。

雙向鏈結串列中的每個節點都包含資料，以及指向下一個與前一個節點的指標（如果存在的話）。

只要已經持有某個位置的參考，就能有效率地在串列中的任何位置新增節點。同樣地，也能以常數時間把另一個串列的所有元素插入任何位置。

在 Rust 裡，鏈結串列很少被使用，但偶爾會讓新手在嘗試實作時卡住。他們往往會發現，要跟還不熟悉的借用檢查器打交道，出乎意料地困難。

關於 unsafe 的注意事項

請記住，unsafe Rust 的目標是在編譯器無法協助我們保證正確性的情況下，仍然寫出安全的程式碼。使用者必須無法單靠我們所公開的安全介面，造成任何形式的記憶體不安全。

請為你必須維持的安全性關鍵不變式撰寫文件，並為每個 unsafe 區塊加上註解，說明它為什麼是安全的。

任何要求呼叫者維持安全性關鍵不變式的函式，都應該標記為 unsafe，包括私有函式。

步驟 1

實作在前端與後端新增和移除元素（push 與 pop）的功能。這樣就足以把串列當作雙端佇列使用。另外也請實作 len 和 is_empty 函式。

在完成後的實作中，所有對串列的修改都應該透過游標結構完成，以盡量減少重複的程式碼。LinkedList 上的 push_* 和 pop_* 方法，在模組 pre_implemented 中是依據必要的游標方法定義的。如果你願意的話，現在可以先跳過 Cursor 結構並覆寫這些方法，但請在最後把它們改回來。

步驟 2

使用 Iter 結構實作從前端到後端走訪串列的迭代功能。

步驟 3

完成游標的功能。它應該能夠移動到任何位置，並在該處插入或移除元素。

步驟 4

為你的 LinkedList 實作 Drop trait，以清理資源。

步驟 5（進階且為選用）

最後這兩件事的測試，是透過功能旗標 advanced 條件式編譯的。請在 Cargo.toml 檔案的 [features] 底下加入 default = ["advanced"] 這個鍵，以啟用它們。

為了讓你的結構的使用者擁有最大的彈性，請確保你的 LinkedList<T> 對 T 具備共變性。舉例來說，這表示 LinkedList<&'static T> 也可以當作 LinkedList<&'a T> 使用。關於 Rust 中變異性的說明，請參見 Rustonomicon。

請確保你的串列能安全地跨執行緒邊界傳送與共享，並以手動實作 Send 和 Sync 的方式向型別系統表達這一點。這兩個 trait 通常會自動推導，但因為使用了裸指標，在這裡並不會自動實作。關於它們重要性的詳細說明，請參見 Send 與 Sync 的文件，以及 rustonomicon 的相關章節。