連結串列

說明

實作一個雙向鏈結串列。

和陣列一樣，鏈結串列是一種簡單的線性資料結構。 許多常見的資料型態都可以用鏈結串列實作，例如佇列、堆疊和關聯式陣列。

鏈結串列是一群稱為節點的資料元素集合。 在單向鏈結串列中，每個節點都儲存一個值，以及一個指向下一個節點的連結。 在雙向鏈結串列中，每個節點還儲存一個指向前一個節點的連結。

你要撰寫一個雙向鏈結串列的實作。 先實作一個 Node 來儲存一個值，以及指向前一個和下一個節點的指標。 接著實作一個 List，它會保存第一個與最後一個節點的參照，並提供類似陣列的介面來新增和移除項目：

• push（在尾端插入值）；
• pop（從尾端移除值）；
• shift（從前端移除值）。
• unshift（在前端插入值）；

為了讓你的實作保持簡單，測試不會涵蓋錯誤情況。 具體來說：pop 或 shift 永遠不會在空串列上被呼叫。

想多了解鏈結串列，請參閱 Wikipedia 上的鏈結串列。