1.鏈表：單鏈表，雙鏈表，循環(huán)鏈表

2.單鏈表

單鏈表是一種鏈式存取的數(shù)據(jù)結(jié)構(gòu)，用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。與順序表不同，鏈表不限制數(shù)據(jù)的物理存儲狀態(tài)，換句話說，使用鏈表存儲的數(shù)據(jù)元素，其物理存儲位置是隨機的。

各數(shù)據(jù)元素的指針

數(shù)據(jù)元素隨機存儲，并通過指針表示數(shù)據(jù)之間邏輯關(guān)系的存儲結(jié)構(gòu)就是鏈式存儲結(jié)構(gòu)。鏈表中的數(shù)據(jù)是以結(jié)點來表示的，每個結(jié)點的構(gòu)成：元素(數(shù)據(jù)元素的映象) + 指針(指示后繼元素存儲位置)，元素就是存儲數(shù)據(jù)的存儲單元，指針就是連接每個結(jié)點的地址數(shù)據(jù)。

結(jié)點結(jié)構(gòu)

單鏈表的建立有頭插法、尾插法兩種方法。

頭插法

單鏈表是用戶不斷申請存儲單元和改變鏈接關(guān)系而得到的一種特殊數(shù)據(jù)結(jié)構(gòu)，將鏈表的左邊稱為鏈頭，右邊稱為鏈尾。頭插法建單鏈表是將鏈表右端看成固定的，鏈表不斷向左延伸而得到的。頭插法最先得到的是尾結(jié)點。由于鏈表的長度是隨機的，故用一個while循環(huán)來控制鏈表中結(jié)點個數(shù)。假設(shè)每個結(jié)點的值都大于O，則循環(huán)條件為輸入的值大于o。申請存儲空間可使用malloc()函數(shù)實現(xiàn)，需設(shè)立一申請單元指針，但malloc()函數(shù)得到的指針并不是指向結(jié)構(gòu)體的指針，需使用強制類型轉(zhuǎn)換，將其轉(zhuǎn)換成結(jié)構(gòu)體型指針。剛開始時，鏈表還沒建立，是一空鏈表，head指針為NULL。
鏈表建立的過程是申請空間、得到數(shù)據(jù)、建立鏈接的循環(huán)處理過程。

尾插法

若將鏈表的左端固定，鏈表不斷向右延伸，這種建立鏈表的方法稱為尾插法。尾插法建立鏈表時，頭指針須設(shè)立一個搜索指針，向鏈表右邊延伸，則整個算法中應(yīng)設(shè)立三個鏈表指針，即頭指針head、搜索指針p2、申請單元指針pl。尾插法最先得到的是頭結(jié)點。

部分內(nèi)容轉(zhuǎn)載自http://c.biancheng.net/view/3338.html

鏈表插入元素

雖然新元素的插入位置不固定，但是鏈表插入元素的思想是固定的，將新元素插入到指定的位置需要進行以下 2 步操作：
(1)將新結(jié)點的 next 指針指向插入位置后的結(jié)點；
(2)將插入位置前結(jié)點的 next 指針指向插入結(jié)點；

三種情況

鏈表刪除元素

從鏈表中刪除指定數(shù)據(jù)元素時，實則就是將存有該數(shù)據(jù)元素的節(jié)點從鏈表中摘除，對不再利用的存儲空間要及時釋放。
因此，從鏈表中刪除數(shù)據(jù)元素需要進行以下 2 步操作：
(1)將結(jié)點從鏈表中摘下來;
(2)手動釋放掉結(jié)點，回收被結(jié)點占用的存儲空間;

鏈表刪除元素

 link * del = temp->next;//單獨設(shè)置一個指針指向被刪除結(jié)點，以防丟失
 temp->next = temp->next->next;//刪除某個結(jié)點的方法就是更改前一個結(jié)點的指針域
free(del);//手動釋放該結(jié)點，防止內(nèi)存泄漏

鏈表查找元素

在鏈表中查找指定數(shù)據(jù)元素，最常用的方法是：從表頭依次遍歷表中節(jié)點，用被查找元素與各節(jié)點數(shù)據(jù)域中存儲的數(shù)據(jù)元素進行比對，直至比對成功或遍歷至鏈表最末端的 NULL（比對失敗的標志）。

鏈表更新元素

更新鏈表中的元素，只需通過遍歷找到存儲此元素的節(jié)點，對節(jié)點中的數(shù)據(jù)域做更改操作即可。

3.雙鏈表

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個結(jié)點開始，都可以很方便地訪問它的前驅(qū)結(jié)點和后繼結(jié)點。一般我們都構(gòu)造雙向循環(huán)鏈表。

雙向鏈表結(jié)構(gòu)示意圖

雙向，指的是各節(jié)點之間的邏輯關(guān)系是雙向的，但通常頭指針只設(shè)置一個，除非實際情況需要。

雙鏈表的結(jié)點

雙向鏈表添加節(jié)點

根據(jù)數(shù)據(jù)添加到雙向鏈表中的位置不同，可細分為以下 3 種情況：

1.添加至表頭

將新數(shù)據(jù)元素添加到表頭，只需要將該元素與表頭元素建立雙層邏輯關(guān)系即可。換句話說，假設(shè)新元素節(jié)點為 temp，表頭節(jié)點為 head，則需要做以下 2 步操作即可：

1. temp->next=head; head->prior=temp;

