一口氣搞懂「鏈表」，就靠這20+張圖了

說(shuō)真的，任何說(shuō)起嵌入式軟件怎么入門(mén)啊？需要學(xué)些什么東西啊，我差不多一致的回答都是：軟件方面C語(yǔ)言和數(shù)據(jù)結(jié)構(gòu)加上一些簡(jiǎn)單常用的算法，這些需要學(xué)好。

借著自己的回顧學(xué)習(xí)，我也寫(xiě)一些基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)知識(shí)，多畫(huà)圖，少BB，與大家一起學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)

順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)

數(shù)組—順序存儲(chǔ)

數(shù)組作為一個(gè)順序儲(chǔ)存方式的數(shù)據(jù)結(jié)構(gòu)，可是有大作為的，它的靈活使用為我們的程序設(shè)計(jì)帶來(lái)了大量的便利；

但是，但是，數(shù)組最大的缺點(diǎn)就是我們的插入和刪除時(shí)需要移動(dòng)大量的元素，所以呢，大量的消耗時(shí)間，以及冗余度難以接受了。

以C語(yǔ)言數(shù)組插入一個(gè)元素為例，當(dāng)我們需要在一個(gè)數(shù)組{1,2,3,4}的第1個(gè)元素后的位置插入一個(gè)’A’時(shí)，我們需要做的有：

1. 將第1個(gè)元素后的整體元素后移，形成新的數(shù)組{1,2,2,3,4}

2. 再將第2個(gè)元素位置的元素替換為我們所需要的元素’A’

3. 最終形成我們的預(yù)期，這需要很多的操作喔。

上圖可以看出，使用數(shù)組都有這兩大缺點(diǎn)：

1. 插入刪除操作所需要移動(dòng)的元素很多，浪費(fèi)算力。

2. 必須為數(shù)組開(kāi)足夠的空間，否則有溢出風(fēng)險(xiǎn)。

鏈表—鏈?zhǔn)酱鎯?chǔ)

由于數(shù)組的這些缺點(diǎn)，自然而然的就產(chǎn)生鏈表的思想了。

鏈表通過(guò)不連續(xù)的儲(chǔ)存方式，自適應(yīng)內(nèi)存大小，以及指針的靈活使用，巧妙的簡(jiǎn)化了上述的內(nèi)容。

鏈表的基本思維是，利用結(jié)構(gòu)體的設(shè)置，額外開(kāi)辟出一份內(nèi)存空間去作指針，它總是指向下一個(gè)結(jié)點(diǎn)，一個(gè)個(gè)結(jié)點(diǎn)通過(guò)NEXT指針相互串聯(lián)，就形成了鏈表。

其中DATA為自定義的數(shù)據(jù)類(lèi)型，NEXT為指向下一個(gè)鏈表結(jié)點(diǎn)的指針，通過(guò)訪(fǎng)問(wèn)NEXT，可以引導(dǎo)我們?nèi)ピL(fǎng)問(wèn)鏈表的下一個(gè)結(jié)點(diǎn)。

對(duì)于一連串的結(jié)點(diǎn)而言，就形成了鏈表如下圖：

上文所說(shuō)的插入刪除操作只需要修改指針?biāo)赶虻膮^(qū)域就可以了，不需要進(jìn)行大量的數(shù)據(jù)移動(dòng)操作。如下圖：

相比起數(shù)組，鏈表解決了數(shù)組不方便移動(dòng)，插入，刪除元素的弊端，但相應(yīng)的，鏈表付出了更加大的內(nèi)存犧牲換來(lái)的這些功能的實(shí)現(xiàn)。

鏈表概述

包含單鏈表，雙鏈表，循環(huán)單鏈表，實(shí)際應(yīng)用中的功能不同，但實(shí)現(xiàn)方式都差不多。

• 單鏈表就像是美國(guó)男籃，一代一代往下傳；

• 雙鏈表像是中國(guó)男足，你傳球給我，我傳球給你，最終傳給了守門(mén)員；

• 循環(huán)鏈表就像是中國(guó)男籃，火炬從姚明傳給王治郅，王治郅傳給易建聯(lián)，現(xiàn)在易建聯(lián)傷了，又傳給了姚明

單鏈表

單鏈表概念和簡(jiǎn)單的設(shè)計(jì)

