前言

在前面記錄八 線性表的順序存儲結(jié)構(gòu)和記錄九 線性表的順序存儲結(jié)構(gòu)擴(kuò)展(動態(tài)順序表)中我們了解到線性表的順序存儲結(jié)構(gòu)。我們能夠了解到其順序表的優(yōu)缺點。我們知道，順序表的查找和更新是十分快的。通過下標(biāo)索引的話，其時間復(fù)雜度為常數(shù)階。但是，我們在進(jìn)行插入，刪除的時候，我們發(fā)現(xiàn)，我們通常需要移動大量的數(shù)據(jù)才可以完成。有沒有什么存儲結(jié)構(gòu)能夠快速的插入和刪除呢？
當(dāng)然有，那就是鏈?zhǔn)酱鎯Y(jié)構(gòu)。

順序表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

鏈?zhǔn)酱鎯Y(jié)構(gòu)，又叫鏈接存儲結(jié)構(gòu)。在計算機(jī)中用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素(這組存儲單元可以是連續(xù)的,也可以是不連續(xù)的).【1】

鏈?zhǔn)酱鎯Y(jié)構(gòu)的存儲單元通常是不連續(xù)的，其每一個數(shù)據(jù)結(jié)點通常是由兩個域組成。數(shù)據(jù)域和指針域(我通常認(rèn)為指針域為關(guān)系域，因為部分語言并沒有指針。以下，我會將指針域改成關(guān)系域)。然后每一個數(shù)據(jù)結(jié)點進(jìn)行連接。

數(shù)據(jù)域 ：存放數(shù)據(jù)的地方。

關(guān)系域(指針域) ：存放數(shù)據(jù)之間關(guān)系的地方。

其存儲結(jié)構(gòu)抽象類型為

ADT 鏈?zhǔn)酱鎯Y(jié)構(gòu){
    數(shù)據(jù)域：存放數(shù)據(jù)
    關(guān)系域(指針域)：存放數(shù)據(jù)之間的關(guān)系
}結(jié)點;

那么數(shù)據(jù)之間是如何聯(lián)系的呢？下看圖:

舉個栗子圖

鏈表

鏈表，是其線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的簡稱。鏈表通常有：單鏈表、雙向鏈表、循環(huán)鏈表、循環(huán)雙向鏈表、靜態(tài)鏈表，循環(huán)靜態(tài)鏈表、循環(huán)靜態(tài)雙向鏈表等等。

單鏈表大致如下圖(這個是我學(xué)鏈表的時候理解畫的。偷一下懶)

結(jié)構(gòu)體實現(xiàn)鏈表

掌握了單鏈表，除了靜態(tài)鏈表之外，其它的都比較好理解。

單鏈表的方法

構(gòu)造單鏈表

在構(gòu)造單鏈表之前，我們首先要了解到一個概念：首元結(jié)點和頭結(jié)點。

首元結(jié)點：帶有數(shù)據(jù)的第一個結(jié)點。

頭結(jié)點：首元結(jié)點的直接前驅(qū)結(jié)點，其沒有直接前驅(qū)。

(帶頭結(jié)點的鏈表和不帶頭結(jié)點的鏈表)

首元結(jié)點和頭結(jié)點

添加結(jié)點

添加結(jié)點也有兩種方式：頭插法和尾插法。

頭插法：數(shù)據(jù)通過頭指針直接添加到鏈表中。(頭插法在遍歷的時候，數(shù)據(jù)的順序和插入時的順序是相反的。例如，插入的順序是1、2、3、4、5。則遍歷輸出后則就是5、4、3、2、1.)

尾插法：首先遍歷找到尾部結(jié)點。然后通過尾部結(jié)點將數(shù)據(jù)添加到鏈表中。(其主要是麻煩在需要找到尾部結(jié)點。如果只有頭指針，則每一次添加都需要遍歷一次來鏈表。所以我們通常會添加一個尾指針來指向鏈表的尾部。)

方法為：
1.頭插法：
1.添加的結(jié)點的關(guān)系域(指針域)先指向首元結(jié)點。(保存原先的數(shù)據(jù))
2.再將頭結(jié)點指向新添加的結(jié)點。(沒有頭結(jié)點，就直接讓添加的結(jié)點變成頭指針)

(帶頭結(jié)點的的鏈表)
newNode->next = header->next;//新添加的結(jié)點先保存好原先的數(shù)據(jù)。指向首元結(jié)點
header->next = newNode;//再將頭結(jié)點的指針域指向新添加的結(jié)點。
(不帶頭結(jié)點的鏈表)
newNode->next = header;//先保存好原先的數(shù)據(jù)。即添加結(jié)點的關(guān)系域(指針域)指向首元結(jié)點
header = newNode;//修改頭指針

