漫遊於歷史與現代之間

資料結構有一個基本結構叫做「鏈結串列」，裡面有一個比較難的叫做「雙向串列」，這個地方我感到各個教科書都寫得很奇怪，我發現將書上的圖示改良以後，就會便的很好理解，所以與大家分享。先看雙向串列書上畫的樣子：

姑且先別管那些擾人的箭頭，只看一個就好。

在C語言中我們會這樣宣告：

typedef struct dnode{

  struct dnode *llink; 

  int data; 

  struct dnode *rlink; 

}dlist_node;

typedef dlist_node *dlist_pointer;

宣告以後就會變得如此：

但如果要進行實作，會發現第一張圖根本不知道箭頭指到哪邊，所以我把第一張圖改良以後變成如此。

這樣所有的脈絡就很清晰了，現在進行實作新增結點看看：

按照串列的慣例，都是先把掛上新增的節點，然後在截斷舊的線，所以ptr的左線和右線分別步驟是

(1)ptr->llink = current->llink; 

(2)ptr->rlink = current;

然後剪斷舊線

(3)current->llink->rlink = ptr;

(4)current->llink = ptr;

其他題目也依此類推，有此概念後，雙向鏈結串列變得輕而易舉。