單鏈表是一種鏈?zhǔn)酱嫒〉臄?shù)據(jù)結(jié)構(gòu)，鏈表中的數(shù)據(jù)是以結(jié)點(diǎn)來(lái)表示的，每個(gè)結(jié)點(diǎn)由元素和指針構(gòu)成。

元素表示數(shù)據(jù)元素的映象，就是存儲(chǔ)數(shù)據(jù)的存儲(chǔ)單元；指針指示出后繼元素存儲(chǔ)位置，就是連接每個(gè)結(jié)點(diǎn)的地址數(shù)據(jù)。

以結(jié)點(diǎn)的序列表示的線(xiàn)性表稱(chēng)作線(xiàn)性鏈表，也就是單鏈表，單鏈表是鏈?zhǔn)酱嫒〉慕Y(jié)構(gòu)。

對(duì)于鏈表的每一個(gè)結(jié)點(diǎn)，我們使用結(jié)構(gòu)體進(jìn)行設(shè)計(jì)，其主要內(nèi)容有：

其中，DATA數(shù)據(jù)元素，可以為你想要儲(chǔ)存的任何數(shù)據(jù)格式，可以是數(shù)組，可以是int，甚至可以是結(jié)構(gòu)體（這就是傳說(shuō)中的結(jié)構(gòu)體套結(jié)構(gòu)體）

NEXT為一個(gè)指針，其代表了一個(gè)可以指向的區(qū)域，通常是用來(lái)指向下一個(gè)結(jié)點(diǎn)，鏈表的尾部NEXT指向NULL（空），因?yàn)槲膊繘](méi)有任何可以指向的空間了

故，對(duì)于一個(gè)單鏈表的結(jié)點(diǎn)定義，可以代碼描述成：

//定義結(jié)點(diǎn)類(lèi)型
typedef struct Node {
    int data;       //數(shù)據(jù)類(lèi)型，你可以把int型的data換成任意數(shù)據(jù)類(lèi)型，包括結(jié)構(gòu)體struct等復(fù)合類(lèi)型
    struct Node *next;          //單鏈表的指針域
} Node,*LinkedList;  
//Node表示結(jié)點(diǎn)的類(lèi)型，LinkedList表示指向Node結(jié)點(diǎn)類(lèi)型的指針類(lèi)型

鏈表的初始化

初始化主要完成以下工作：創(chuàng)建一個(gè)單鏈表的前置節(jié)點(diǎn)并向后逐步添加節(jié)點(diǎn)，一般指的是申請(qǐng)結(jié)點(diǎn)的空間，同時(shí)對(duì)一個(gè)結(jié)點(diǎn)賦空值(NULL)，其代碼可以表示為：

LinkedList listinit(){
    Node *L;
    L=(Node*)malloc(sizeof(Node));      //開(kāi)辟空間 
    if(L==NULL){                     //判斷是否開(kāi)辟空間失敗，這一步很有必要
        printf("申請(qǐng)空間失敗");
        //exit(0);                  //開(kāi)辟空間失敗可以考慮直接結(jié)束程序
    }
    L->next=NULL;       //指針指向空
}

注意：一定要判斷是否開(kāi)辟空間失敗，否則生產(chǎn)中由于未知的情況造成空間開(kāi)辟失敗，仍然在繼續(xù)執(zhí)行代碼，后果將不堪設(shè)想啦，因此養(yǎng)成這樣的判斷是很有必要的。

頭插入法創(chuàng)建單鏈表

利用指針指向下一個(gè)結(jié)點(diǎn)元素的方式進(jìn)行逐個(gè)創(chuàng)建，使用頭插入法最終得到的結(jié)果是逆序的。如圖所示：

從一個(gè)空表開(kāi)始，生成新結(jié)點(diǎn)，并將讀取到的數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭，即頭結(jié)點(diǎn)之后。

//頭插法建立單鏈表
LinkedList LinkedListCreatH() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申請(qǐng)頭結(jié)點(diǎn)空間
    L->next = NULL;                      //初始化一個(gè)空鏈表
  
    int x;                         //x為鏈表數(shù)據(jù)域中的數(shù)據(jù)
    while(scanf("%d",&x) != EOF) {
        Node *p;
        p = (Node *)malloc(sizeof(Node));   //申請(qǐng)新的結(jié)點(diǎn)
        p->data = x;                     //結(jié)點(diǎn)數(shù)據(jù)域賦值
        p->next = L->next;     //將結(jié)點(diǎn)插入到表頭L-->|2|-->|1|-->NULL
        L->next = p;
    }
    return L;
}

