雙向，帶頭節點，帶環連結清單的基本操作

前面已經介紹過了不帶頭節點，不帶環的雙向連結清單，以下将介紹帶頭節點，帶環的雙向連結清單的基本操作。

不帶頭結點時，用一個頭指針代表整個連結清單。帶頭節點，則用頭結點來表示整個連結清單。此時，頭結點的資料域是沒有意義的，對其任意指派即可。如下圖：

雙向，帶頭節點，帶環連結清單的基本操作

當連結清單是單向時，隻有一個next指針指向下一個節點。而雙向時，除有next指向下一個節點外，還有一個prev指針指向前一個結點。

當連結清單不帶環時，連結清單的最後一個元素的next域為空，而帶環時，連結清單的最後一個結點的next域要指向頭結點，而頭結點的prev域要指向連結清單的最後一個節點。這樣，整個連結清單就呈一個環狀。

通過上述分析，便可知道，當雙向連結清單為空時，頭結點的next域和prev域均指向頭結點。

1. 連結清單的結點結構

上述分析已經知道，雙向連結清單的一個節點包括三部分：資料域，next域，prev域，是以，結點結構定義如下：

typedef char DlinklistType;//将節點的資料域類型統一表示                                                                               

//定義雙向連結清單的節點結構
typedef struct DlinkNode
{
    DlinklistType data;//資料域
    struct DlinkNode* next;//指向下一個節點
    struct DlinkNode* prev;//指向上一個節點
}DlinkNode;

2. 雙向連結清單的初始化

因為該連結清單是帶頭節點的，是以初始化時，要建立一個頭結點來表示整個連結清單，此時，還沒有真正的節點，是以連結清單為空，是以将頭結點的next指針和prev指針均指向自己，資料任意指派。

因為初始化時，要使頭指針指向頭結點，即要改變頭指針的指向，是以，在函數傳參時，傳的是頭指針的位址，即二級指針（在測試函數中定義的是頭指針，即DlinkNode*類型的變量）。

代碼如下：

//建立結點
DlinkNode* CreateNode(DlinklistType value)
{
    DlinkNode* new_node = (DlinkNode*)malloc(sizeof(DlinkNode));
    new_node->data = value;
    new_node->next = new_node;//初始時，使節點的兩個指針域均指向自身                                                                  
    new_node->prev = new_node;
    return new_node;
}

//初始化雙向連結清單
void InitDlinklist(DlinkNode** phead)
{
    if(phead == NULL)
    {   
        //非法輸入
        return;
    }   
    //申請頭結點,使頭指針指向新節點
    *phead = CreateNode(0);
    return;
}

因為再對頭指針初始化後，頭指針始終指向頭結點，對連結清單進行以下操作（不包括銷毀連結清單）時，改變的是頭結點的相關指針域，而未改變頭指針的指向，是以，在函數傳參時傳的均是頭指針，即一級指針。

3. 對雙向連結清單進行尾插

在尾插時，首先要找到尾節點，因為連結清單是帶環的雙向連結清單，是以，可以通過頭結點的prev指針找到尾節點。然後在尾節點後面建立一個新節點進行插入。

在插入時，需要改變四個指針的指向，兩兩一組，分别為：

（1）原尾節點的next域要指向新節點，新節點的prev要指向原尾節點；

（2）新節點的next域要指向頭結點，頭結點的prev要指向新節點。

代碼如下：

//對雙向連結清單進行尾插
//head為雙向連結清單的頭指針，value為要插入的值
void DlinklistPushBack(DlinkNode* head,DlinklistType value)
{
    if(head == NULL)
    {
        //非法輸入
        return;
    }

    DlinkNode* new_node = CreateNode(value);//建立新節點
    DlinkNode* tail = head->prev;//找到尾節點

    //一共要修改四個指針，兩兩一組進行修改                                                                                            
    //tail和new_node
    tail->next = new_node;
    new_node->prev = tail;
    
    //new_node和head
    head->prev = new_node;
    new_node->next = head;
    return;
}

4. 對雙向連結清單進行尾删