2. 將 head 移至 temp，重新指向新的表頭。例如，將新元素 7 添加至雙鏈表的表頭

   
   
   添加元素至雙向鏈表的表頭

2.添加至表的中間位置

同單鏈表添加數(shù)據(jù)類似，雙向鏈表中間位置添加數(shù)據(jù)需要經(jīng)過以下 2 個步驟：

1. 新節(jié)點先與其直接后繼節(jié)點建立雙層邏輯關(guān)系；

2. 新節(jié)點的直接前驅(qū)節(jié)點與之建立雙層邏輯關(guān)系；

   
   
   雙向鏈表中間位置添加數(shù)據(jù)元素

3.添加至表尾

與添加到表頭是一個道理，實現(xiàn)過程如下：

1. 找到雙鏈表中最后一個節(jié)點；

2. 讓新節(jié)點與最后一個節(jié)點進行雙層邏輯關(guān)系；

   
   
   雙向鏈表尾部添加數(shù)據(jù)元素

line * insertLine(line * head,int data,int add){
    //新建數(shù)據(jù)域為data的結(jié)點
    line * temp=(line*)malloc(sizeof(line));
    temp->data=data;
    temp->prior=NULL;
    temp->next=NULL;
    //插入到鏈表頭，要特殊考慮
    if (add==1) {
        temp->next=head;
        head->prior=temp;
        head=temp;
    }else{
        line * body=head;
        //找到要插入位置的前一個結(jié)點
        for (int i=1; i<add-1; i++) {
            body=body->next;
        }
        //判斷條件為真，說明插入位置為鏈表尾
        if (body->next==NULL) {
            body->next=temp;
            temp->prior=body;
        }else{
            body->next->prior=temp;
            temp->next=body->next;
            body->next=temp;
            temp->prior=body;
        }
    }
    return head;
}

雙向鏈表刪除節(jié)點

雙鏈表刪除結(jié)點時，只需遍歷鏈表找到要刪除的結(jié)點，然后將該節(jié)點從表中摘除即可。例如，刪除元素 2 的操作過程如圖所示：

雙鏈表刪除元素操作示意圖

//刪除結(jié)點的函數(shù)，data為要刪除結(jié)點的數(shù)據(jù)域的值
line * delLine(line * head,int data){
    line * temp=head;
    //遍歷鏈表
    while (temp) {
        //判斷當前結(jié)點中數(shù)據(jù)域和data是否相等，若相等，摘除該結(jié)點
        if (temp->data==data) {
            temp->prior->next=temp->next;
            temp->next->prior=temp->prior;
            free(temp);
            return head;
        }
        temp=temp->next;
    }
    printf("鏈表中無該數(shù)據(jù)元素");
    return head;
}

雙向鏈表查找節(jié)點

通常，雙向鏈表同單鏈表一樣，都僅有一個頭指針。因此，雙鏈表查找指定元素的實現(xiàn)同單鏈表類似，都是從表頭依次遍歷表中元素。

雙向鏈表更改節(jié)點

更改雙鏈表中指定結(jié)點數(shù)據(jù)域的操作是在查找的基礎(chǔ)上完成的。實現(xiàn)過程是：通過遍歷找到存儲有該數(shù)據(jù)元素的結(jié)點，直接更改其數(shù)據(jù)域即可。

4.循環(huán)鏈表

無論是靜態(tài)鏈表還是動態(tài)鏈表，有時在解決具體問題時，需要我們對其結(jié)構(gòu)進行稍微地調(diào)整。比如，可以把鏈表的兩頭連接，使其成為了一個環(huán)狀鏈表，通常稱為循環(huán)鏈表。只需要將表中最后一個結(jié)點的指針指向頭結(jié)點，鏈表就能成環(huán)

需要注意的是，雖然循環(huán)鏈表成環(huán)狀，但本質(zhì)上還是鏈表，因此在循環(huán)鏈表中，依然能夠找到頭指針和首元節(jié)點等。所以，不要隨意改變頭指針的指向。在使用循環(huán)鏈表時，附帶最多的操作就是遍歷鏈表。

5.靜態(tài)鏈表

靜態(tài)鏈表，也是線性存儲結(jié)構(gòu)的一種，它兼顧了順序表和鏈表的優(yōu)點于一身，可以看做是順序表和鏈表的升級版。使用靜態(tài)鏈表存儲數(shù)據(jù)，數(shù)據(jù)全部存儲在數(shù)組中（和順序表一樣），但存儲位置是隨機的，數(shù)據(jù)之間"一對一"的邏輯關(guān)系通過一個整形變量（稱為"游標"，和指針功能類似）維持（和鏈表類似）。

靜態(tài)鏈表存儲數(shù)據(jù)

通過 "數(shù)組+游標" 的方式存儲具有線性關(guān)系數(shù)據(jù)的存儲結(jié)構(gòu)就是靜態(tài)鏈表。
靜態(tài)鏈表會將第一個數(shù)據(jù)元素放到數(shù)組下標為 1 的位置（a[1]）中。從 a[1] 存儲的數(shù)據(jù)元素 1 開始，通過存儲的游標變量 3，就可以在 a[3] 中找到元素 1 的直接后繼元素 2；同樣，通過元素 a[3] 存儲的游標變量 5，可以在 a[5] 中找到元素 2 的直接后繼元素 3，這樣的循環(huán)過程直到某元素的游標變量為 0 截止（因為 a[0] 默認不存儲數(shù)據(jù)元素）。