尾插入法創(chuàng)建單鏈表

如圖所示為尾插入法的創(chuàng)建過(guò)程。

頭插法生成的鏈表中，結(jié)點(diǎn)的次序和輸入數(shù)據(jù)的順序不一致。若希望兩者次序一致，則需要尾插法。

該方法是將新結(jié)點(diǎn)逐個(gè)插入到當(dāng)前鏈表的表尾上，為此必須增加一個(gè)尾指針r, 使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)，代碼如下：

//尾插法建立單鏈表
  
LinkedList LinkedListCreatT() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申請(qǐng)頭結(jié)點(diǎn)空間
    L->next = NULL;                  //初始化一個(gè)空鏈表
    Node *r;
    r = L;                          //r始終指向終端結(jié)點(diǎn)，開(kāi)始時(shí)指向頭結(jié)點(diǎn)
    int x;                         //x為鏈表數(shù)據(jù)域中的數(shù)據(jù)
    while(scanf("%d",&x) != EOF) {
        Node *p;
        p = (Node *)malloc(sizeof(Node));   //申請(qǐng)新的結(jié)點(diǎn)
        p->data = x;                     //結(jié)點(diǎn)數(shù)據(jù)域賦值
        r->next = p;            //將結(jié)點(diǎn)插入到表頭L-->|1|-->|2|-->NULL
        r = p;
    }
    r->next = NULL;
    return L;
}

遍歷單鏈表如打印、修改

從鏈表的頭開(kāi)始，逐步向后進(jìn)行每一個(gè)元素的訪(fǎng)問(wèn)，稱(chēng)為遍歷。

對(duì)于遍歷操作，我們可以衍生出很多常用的數(shù)據(jù)操作，比如查詢(xún)?cè)兀薷脑兀@取元素個(gè)數(shù)，打印整個(gè)鏈表數(shù)據(jù)等等。

進(jìn)行遍歷的思路極其簡(jiǎn)單，只需要建立一個(gè)指向鏈表L的結(jié)點(diǎn)，然后沿著鏈表L逐個(gè)向后搜索即可，代碼如下：

//便利輸出單鏈表
void printList(LinkedList L){
    Node *p=L->next;
    int i=0;
    while(p){
        printf("第%d個(gè)元素的值為:%d\n",++i,p->data);
        p=p->next;
    }
}

對(duì)于元素修改操作，以下是代碼實(shí)現(xiàn)：

//鏈表內(nèi)容的修改，在鏈表中修改值為x的元素變?yōu)闉閗。
LinkedList LinkedListReplace(LinkedList L,int x,int k) {
    Node *p=L->next;
    int i=0;
    while(p){
        if(p->data==x){
            p->data=k;
        }
        p=p->next;
    }
    return L;
}

簡(jiǎn)單的遍歷設(shè)計(jì)的函數(shù)只需要void無(wú)參即可，而當(dāng)涉及到元素操作時(shí)，可以設(shè)計(jì)一個(gè)LinkedList類(lèi)型的函數(shù)，使其返回一個(gè)操作后的新鏈表。

插入操作

鏈表的插入操作主要分為查找到第i個(gè)位置，將該位置的next指針修改為指向我們新插入的結(jié)點(diǎn)，而新插入的結(jié)點(diǎn)next指針指向我們i+1個(gè)位置的結(jié)點(diǎn)。

其操作方式可以設(shè)置一個(gè)前驅(qū)結(jié)點(diǎn)，利用循環(huán)找到第i個(gè)位置，再進(jìn)行插入。

如圖，在DATA1和DATA2數(shù)據(jù)結(jié)點(diǎn)之中插入一個(gè)NEW_DATA數(shù)據(jù)結(jié)點(diǎn)：

從原來(lái)的鏈表狀態(tài)

到新的鏈表狀態(tài)：

代碼實(shí)現(xiàn)如下：

//單鏈表的插入，在鏈表的第i個(gè)位置插入x的元素
  