要删除尾節點

（1）首先，要判斷連結清單是否為空。為空的删除失敗。連結清單為空的條件是頭結點head滿足：

head->next = head  或  head->prev = head

（2）若連結清單不為空。

1）首先要根據頭結點的prev指針找到尾節點。

2）再根據尾節點找到它的前一個節點，将找到的前一個節點作為新的尾節點。

4）此時，隻需修改兩個指針域：将新的尾節點的next指針指向頭結點，頭結點的prev指針指向新的尾節點

5）最後釋放原尾節點即可。

代碼如下：

//銷毀節點
void DestoryNode(DlinkNode* node)
{
    free(node);
    return;
}

//對雙向連結清單進行尾删
//head為雙向連結清單的頭指針，即頭結點的位址
void DlinklistPopBack(DlinkNode* head)
{
    if(head == NULL)
    {
        //非法輸入
        return;
    }
    if(head->next == head)
    {
        //空連結清單
        return;
    }
    
    //根據頭節點找到尾節點
    DlinkNode* to_delete = head->prev;
    //根據尾節點找到它的前一個節點
    DlinkNode* prev_node = to_delete->prev;
    //修改兩個指針的指向，使上一個節點作為新的尾節點
    prev_node->next = head;                                                                                                           
    head->prev = prev_node;
    //釋放原來的尾節點
    DestoryNode(to_delete);
    return;
}

5. 對連結清單進行頭插

首先要建立一個新節點，然後在頭結點之後，真正的第一個節點之前插入該新節點，根據頭結點可以找到第一個結點，然後修改這三個結點的相關指針域即可：

共需修改四個指針，兩兩為一組：

（1）頭結點的next指向新節點，新節點的prev指向頭結點

（2）新節點的next指向第一個結點，第一個結點的prev指向新節點。

代碼如下：

//頭插
//head為雙向連結清單的頭指針，value為要插入的值
void DlinklistPushFront(DlinkNode* head,DlinklistType value)
{
    if(head == NULL)                                                                                                                  
    {
        //非法輸入
        return;
    }

    //建立新節點
    DlinkNode* new_node = CreateNode(value);
    //找到第一個節點
    DlinkNode* next_node = head->next;

    //需要修改四個指針的指向
    //head和new_node
    head->next = new_node;
    new_node->prev = head;

    //new_node和next_node
    new_node->next = next_node;
    next_node->prev = new_node;
    return;
}

6. 頭删連結清單

（1）首先，判斷連結清單是否為空，為空則删除失敗

（2）連結清單不為空：

1）根據頭結點找到要删除的第一個結點。

2）使頭結點指向要删除結點的下一個節點，使該下一個節點作為新的第一個節點

3）此時，需要修改兩個指針的指向，将頭結點的next指向下一個節點，下一個節點的prev指向頭結點

4）最後，釋放要删除的結點即可。

代碼如下：

//頭删，head為雙向連結清單的頭指針
void DlinklistPopFront(DlinkNode* head)
{
    if(head == NULL)
    {
        //非法輸入
        return;
    }

    if(head->next == head)
    {
        //空連結清單
        return;
    }
    //根據頭節點找到要删除的第一個節點
    DlinkNode* to_delete = head->next;
    //根據要删除的節點找到他的下一個節點
    DlinkNode* next_node = to_delete->next;
    //隻需改變兩個指針，将下一個節點作為新的第一個節點
    head->next = next_node;
    next_node->prev = head;
    //釋放要删除的節點                                                                                                                
    DestoryNode(to_delete);
    return;
}

7. 在指定位置之前插入節點

要在指定位置之前插入節點

（1）首先，根據指定位置處的節點找到它的前一個節點

（2）然後，将新節點插入到指定結點和它的前一個節點之間。

（3）此時，需要修改四個指針的指向：

1）是前一個節點的next指向新節點，新節點的prev指向前一個節點

2）使新節點的next指向指定結點，指定結點的prev指向新節點

代碼如下：

