??鏈表和線性表相對(duì)，指的是在物理內(nèi)存上并非相連線性存儲(chǔ)的一種數(shù)據(jù)結(jié)構(gòu)硫痰。鏈表中的每個(gè)元素都是分散存儲(chǔ)的衩婚。因?yàn)榉稚⒋鎯?chǔ)，為了能夠體現(xiàn)出數(shù)據(jù)元素之間的邏輯關(guān)系效斑，每個(gè)數(shù)據(jù)元素在存儲(chǔ)的同時(shí)非春，要配備一個(gè)指針，用于指向它的直接后繼元素，即每一個(gè)數(shù)據(jù)元素都指向下一個(gè)數(shù)據(jù)元素（最后一個(gè)指向NULL(空))奇昙。

鏈表中數(shù)據(jù)元素的構(gòu)成

每個(gè)元素本身由兩部分組成：

• 本身的信息护侮，稱為“數(shù)據(jù)域”；
• 指向直接后繼的指針储耐，稱為“指針域”羊初。

節(jié)點(diǎn)的構(gòu)成

這兩部分信息組成數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)，稱之為“結(jié)點(diǎn)”弧岳。n個(gè)結(jié)點(diǎn)通過指針域相互鏈接凳忙，組成一個(gè)鏈表业踏。

含有n個(gè)節(jié)點(diǎn)的鏈表

上圖中禽炬，由于每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，生成的鏈表又被稱為 線性鏈表 或 單鏈表勤家。
鏈表中存放的不是基本數(shù)據(jù)類型腹尖，需要用結(jié)構(gòu)體自定義實(shí)現(xiàn)：

typedef struct Link{
    char elem;//代表數(shù)據(jù)域
    struct Link * next;//代表指針域，指向直接后繼元素
}link;

頭結(jié)點(diǎn)伐脖、頭指針和首元結(jié)點(diǎn)

• 頭結(jié)點(diǎn)： 有時(shí)热幔，在鏈表的第一個(gè)結(jié)點(diǎn)之前會(huì)額外增設(shè)一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)的數(shù)據(jù)域一般不存放數(shù)據(jù)（有些情況下也可以存放鏈表的長(zhǎng)度等信息）讼庇，此結(jié)點(diǎn)被稱為頭結(jié)點(diǎn)绎巨。

若頭結(jié)點(diǎn)的指針域?yàn)榭眨∟ULL），表明鏈表是空表蠕啄。頭結(jié)點(diǎn)對(duì)于鏈表來(lái)說场勤，不是必須的，在處理某些問題時(shí)歼跟，給鏈表添加頭結(jié)點(diǎn)會(huì)使問題變得簡(jiǎn)單和媳。

• 首元結(jié)點(diǎn)：鏈表中第一個(gè)元素所在的結(jié)點(diǎn)，它是頭結(jié)點(diǎn)后邊的第一個(gè)結(jié)點(diǎn)哈街。
• 頭指針：永遠(yuǎn)指向鏈表中第一個(gè)結(jié)點(diǎn)的位置（如果鏈表有頭結(jié)點(diǎn)留瞳，頭指針指向頭結(jié)點(diǎn)；否則骚秦，頭指針指向首元結(jié)點(diǎn)）她倘。

頭結(jié)點(diǎn)和頭指針的區(qū)別：頭指針是一個(gè)指針，頭指針指向鏈表的頭結(jié)點(diǎn)或者首元結(jié)點(diǎn)作箍；頭結(jié)點(diǎn)是一個(gè)實(shí)際存在的結(jié)點(diǎn)硬梁，它包含有數(shù)據(jù)域和指針域。兩者在程序中的直接體現(xiàn)就是：頭指針只聲明而沒有分配存儲(chǔ)空間蒙揣，頭結(jié)點(diǎn)進(jìn)行了聲明并分配了一個(gè)結(jié)點(diǎn)的實(shí)際物理內(nèi)存靶溜。

頭結(jié)點(diǎn)、首元結(jié)點(diǎn)和頭指針

注意：?jiǎn)捂湵碇锌梢詻]有頭結(jié)點(diǎn)，但是不能沒有頭指針罩息！

鏈表的創(chuàng)建和遍歷

萬(wàn)事開頭難嗤详，初始化鏈表首先要做的就是創(chuàng)建鏈表的頭結(jié)點(diǎn)或者首元結(jié)點(diǎn)。創(chuàng)建的同時(shí)瓷炮，要保證有一個(gè)指針永遠(yuǎn)指向的是鏈表的表頭葱色，這樣做不至于丟失鏈表。
例如創(chuàng)建一個(gè)鏈表（1娘香，2苍狰，3，4）:

link * initLink(){
    link * p=(link*)malloc(sizeof(link));//創(chuàng)建一個(gè)頭結(jié)點(diǎn)
    link * temp=p;//聲明一個(gè)指針指向頭結(jié)點(diǎn)烘绽，用于遍歷鏈表
    //生成鏈表
    for (int i=1; i<5; i++) {
        link *a=(link*)malloc(sizeof(link));
        a->elem=i;
        a->next=NULL;
        temp->next=a; //這里*temp是一個(gè)指向頭結(jié)點(diǎn)的指針淋昭，所以temp->next指的是頭結(jié)點(diǎn)的next域
        temp=temp->next;
    }
    return p;
}

這里是尾插法建立鏈表，建立鏈表有兩種方法：頭插法和尾插法