LinkedList LinkedListInsert(LinkedList L,int i,int x) {
    Node *pre;                      //pre為前驅(qū)結(jié)點(diǎn)
    pre = L;
    int tempi = 0;
    for (tempi = 1; tempi < i; tempi++) {
        pre = pre->next;                 //查找第i個(gè)位置的前驅(qū)結(jié)點(diǎn)
    }
    Node *p;                                //插入的結(jié)點(diǎn)為p
    p = (Node *)malloc(sizeof(Node));
    p->data = x;
    p->next = pre->next;
    pre->next = p;
  
    return L;
}

刪除操作

刪除元素要建立一個(gè)前驅(qū)結(jié)點(diǎn)和一個(gè)當(dāng)前結(jié)點(diǎn)，當(dāng)找到了我們需要?jiǎng)h除的數(shù)據(jù)時(shí)，直接使用前驅(qū)結(jié)點(diǎn)跳過(guò)要?jiǎng)h除的結(jié)點(diǎn)指向要?jiǎng)h除結(jié)點(diǎn)的后一個(gè)結(jié)點(diǎn)，再將原有的結(jié)點(diǎn)通過(guò)free函數(shù)釋放掉。如圖所示：

代碼如下：

//單鏈表的刪除，在鏈表中刪除值為x的元素
  
LinkedList LinkedListDelete(LinkedList L,int x) {
    Node *p,*pre;                   //pre為前驅(qū)結(jié)點(diǎn)，p為查找的結(jié)點(diǎn)。
    p = L->next;
     
    while(p->data != x) {              //查找值為x的元素
        pre = p;
        p = p->next;
    }
    pre->next = p->next;          //刪除操作，將其前驅(qū)next指向其后繼。
    free(p);
     
    return L;
}

雙向鏈表

雙向鏈表的簡(jiǎn)介以及概念

單鏈表是指結(jié)點(diǎn)中只有一個(gè)指向其后繼的指針，具有單向性，但是有時(shí)需要搜索大量數(shù)據(jù)的時(shí)候，就需要多次進(jìn)行從頭開(kāi)始的遍歷，這樣的搜索就不是很高效了。

在單鏈表的基礎(chǔ)上，對(duì)于每一個(gè)結(jié)點(diǎn)設(shè)計(jì)一個(gè)前驅(qū)結(jié)點(diǎn)，前驅(qū)結(jié)點(diǎn)與前一個(gè)結(jié)點(diǎn)相互連接，構(gòu)成一個(gè)鏈表，就產(chǎn)生了雙向鏈表的概念了。

雙向鏈表可以簡(jiǎn)稱(chēng)為雙鏈表，是鏈表的一種，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開(kāi)始，都可以很方便地訪(fǎng)問(wèn)它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。

一個(gè)完整的雙向鏈表應(yīng)該是頭結(jié)點(diǎn)的pre指針指為空，尾結(jié)點(diǎn)的next指針指向空，其余結(jié)點(diǎn)前后相鏈。

雙向鏈表的結(jié)點(diǎn)設(shè)計(jì)

對(duì)于每一個(gè)結(jié)點(diǎn)而言，有：

其中，DATA表示數(shù)據(jù)，其可以是簡(jiǎn)單的類(lèi)型也可以是復(fù)雜的結(jié)構(gòu)體；

pre代表的是前驅(qū)指針，它總是指向當(dāng)前結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，如果當(dāng)前結(jié)點(diǎn)是頭結(jié)點(diǎn)，則pre指針為空；

next代表的是后繼指針，它總是指向當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，如果當(dāng)前結(jié)點(diǎn)是尾結(jié)點(diǎn)，則next指針為空

其代碼設(shè)計(jì)如下：

typedef struct line{
    int data;           //data
    struct line *pre;   //pre node
    struct line *next;  //next node
}line,*a;
//分別表示該結(jié)點(diǎn)的前驅(qū)(pre)，后繼(next)，以及當(dāng)前數(shù)據(jù)(data)

3. 雙鏈表的創(chuàng)建

創(chuàng)建雙向鏈表需要先創(chuàng)建頭結(jié)點(diǎn)，然后逐步的進(jìn)行添加雙向鏈表的頭結(jié)點(diǎn)是有數(shù)據(jù)元素的，也就是頭結(jié)點(diǎn)的data域中是存有數(shù)據(jù)的，這與一般的單鏈表是不同的。

