你正在參與一個專案,要為繁忙的鐵路網開發一套列車調度系統。
你接到的任務是為調度系統中的列車路線開發一個原型。 每條路線由一連串車站組成,也就是某一班列車沿途停靠的車站序列。
你的團隊決定用雙向鏈結串列來表示時刻表上的每一條火車路線。火車路線上每一站,都會用鏈結串列中的一個節點來表示。
你不需要煩惱各站的抵達和出發時間。每一站單純用一個數字來表示就好。
路線可以延伸,在路線的開頭或結尾加入車站。路線也可以縮短,把開頭或結尾的車站移除。
有時候某個車站會關閉,這時就必須把這個車站從路線中移除,即使它不在路線的開頭或結尾也一樣。
路線的大小不是用火車行駛的距離來衡量,而是看它停靠幾站。
鏈結串列是電腦科學中一種基礎的資料結構,也常用來實作其他資料結構。 顧名思義,它是一串彼此鏈結在一起的節點。 它是由「節點」組成的串列,每個節點會連接到它的一個或多個鄰居。 在單向鏈結串列中,每個節點只連接到它後面那個節點。 在雙向鏈結串列中,每個節點同時連接到它前面的節點和它後面的節點。
如果你想更深入了解鏈結串列,可以看看這篇文章,裡面用漂亮的圖解來說明。
你將實作一個雙向鏈結串列。
請實作一個節點,用來儲存值,以及指向前一個和下一個節點的指標。
接著實作一個鏈結串列,它會保存第一個與最後一個節點的參考,並提供類似陣列的介面來新增和移除項目:
push(在尾端插入值);pop(移除尾端的值);shift(移除前端的值);unshift(在前端插入值);delete(移除第一個符合的節點)為了讓你的實作保持簡單,測試不會涵蓋錯誤情況。具體來說:pop 或 shift 永遠不會在空的鏈結串列上被呼叫。