2.尾插法：
1.先找到尾結(jié)點。
2.尾結(jié)點的指針域指向新添加的結(jié)點。

(沒有尾結(jié)點的鏈表)
Node move = new Node;//創(chuàng)建一個移動的指針。(不能用頭指針去尋找尾結(jié)點，因為頭指針是整個鏈表的標(biāo)識。如果我們找不到頭結(jié)點的時候，我們就找不到鏈表了。)
//帶有頭結(jié)點的鏈表
while(move ->next != NULL){//循環(huán)找到尾結(jié)點
    move = move->next;
}
//不帶頭結(jié)點的鏈表
while(move != NULL){//循環(huán)找到尾結(jié)點
    move = move->next;
}
newNode->next = move->next;//先保存好尾部結(jié)點的指針域。(單鏈表尾結(jié)點為NULL)
move->next = newNode;//尾部結(jié)點指向新添加的數(shù)據(jù)。
(有尾結(jié)點的鏈表)
newNode->next = tail->next;//先保存好尾部結(jié)點的指針域
tail  = newNode;//尾部結(jié)點指向新的結(jié)點

插入數(shù)據(jù)

插入數(shù)據(jù)

方法：
1.找到需要插入結(jié)點的前一個結(jié)點。
2.將插入結(jié)點的指針域指向第一步找到結(jié)點的指針域。(保存數(shù)據(jù)，防止數(shù)據(jù)丟失)
3.將第一步找到的結(jié)點的指針域指向插入結(jié)點
(不需要移動大量的數(shù)據(jù)，只需要移動指針即可。)

(設(shè)需要將newNode結(jié)點插入到insertNode結(jié)點之前)
Node move = new Node;//創(chuàng)建一個移動的指針。(不能用頭指針去尋找尾結(jié)點，因為頭指針是整個鏈表的標(biāo)識。如果我們找不到頭結(jié)點的時候，我們就找不到鏈表了。)
//帶有頭結(jié)點的鏈表(沒有頭結(jié)點特別不好插入。各種判斷。這里就不進(jìn)行了。)
while(move->next != NULL){//循環(huán)遍歷，查找的數(shù)據(jù)的前一個結(jié)點。
    if (move->next->data == insertNode->data){//查找到前一個結(jié)點
         break;         
    }
    move = move->next;
}
newNode->next = move ->next;//(move為插入結(jié)點的前一個結(jié)點.move->next指向的就是insertNode)
move->next = newNode;//插入新結(jié)點

刪除數(shù)據(jù)

刪除數(shù)據(jù)

方法：
1.找到需要刪除結(jié)點的前一個結(jié)點。
2.保存第一步找到的結(jié)點的指針域。
3.將第一步找到的結(jié)點的指針域等于下一個結(jié)點的指針域。
3.釋放第二步保存的指針域。

(設(shè)需要刪除delNode結(jié)點)
Node move = new Node;//創(chuàng)建一個移動的指針。(不能用頭指針去尋找尾結(jié)點，因為頭指針是整個鏈表的標(biāo)識。如果我們找不到頭結(jié)點的時候，我們就找不到鏈表了。)
//帶有頭結(jié)點的鏈表
while(move->next != NULL){
      if(move->next->data == delNode->data){//第一步：判斷是否為需要刪除的結(jié)點(move是需要刪除結(jié)點的前一個結(jié)點的)
              Node del = move->next;//第二步：保存需要刪除的結(jié)點
              move->next = move->next->next;//第三步：刪除結(jié)點
              delete del;//第四步:釋放內(nèi)存
              break;
      }
      move = move->next;
}

總結(jié)

鏈?zhǔn)酱鎯Y(jié)構(gòu)使用與大量的插入和刪除操作。其不適合與查找操作。因為其查找每次都的遍歷整個鏈表。而且。鏈?zhǔn)酱鎯Y(jié)構(gòu)會比順序存儲結(jié)構(gòu)多一個空間。用來存放數(shù)據(jù)的關(guān)系。且鏈?zhǔn)酱鎯Y(jié)構(gòu)不需要連續(xù)的空間。而順序存儲結(jié)構(gòu)一定是連續(xù)的。

鏈?zhǔn)酱鎯Y(jié)構(gòu)的抽象類已經(jīng)在記錄七 線性表給出。

參考資料:【1】百度百科-鏈?zhǔn)酱鎯Y(jié)構(gòu)