對(duì)于逐步添加數(shù)據(jù)，先開(kāi)辟一段新的內(nèi)存空間作為新的結(jié)點(diǎn)，為這個(gè)結(jié)點(diǎn)進(jìn)行的data進(jìn)行賦值，然后將已成鏈表的上一個(gè)結(jié)點(diǎn)的next指針指向自身，自身的pre指針指向上一個(gè)結(jié)點(diǎn)。

其代碼可以設(shè)計(jì)為：

//創(chuàng)建雙鏈表
line* initLine(line * head){
    int number,pos=1,input_data;
    //三個(gè)變量分別代表結(jié)點(diǎn)數(shù)量，當(dāng)前位置，輸入的數(shù)據(jù)
    printf("請(qǐng)輸入創(chuàng)建結(jié)點(diǎn)的大小\n");
    scanf("%d",&number);
    if(number<1){return NULL;} //輸入非法直接結(jié)束
    //////頭結(jié)點(diǎn)創(chuàng)建///////
    head=(line*)malloc(sizeof(line));
    head->pre=NULL;
    head->next=NULL;
    printf("輸入第%d個(gè)數(shù)據(jù)\n",pos++);
    scanf("%d",&input_data);
    head->data=input_data;
  
    line * list=head;
    while (pos<=number) {
        line * body=(line*)malloc(sizeof(line));
        body->pre=NULL;
        body->next=NULL;
        printf("輸入第%d個(gè)數(shù)據(jù)\n",pos++);
        scanf("%d",&input_data);
        body->data=input_data;
        
        list->next=body;
        body->pre=list;
        list=list->next;
    }
    return head;
}

雙向鏈表創(chuàng)建的過(guò)程可以分為：創(chuàng)建頭結(jié)點(diǎn)->創(chuàng)建一個(gè)新的結(jié)點(diǎn)->將頭結(jié)點(diǎn)和新結(jié)點(diǎn)相互鏈接->再度創(chuàng)建新結(jié)點(diǎn)，這樣會(huì)有助于理解。

雙向鏈表的插入操作

如圖所示：

對(duì)于每一次的雙向鏈表的插入操作，首先需要?jiǎng)?chuàng)建一個(gè)獨(dú)立的結(jié)點(diǎn)，并通過(guò)malloc操作開(kāi)辟相應(yīng)的空間；

其次我們選中這個(gè)新創(chuàng)建的獨(dú)立節(jié)點(diǎn)，將其的pre指針指向所需插入位置的前一個(gè)結(jié)點(diǎn)；

同時(shí)，其所需插入的前一個(gè)結(jié)點(diǎn)的next指針修改指向?yàn)樵撔碌慕Y(jié)點(diǎn)，該新的結(jié)點(diǎn)的next指針將會(huì)指向一個(gè)原本的下一個(gè)結(jié)點(diǎn)，而修改下一個(gè)結(jié)點(diǎn)的pre指針為指向新結(jié)點(diǎn)自身，這樣的一個(gè)操作我們稱(chēng)之為雙向鏈表的插入操作。

其代碼可以表示為：

//插入數(shù)據(jù)
line * insertLine(line * head,int data,int add){
    //三個(gè)參數(shù)分別為：進(jìn)行此操作的雙鏈表，插入的數(shù)據(jù)，插入的位置
    //新建數(shù)據(jù)域?yàn)閐ata的結(jié)點(diǎn)
    line * temp=(line*)malloc(sizeof(line));
    temp->data=data;
    temp->pre=NULL;
    temp->next=NULL;
    //插入到鏈表頭，要特殊考慮
    if (add==1) {
        temp->next=head;
        head->pre=temp;
        head=temp;
    }else{
        line * body=head;
        //找到要插入位置的前一個(gè)結(jié)點(diǎn)
        for (int i=1; i<add-1; i++) {
            body=body->next;
        }
        //判斷條件為真，說(shuō)明插入位置為鏈表尾
        if (body->next==NULL) {
            body->next=temp;
            temp->pre=body;
        }else{
            body->next->pre=temp;
            temp->next=body->next;
            body->next=temp;
            temp->pre=body;
        }
    }
    return head;
}

雙向鏈表的刪除操作

如圖：