頭插法和尾插法的區(qū)別

鏈表中查找某節(jié)點(diǎn)

一般情況下安接，鏈表只能通過頭結(jié)點(diǎn)或者頭指針進(jìn)行訪問翔忽，所以實(shí)現(xiàn)查找某結(jié)點(diǎn)最常用的方法就是對(duì)鏈表中的結(jié)點(diǎn)進(jìn)行逐個(gè)遍歷。

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

int selectElem(link * p,int elem){
    link * t=p;
    int i=1;
    while (t->next) {
        t=t->next;
        if (t->elem==elem) {
            return i;
        }
        i++;
    }
    return -1;
}

更改某節(jié)點(diǎn)的數(shù)據(jù)域

直接遍歷鏈表盏檐，找到節(jié)點(diǎn)歇式，然后直接更改其數(shù)據(jù)域即可。
實(shí)現(xiàn)代碼：

//更新函數(shù)胡野，其中材失，pos表示更改結(jié)點(diǎn)在鏈表中的位置，newElem 為新的數(shù)據(jù)域的值
int *amendElem(link * p, int pos, int newElem){
    link * temp = p;
     temp=temp->next;//在遍歷之前硫豆，temp指向首元結(jié)點(diǎn)
    //遍歷到被刪除結(jié)點(diǎn)
    for (int i=1; i<pos; i++) {
        temp=temp->next;
    }
    temp->elem=newElem;
    return p;
}

向鏈表中插入結(jié)點(diǎn)

鏈表中插入頭結(jié)點(diǎn)龙巨，根據(jù)插入位置的不同，分為3種：

• 插入到鏈表的首部够庙，也就是頭結(jié)點(diǎn)和首元結(jié)點(diǎn)中間恭应；
• 插入到鏈表中間的某個(gè)位置；
• 插入到鏈表最末端耘眨；

向鏈表中插入節(jié)點(diǎn)5

雖然插入位置有區(qū)別昼榛，都使用相同的插入手法。分為兩步剔难，如上圖所示：

1. 將新結(jié)點(diǎn)的next指針指向插入位置后的結(jié)點(diǎn)胆屿；
2. 將插入位置前的結(jié)點(diǎn)的next指針指向插入結(jié)點(diǎn)；

提示：在做插入操作時(shí)偶宫，首先要找到插入位置的上一個(gè)結(jié)點(diǎn)非迹，圖4中，也就是找到結(jié)點(diǎn) 1纯趋，相應(yīng)的結(jié)點(diǎn) 2 可通過結(jié)點(diǎn) 1 的 next 指針表示憎兽，這樣冷离，先進(jìn)行步驟 1，后進(jìn)行步驟 2纯命，實(shí)現(xiàn)過程中不需要添加其他輔助指針西剥。
要先執(zhí)行1再2，不能顛倒亿汞，如果先執(zhí)行2瞭空，則后續(xù)節(jié)點(diǎn)就丟失了無(wú)法找到。

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

link * insertElem(link * p,int elem,int add){
    link * temp=p;//創(chuàng)建臨時(shí)結(jié)點(diǎn)temp
    //首先找到要插入位置的上一個(gè)結(jié)點(diǎn)
    for (int i=1; i<add; i++) {
        if (temp==NULL) {
            printf("插入位置無(wú)效\n");
            return p;
        }
        temp=temp->next;
    }    
    //創(chuàng)建插入結(jié)點(diǎn)c
    link * c=(link*)malloc(sizeof(link));
    c->elem=elem;
    //向鏈表中插入結(jié)點(diǎn)
    c->next=temp->next;
    temp->next=c;
    return  p;
}

注意：首先要保證插入位置的可行性疗我，例如圖 5 中咆畏，原本只有 5 個(gè)結(jié)點(diǎn)，插入位置可選擇的范圍為：1-6吴裤，如果超過6旧找，本身不具備任何意義，程序提示插入位置無(wú)效嚼摩。

從鏈表中刪除節(jié)點(diǎn)

當(dāng)需要從鏈表中刪除某個(gè)結(jié)點(diǎn)時(shí)钦讳，需要進(jìn)行兩步操作：

• 將結(jié)點(diǎn)從鏈表中摘下來(lái);
• 手動(dòng)釋放掉結(jié)點(diǎn)，回收被結(jié)點(diǎn)占用的內(nèi)存空間;

使用malloc函數(shù)申請(qǐng)的空間枕面，一定要注意手動(dòng)free掉。否則在程序運(yùn)行的整個(gè)過程中缚去，申請(qǐng)的內(nèi)存空間不會(huì)自己釋放（只有當(dāng)整個(gè)程序運(yùn)行完了以后潮秘，這塊內(nèi)存才會(huì)被回收），造成內(nèi)存泄漏易结，別把它當(dāng)成是小問題枕荞。

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

link * delElem(link * p,int add){
    link * temp=p;
    //temp指向被刪除結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)
    for (int i=1; i<add; i++) {
        temp=temp->next;
    }
    link * del=temp->next;//單獨(dú)設(shè)置一個(gè)指針指向被刪除結(jié)點(diǎn)，以防丟失
    temp->next=temp->next->next;//刪除某個(gè)結(jié)點(diǎn)的方法就是更改前一個(gè)結(jié)點(diǎn)的指針域
    free(del);//手動(dòng)釋放該結(jié)點(diǎn)搞动，防止內(nèi)存泄漏
    return p;
}