//在指定位置pos之前插入節點
void DlinklistInsert(DlinkNode* head,DlinkNode* pos,DlinklistType value)
{
    if(head == NULL || pos == NULL)
    {                                                                                                                                 
        //非法輸入
        return;
    }
    //根據pos找到他的前一個節點
    DlinkNode* prev_node = pos->prev;
    DlinkNode* new_node = CreateNode(value);//建立新節點
    
    //prev_node/new_node
    prev_node->next = new_node;
    new_node->prev = prev_node;
    
    //new_node/pos 
    new_node->next = pos;
    pos->prev = new_node;
    return;
}

8. 在指定位置之後插入節點

與上述類似

（1）首先，根據指定位置處的節點找到它的下一個節點

（2）然後，将新節點插入到指定結點和它的下一個節點之間。

（3）此時，需要修改四個指針的指向：

1）使下一個節點的prev指向新節點，新節點的next指向下一個節點

2）使新節點的prev指向指定結點，指定結點的next指向新節點

代碼如下：

//在指定位置之後插入節點
void DlinklistInsertAfter(DlinkNode* head,DlinkNode* pos,DlinklistType value)
{                                                                                                                                     
    if(head == NULL || pos == NULL)
    {
        //非法輸入
        return;
    }

    //建立新節點
    DlinkNode* new_node = CreateNode(value);
   //根據pos找到他的下一個節點
    DlinkNode* next_node = pos->next;
    
    //pos/new_node
    pos->next = new_node;
    new_node->prev = pos;
    
    //new_node/next_node
    new_node->next = next_node;
    next_node->prev = new_node;
    return;
}

9. 查找指定值所在的位置

（1）如果連結清單為空，則查找失敗

（2）若連結清單非空，則對連結清單從頭開始周遊。使指定值和連結清單的每個節點的資料域進行對比，如果相同，傳回該結點的位址，如果不同，指針後移

（3）當連結清單周遊結束時，還未找到指定值，說明，該值不存在與連結清單中，則查找失敗。注意，連結清單周遊結束時，即又回到頭結點處時。

代碼如下：

//查找指定值所在的位置
DlinkNode* DlinklistFind(DlinkNode* head,DlinklistType to_find)
{
    if(head == NULL)
    {
        //非法輸入
        return NULL;
    }

    if(head->next == head)
    {
        //空連結清單
        return NULL;
    }
    //定義cur為目前指針周遊來周遊連結清單，初始從真正的第一個節點開始
    DlinkNode* cur = head->next;
    while(cur != head)//當未周遊完連結清單時
    {
        if(cur->data == to_find)//當找到指定值時
        {
            return cur;//傳回指定值所在節點的位置
        }
        cur = cur->next;//若沒找到，繼續後移
    }
    return NULL;//周遊完連結清單還沒找到                                                                                                  
}

10 . 删除指定位置處的節點

（1）首先要判斷連結清單是否為空，為空在删除失敗

（2）判斷要删除的位置是不是頭結點所在的位置。因為頭結點代表着整個連結清單，除銷毀連結清單外不能對其進行删除

（3）若不為（1）（2），根據指定位置找到它的前一個和後一個節點

（4）修改前，後節點的相應指針：使前一個節點的next指向後一個節點，後一個節點的prev指向前一個節點

（5）最後，釋放指定位置處的結點。

代碼如下：

//删除指定位置的節點
void DlinklistErase(DlinkNode* head,DlinkNode* pos)
{
    if(head == NULL || pos == NULL)
    {
        //非法輸入
        return;
    }   
    if(head->next == head)
    {
        //空連結清單
        return;
    }   
    
    if(head == pos)
    {
        //不能删除頭節點
        return;
    }   
    //找到指定位置處的下一個節點
    DlinkNode* next_node = pos->next;
    //找到指定位置處的上一個節點
    DlinkNode* prev_node = pos->prev;
    
    //修改相應指針的指向
    next_node->prev = prev_node;
    prev_node->next = next_node;
    //釋放指定位置處的節點                                                                                                            
    DestoryNode(pos);
    return;
}

11. 按值删除節點

（1）如果連結清單為空，則删除失敗