刪除操作的過(guò)程是：選擇需要?jiǎng)h除的結(jié)點(diǎn)->選中這個(gè)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)->將前一個(gè)結(jié)點(diǎn)的next指針指向自己的下一個(gè)結(jié)點(diǎn)->選中該節(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)->將下一個(gè)結(jié)點(diǎn)的pre指針修改指向?yàn)樽约旱纳弦粋€(gè)結(jié)點(diǎn)。

在進(jìn)行遍歷的時(shí)候直接將這一個(gè)結(jié)點(diǎn)給跳過(guò)了，之后，我們釋放刪除結(jié)點(diǎn)，歸還空間給內(nèi)存，這樣的操作我們稱(chēng)之為雙鏈表的刪除操作。

其代碼可以表示為：

//刪除元素
line * deleteLine(line * head,int data){
    //輸入的參數(shù)分別為進(jìn)行此操作的雙鏈表，需要?jiǎng)h除的數(shù)據(jù)
    line * list=head;
    //遍歷鏈表
    while (list) {
        //判斷是否與此元素相等
        //刪除該點(diǎn)方法為將該結(jié)點(diǎn)前一結(jié)點(diǎn)的next指向該節(jié)點(diǎn)后一結(jié)點(diǎn)
        //同時(shí)將該結(jié)點(diǎn)的后一結(jié)點(diǎn)的pre指向該節(jié)點(diǎn)的前一結(jié)點(diǎn)
        if (list->data==data) {
            list->pre->next=list->next;
            list->next->pre=list->pre;
            free(list);
            printf("--刪除成功--\n");
            return head;
        }
        list=list->next;
    }
    printf("Error:沒(méi)有找到該元素，沒(méi)有產(chǎn)生刪除\n");
    return head;
}

雙向鏈表的遍歷

雙向鏈表的遍歷利用next指針逐步向后進(jìn)行索引即可。

注意，在判斷這里，我們既可以用while(list)的操作直接判斷是否鏈表為空，也可以使用while(list->next)的操作判斷該鏈表是否為空，其下一節(jié)點(diǎn)為空和本結(jié)點(diǎn)是否為空的判斷條件是一樣的效果。

其簡(jiǎn)單的代碼可以表示為：

//遍歷雙鏈表,同時(shí)打印元素?cái)?shù)據(jù)
void printLine(line *head){
    line *list = head;
    int pos=1;
    while(list){
        printf("第%d個(gè)數(shù)據(jù)是:%d\n",pos++,list->data);
        list=list->next;
    }
}

循環(huán)鏈表

循環(huán)鏈表概念

對(duì)于單鏈表以及雙向鏈表，就像一個(gè)小巷，無(wú)論怎么走最終都能從一端走到另一端，顧名思義，循環(huán)鏈表則像一個(gè)有傳送門(mén)的小巷，當(dāng)你以為你走到結(jié)尾的時(shí)候，其實(shí)這就是開(kāi)頭。

循環(huán)鏈表和非循環(huán)鏈表其實(shí)創(chuàng)建的過(guò)程唯一不同的是，非循環(huán)鏈表的尾結(jié)點(diǎn)指向空（NULL），而循環(huán)鏈表的尾指針指向的是鏈表的開(kāi)頭。

通過(guò)將單鏈表的尾結(jié)點(diǎn)指向頭結(jié)點(diǎn)的鏈表稱(chēng)之為循環(huán)單鏈表（Circular linkedlist）

一個(gè)完整的循環(huán)單鏈表如圖：

循環(huán)鏈表結(jié)點(diǎn)設(shè)計(jì)（以單循環(huán)鏈表為例）

對(duì)于循環(huán)單鏈表的結(jié)點(diǎn)，可以完全參照于單鏈表的結(jié)點(diǎn)設(shè)計(jì)，如圖：

data表示數(shù)據(jù)；

next表示指針，它總是指向自身的下一個(gè)結(jié)點(diǎn)，對(duì)于只有一個(gè)結(jié)點(diǎn)的存在，這個(gè)next指針則永遠(yuǎn)指向自身，對(duì)于一個(gè)鏈表的尾部結(jié)點(diǎn)，next永遠(yuǎn)指向開(kāi)頭。

其代碼如下：

typedef struct list{
    int data;
    struct list *next;
}list;
//data為存儲(chǔ)的數(shù)據(jù)，next指針為指向下一個(gè)結(jié)點(diǎn)

