雙鏈表

雙鏈表

雙向鏈表（Double Linked List）
    　雙（向）鏈表中有兩條方向不同的鏈即每個結點中除next域存放後繼結點地址外還增加一個指向其直接前趨的指針域prior
 
注意
    　①雙鏈表由頭指針head惟一確定的
    　②帶頭結點的雙鏈表的某些運算變得方便
    　③將頭結點和尾結點鏈接起來為雙（向）循環鏈表

雙向鏈表的結點結構和形式描述
①結點結構(見上圖a)
     
②形式描述
    typedef struct dlistnode{
         DataType data;
         struct dlistnode *prior*next;
      }DListNode;
    typedef DListNode *DLinkList;
    DLinkList head;

雙向鏈表的前插和刪除本結點操作
    　由於雙鏈表的對稱性在雙鏈表能能方便地完成各種插入刪除操作
①雙鏈表的前插操作

     
    void DInsertBefore(DListNode *pDataType x)
      {//在帶頭結點的雙鏈表中將值為x的新結點插入*p之前設p≠NULL
        DListNode *s=malloc(sizeof(DListNode));//①
        s>data=x;//②
        s>prior=p>prior;//③
        s>next=p;//④
        p>prior>next=s;//⑤
        p>prior=s;//⑥
       }
②雙鏈表上刪除結點*p自身的操作 

  
    void DDeleteNode(DListNode *p)
      {//在帶頭結點的雙鏈表中刪除結點*p設*p為非終端結點
          p>prior>next=p>next;//①
          p>next>prior=p>prior;//②
          free(p);//③
      }
注意
    　與單鏈表上的插入和刪除操作不同的是在雙鏈表中插入和刪除必須同時修改兩個方向上的指針
    　上述兩個算法的時間復雜度均為O()

From:http://tw.wingwit.com/Article/program/sjjg/201311/22874.html