（2）根據上述的find函數先找到該值所在的位置，如果沒找到，則删除失敗

（3）若找到了，則根據該位置上述的Erase函數對其進行删除

代碼如下：

//按值删除
void DlinklistRemove(DlinkNode* head,DlinklistType to_delete_value)
{
    if(head == NULL)
    {
        //非法輸入
        return;
    }
    if(head->next == head)
    {
        //空連結清單
        return;
    }
    
    //找到指定值所在的位置
    DlinkNode* to_delete =  DlinklistFind(head,to_delete_value);
    if(to_delete == NULL)
    {
        //沒找到該節點
        return;
    }
    //根據指定位置删除節點                                                                                                            
    DlinklistErase(head,to_delete);
    return;
}

12. 删除指定值所在的所有節點

與上述類似

（1）連結清單為空，删除失敗

（2）連結清單不為空，先找到指定值所在的位置，然後根據位置删除節點

（3）一直循環過程（2），直到找不到指定值所在的位置，說明已經删除指定值處的所有結點

代碼如下：

//按值删除所有
void DlinklistRemoveAll(DlinkNode* head,DlinklistType to_delete_value)
{
    if(head == NULL)
    {
        //非法輸入
        return;
    }
    if(head->next == head)
    {
        //空連結清單
        return;
    }
    //根據指定值找所在的位置
    DlinkNode* to_delete = DlinklistFind(head,to_delete_value);
    while(to_delete != NULL)//如果一直能找到指定值所在的位置
    {
        DlinklistErase(head,to_delete);//則對其進行删除
        to_delete = DlinklistFind(head,to_delete_value);
    }
    return;//此時，所有指定值所在的節點已全部删除                                                                                     
}

13. 銷毀連結清單

在對連結清單初始化前，連結清單隻用一個頭指針進行表示，是以銷毀連結清單後，即恢複到初始化前的狀态。

（1）首先，周遊連結清單，将連結清單的結點一個個進行釋放

（2）然後，在對頭結點進行釋放

（3）因為頭結點未釋放前，由頭指針指向。而釋放後，頭指針指向的是一個無效的位址，即頭指針變成了野指針。是以頭結點釋放後，要對頭指針置空。此時，要改變頭指針的指向，是以，函數傳參時要傳頭指針的位址即二級指針。

代碼如下：

//銷毀連結清單
void DestoryDlinklist(DlinkNode** phead)
{
    if(phead == NULL)
    {
        //非法輸入
        return;
    }

    //周遊連結清單對各節點進行釋放
    DlinkNode* to_delete = (*phead)->next;
    while(to_delete != *phead)
    {
        DlinkNode* next_node = to_delete->next;
        DestoryNode(to_delete);
        to_delete = next_node;
    }
    //釋放頭節點
    DestoryNode(*phead);
    //頭指針置空                                                                                                                      
    *phead = NULL;

}

14. 統計雙向連結清單的長度

（1）首先判定連結清單是否為空，為空，則傳回0

（2）然後從第一個結點開始周遊，周遊到一個結點，長度加1，直到回到頭結點

代碼如下：

//統計雙向連結清單的長度
int DlinklistSize(DlinkNode*head)
{
    if(head == NULL)
    {   
        //非法輸入
        return -1; 
    }   
    if(head->next == head)//該部分代碼可包含在下述代碼中
    {   
        //空連結清單
        return 0;
    }   

    //從第一個節點開始周遊，周遊一個，長度加1，直到回到頭節點                                                                         
    DlinkNode* cur = head->next;
    int size = 0;
    while(cur != head)
    {   
        size++;
        cur = cur->next;
    }   
    return size;
}

雙向，帶頭節點，帶環連結清單的基本操作

繼續閱讀

不用iconv函數實作UTF-8編碼轉換GB2312的PHP函數

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

浮點數計算精度控制

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

C++ 第十五周報告1--《冒泡法排序》

[轉]九大排序算法——C語言實作及詳解

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

QR碼編碼原理三（日本漢字和中文編碼）

Linux裝置模型（中）之上層容器