循環(huán)單鏈表初始化

先創(chuàng)建一個(gè)頭結(jié)點(diǎn)并且給其開(kāi)辟內(nèi)存空間，在開(kāi)辟內(nèi)存空間成功之后，將頭結(jié)點(diǎn)的next指向head自身，創(chuàng)建一個(gè)init函數(shù)來(lái)完成；

為了重復(fù)創(chuàng)建和插入，我們可以在init函數(shù)重新創(chuàng)建的結(jié)點(diǎn)next指向空，而在主函數(shù)調(diào)用創(chuàng)建之后，將head頭結(jié)點(diǎn)的next指針指向自身。

這樣的操作方式可以方便過(guò)后的創(chuàng)建單鏈表，直接利用多次調(diào)用的插入函數(shù)即可完成整體創(chuàng)建。

其代碼如下：

//初始結(jié)點(diǎn)
list *initlist(){
    list *head=(list*)malloc(sizeof(list));
    if(head==NULL){
        printf("創(chuàng)建失敗，退出程序");
        exit(0);
    }else{
        head->next=NULL;
        return head;
    }
}

在主函數(shù)重調(diào)用可以是這樣

    //////////初始化頭結(jié)點(diǎn)//////////////
    list *head=initlist();
    head->next=head;

循環(huán)鏈表的創(chuàng)建操作

如圖所示：

通過(guò)逐步的插入操作，創(chuàng)建一個(gè)新的節(jié)點(diǎn)，將原有鏈表尾結(jié)點(diǎn)的next指針修改指向到新的結(jié)點(diǎn)，新的結(jié)點(diǎn)的next指針再重新指向頭部結(jié)點(diǎn)，然后逐步進(jìn)行這樣的插入操作，最終完成整個(gè)單項(xiàng)循環(huán)鏈表的創(chuàng)建。

其代碼如下：

//創(chuàng)建——插入數(shù)據(jù)
int insert_list(list *head){
    int data;   //插入的數(shù)據(jù)類(lèi)型
    printf("請(qǐng)輸入要插入的元素：");
    scanf("%d",&data);
  
    list *node=initlist();
    node->data=data;
    //初始化一個(gè)新的結(jié)點(diǎn)，準(zhǔn)備進(jìn)行鏈接
  
    if(head!=NULL){
        list *p=head;
        //找到最后一個(gè)數(shù)據(jù)
        while(p->next!=head){
            p=p->next;
        }
        p->next=node;
        node->next=head;
        return 1;
    }else{
        printf("頭結(jié)點(diǎn)已無(wú)元素\n");
        return 0;
    }
  
}

循環(huán)單鏈表的插入操作

如圖，對(duì)于插入數(shù)據(jù)的操作，可以創(chuàng)建一個(gè)獨(dú)立的結(jié)點(diǎn)，通過(guò)將需要插入的結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)的next指針指向該節(jié)點(diǎn)，再由需要插入的結(jié)點(diǎn)的next指針指向下一個(gè)結(jié)點(diǎn)的方式完成插入操作。

其代碼如下：

//插入元素
list *insert_list(list *head,int pos,int data){
    //三個(gè)參數(shù)分別是鏈表，位置，參數(shù)
    list *node=initlist();  //新建結(jié)點(diǎn)
    list *p=head;       //p表示新的鏈表
    list *t;
    t=p;
    node->data=data;
    if(head!=NULL){
        for(int i=1;i<pos;i++){
            t=t->next;  //走到需要插入的位置處
        }
        node->next=t->next;
        t->next=node;
        return p;
    }
    return p;
}

循環(huán)單鏈表的刪除操作

如下圖所示，循環(huán)單鏈表的刪除操作是先找到需要?jiǎng)h除的結(jié)點(diǎn)，將其前一個(gè)結(jié)點(diǎn)的next指針直接指向刪除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)即可。

需要注意的是尾結(jié)點(diǎn)，因?yàn)閯h除尾節(jié)點(diǎn)后，尾節(jié)點(diǎn)前一個(gè)結(jié)點(diǎn)就成了新的尾節(jié)點(diǎn)，這個(gè)新的尾節(jié)點(diǎn)需要指向的是頭結(jié)點(diǎn)而不是空。

其代碼如下：

