啟迪思維：雙向循環鏈表

文章目錄：

01. 博文簡介：

02. 概念：

03. 示例圖：

04. 優缺點：

05. 代碼分析：

06. 運行環境：

07. 題記： 

一：概念

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接後繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和後繼結點，一般我們都構造雙向循環表，STL。

二：示例圖

三：鏈表的優缺點

鏈表最大的一個缺點，就是查找一個元素，必須整個鏈表遍歷，也可以看出這種數據結構便於插入或者刪除一個接點。

四：代碼分析

1、獲取節點信息

        
 DLNode<T>* GetElemP(size_t i)       j =      DLNode<T> *p = 
              p = p->         j++     }(p != head && j < 
       
    
 DLNode<T>* GetElemE( T &e)      DLNode<T> *p = head-> 
     (p != head && e != p->         p = p->  
      }

2、插入節點

 插入過程如下圖：

 代碼分析如下：

    
  Insert(size_t i, T &     
     DLNode<T> *p =     
      
  Insert(DLNode<T> *p, T &     
     DLNode<T> *q =  DLNode<T>     
     q->next = p->     
     q->prev = 
     
     p->next->prev =     
     p->next =     
  AddHead( T &      
  Insert( T &     Insert( }

3、刪除節點

刪除節點如下圖，可以從圖中看到，刪除節點僅僅改變前驅和後繼節點相關的指針域，這個就是為什麼數據刪除高手還可以找回來原因；

代碼分析如下：

    
  Delete( T &     
     DLNode<T> *p =     
     std::auto_ptr<DLNode<T> >     
     p->next->prev = p->     
     p->prev->next = p-> }

    
      
     DLNode<T> *p = head-> 
     
     (p !=         std::cout<<<<p->         std::cout<<<<         p = p->  }

    
      
     DLNode<T> *p = head-> 
     
     (p != head && p !=          
         std::auto_ptr<DLNode<T> >         std::cout<<         std::cout<<         
         p = p->      
     head->next = head->prev = }

6、是否為空和計算鏈表長度

 head->next =
 i = <T> *p = head->
    (p !=
        p = p->
        i++

      std::cout<<<<     ( i = ; i <= ; ++       AddHead(     AddHead(      std::cout<<<< 
     std::cout<<<<Length()<< 
     std::cout<<<<     Delete(     std::cout<<<< 
     std::cout<<<<Length()<< 
     std::cout<<<< 
       Delete(      std::cout<<<<Length()<< }

9、完整代碼

1

2

六：題記

1

2

3

 歡迎繼續閱讀“啟迪思維：數據結構和算法”系列