//刪除元素
int delete_list(list *head) {
    if(head == NULL) {
        printf("鏈表為空！\n");
        return 0;
    }
    //建立臨時(shí)結(jié)點(diǎn)存儲(chǔ)頭結(jié)點(diǎn)信息（目的為了找到退出點(diǎn)）
    //如果不這么建立的化需要使用一個(gè)數(shù)據(jù)進(jìn)行計(jì)數(shù)標(biāo)記，計(jì)數(shù)達(dá)到鏈表長(zhǎng)度時(shí)自動(dòng)退出
    //循環(huán)鏈表當(dāng)找到最后一個(gè)元素的時(shí)候會(huì)自動(dòng)指向頭元素，這是我們不想讓他發(fā)生的
    list *temp = head;          
    list *ptr = head->next;
  
    int del;
    printf("請(qǐng)輸入你要?jiǎng)h除的元素：");
    scanf("%d",&del);
  
    while(ptr != head) {
        if(ptr->data == del) {
            if(ptr->next == head) { 
                temp->next = head;
                free(ptr);
                return 1;
            }
            temp->next = ptr->next;    //核心刪除操作代碼
            free(ptr);
            //printf("元素刪除成功！\n");
            return 1;
        }
        temp = temp->next;
        ptr = ptr->next;
    }
    printf("沒(méi)有找到要?jiǎng)h除的元素\n");
    return 0;
}

循環(huán)單鏈表的遍歷

與普通的單鏈表和雙向鏈表的遍歷不同，循環(huán)鏈表需要進(jìn)行結(jié)點(diǎn)的特殊判斷。

先找到尾節(jié)點(diǎn)的位置，由于尾節(jié)點(diǎn)的next指針是指向頭結(jié)點(diǎn)的，所以不能使用鏈表本身是否為空（NULL）的方法進(jìn)行簡(jiǎn)單的循環(huán)判斷，我們需要通過(guò)判斷結(jié)點(diǎn)的next指針是否等于頭結(jié)點(diǎn)的方式進(jìn)行是否完成循環(huán)的判斷。

此外還有一種計(jì)數(shù)的方法，即建立一個(gè)計(jì)數(shù)器count=0，每一次next指針指向下一個(gè)結(jié)點(diǎn)時(shí)計(jì)數(shù)器+1，當(dāng)count數(shù)字與鏈表的節(jié)點(diǎn)數(shù)相同的時(shí)候即完成循環(huán)；

但是這樣做會(huì)有一個(gè)問(wèn)題，就是獲取到鏈表的節(jié)點(diǎn)數(shù)同時(shí)，也需要完成一次遍歷才可以達(dá)成目標(biāo)。

其代碼如下：

//遍歷元素
int display(list *head) {
    if(head != NULL) {
        list *p  = head;
        //遍歷頭節(jié)點(diǎn)到，最后一個(gè)數(shù)據(jù)
        while(p->next != head ) {
            printf("%d   ",p->next->data);
            p = p->next;
        }
        printf("\n");   //換行
        //把最后一個(gè)節(jié)點(diǎn)賦新的節(jié)點(diǎn)過(guò)去
        return 1;
    } else {
        printf("頭結(jié)點(diǎn)為空!\n");
        return 0;
    }
}

進(jìn)階概念——雙向循環(huán)鏈表

循環(huán)單鏈表也有一個(gè)孿生兄弟——雙向循環(huán)鏈表，其設(shè)計(jì)思路與單鏈表和雙向鏈表的設(shè)計(jì)思路一樣，就是在原有的雙向鏈表的基礎(chǔ)上，將尾部結(jié)點(diǎn)和頭部結(jié)點(diǎn)進(jìn)行互相連接。交給大家了。

關(guān)于鏈表的總結(jié)

在順序表中做插入刪除操作時(shí)，平均移動(dòng)大約表中一半的元素，因此對(duì)n較大的順序表效率低。并且需要預(yù)先分配足夠大的存儲(chǔ)空間，而鏈表恰恰是其中運(yùn)用的精華。

基于存儲(chǔ)，運(yùn)算，環(huán)境這幾方面考慮，可以讓我們更好的在項(xiàng)目中使用鏈表。

今天鏈表基礎(chǔ)就講到這里，下一期，我們?cè)僖?jiàn)！