互聯(lián)網(wǎng)中鏈表是一種采用什么存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表

這篇文章主要介紹互聯(lián)網(wǎng)中鏈表是一種采用什么存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表，文中介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！

鏈表是一種采用“鏈?zhǔn)健贝鎯?chǔ)結(jié)構(gòu)存儲(chǔ)的線性表。鏈表的數(shù)據(jù)元素所占的存儲(chǔ)單元地址可以是連續(xù)的，也可以是不連續(xù)的，可根據(jù)需要臨時(shí)、動(dòng)態(tài)地申請(qǐng)分配相應(yīng)的存儲(chǔ)空間，數(shù)據(jù)元素之間的邏輯關(guān)系可以用“鏈”來(lái)表達(dá)。

本教程操作環(huán)境：windows7系統(tǒng)、Dell G3電腦。

為了克服順序表存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)，充分利用存儲(chǔ)空間和提高運(yùn)行效率，線性表可以采用另一種存儲(chǔ)結(jié)構(gòu)——鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱“鏈表（link list）”

一、鏈表概述

鏈表的數(shù)據(jù)元素所占的存儲(chǔ)單元地址可以是連續(xù)的，也可以是不連續(xù)的，可根據(jù)需要臨時(shí)、動(dòng)態(tài)地申請(qǐng)分配相應(yīng)的存儲(chǔ)空間，數(shù)據(jù)元素之間的邏輯關(guān)系可以用“鏈”來(lái)表達(dá)。

鏈表的插入和刪除不需要移動(dòng)數(shù)據(jù)元素，只需要修改鏈即可實(shí)現(xiàn)。

鏈表分類：

1.按鏈表內(nèi)存分配實(shí)現(xiàn)的方式分類

①動(dòng)態(tài)鏈表

②靜態(tài)鏈表

2.按鏈接方式分類

①單鏈表

②循環(huán)鏈表

③雙鏈表

（它們均為動(dòng)態(tài)鏈表）

二、單鏈表的定義

1.定義

為了表示每個(gè)數(shù)據(jù)元素ai與其直接后繼數(shù)據(jù)元素ai+1之間的邏輯關(guān)系，對(duì)于每個(gè)數(shù)據(jù)元素ai，除了存儲(chǔ)本身的信息外，還需要存儲(chǔ)一個(gè)指示其直接后繼的信息（后繼的存儲(chǔ)位置-地址）。

存儲(chǔ)數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，存儲(chǔ)直接后繼位置的域稱為指針域，指針域中存儲(chǔ)的信息稱為指針或鏈。

這兩部分信息組成數(shù)據(jù)元素ai的存儲(chǔ)映像，稱為結(jié)點(diǎn)。

n個(gè)結(jié)點(diǎn)鏈成一個(gè)鏈表，即為線性表（a1,a2,a3,...,an）的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，因?yàn)殒湵淼拿總€(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，所以稱為單鏈表。

對(duì)于線性表來(lái)說(shuō)，總有個(gè)頭有個(gè)尾，鏈表也不例外。鏈表中指向單鏈表第一個(gè)結(jié)點(diǎn)的指針叫做頭指針，整個(gè)鏈表的存取必須從頭指針開(kāi)始進(jìn)行，之后的每個(gè)結(jié)點(diǎn)都是上個(gè)結(jié)點(diǎn)的后繼指針指向的位置。鏈表的最后一個(gè)結(jié)點(diǎn)的指針為“空（通常用NULL表示）”——空指針。

為了方便實(shí)現(xiàn)鏈表的各種運(yùn)算，在單鏈表的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)之前設(shè)一個(gè)類型相同的結(jié)點(diǎn)，該結(jié)點(diǎn)稱為頭結(jié)點(diǎn)。

頭結(jié)點(diǎn)的數(shù)據(jù)域可以存儲(chǔ)一個(gè)特殊的標(biāo)志信息如鏈表的長(zhǎng)度，也可以不存儲(chǔ)任何數(shù)據(jù)。

鏈表的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)又稱為首結(jié)點(diǎn)和尾結(jié)點(diǎn)。

2.頭指針和頭結(jié)點(diǎn)的異同點(diǎn)

頭指針：

• 頭指針是指鏈表中指向第一個(gè)結(jié)點(diǎn)的指針，若鏈表有頭結(jié)點(diǎn)，則是指向頭結(jié)點(diǎn)的指針。

• 頭指針具有標(biāo)識(shí)作用，常用頭指針冠以鏈表的名字。

• 無(wú)論鏈表是否為空，頭指針均不為空。頭指針是鏈表的必要元素。

頭結(jié)點(diǎn)：

• 頭結(jié)點(diǎn)是為了操作的統(tǒng)一和方便而設(shè)立的，放在第一個(gè)元素的結(jié)點(diǎn)之前，其數(shù)據(jù)域一般無(wú)意。

• 有了頭結(jié)點(diǎn)，對(duì)在第一元素結(jié)點(diǎn)前插入結(jié)點(diǎn)和刪除第一個(gè)結(jié)點(diǎn)，其操作與其他結(jié)點(diǎn)的操作就統(tǒng)一了。

• 頭結(jié)點(diǎn)不一定是鏈表必須要素。

3.代碼演示

/*線性表的單鏈表存儲(chǔ)結(jié)構(gòu)*/
/*結(jié)點(diǎn)定義*/
typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node;

/*單鏈表定義*/
typedef struct Node *LinkList;

三、單鏈表的操作

1.插入操作

1）插入模擬

假設(shè)存儲(chǔ)元素e的結(jié)點(diǎn)為s,將s插入到ai結(jié)點(diǎn)后面，如何操作？

思考：兩句插入代碼能否交換？

不能，如果調(diào)換過(guò)來(lái)，會(huì)導(dǎo)致ai+1等后面的元素?zé)o法找到，因?yàn)閟的指針域沒(méi)有指向ai+1的地址。

2）單鏈表第i個(gè)數(shù)據(jù)插入結(jié)點(diǎn)的算法思路

• 聲明一個(gè)結(jié)點(diǎn)p指向鏈表的第一個(gè)結(jié)點(diǎn)，初始化j=1;

• 當(dāng)j<i時(shí)，遍歷鏈表,讓p的指針向后移動(dòng)，不斷指向下一個(gè)結(jié)點(diǎn)，j++;

• 若到鏈表末尾p為空，則說(shuō)明第i個(gè)元素不存在；若查找成功，生成一個(gè)空節(jié)點(diǎn)s（使用malloc函數(shù)）

• 將數(shù)據(jù)元素e賦值給s->data,即為s->data=e;

• 插入標(biāo)準(zhǔn)語(yǔ)句：s->next=p->next；p->next=s;

• 返回成功。

2.刪除操作

1）刪除模擬

假設(shè)存儲(chǔ)元素ai的結(jié)點(diǎn)為q,要實(shí)現(xiàn)將結(jié)點(diǎn)q刪除單鏈表的操作。

2）單鏈表刪除第i個(gè)數(shù)據(jù)結(jié)點(diǎn)的算法思路

• 聲明一個(gè)結(jié)點(diǎn)p指向鏈表的第一個(gè)結(jié)點(diǎn)，初始化j=1;

• 當(dāng)j<i時(shí)，遍歷鏈表,讓p的指針向后移動(dòng)，不斷指向下一個(gè)結(jié)點(diǎn)，j++;

• 若到鏈表末尾p為空，則說(shuō)明第i個(gè)元素不存在；若查找成功，將刪除結(jié)點(diǎn)p->next賦值給q

• 插入標(biāo)準(zhǔn)語(yǔ)句：p->next=q->next；

• 將q結(jié)點(diǎn)賦值給e,即為e=q->data;

• 釋放q結(jié)點(diǎn)

• 返回成功。

四、單鏈表結(jié)構(gòu)和順序表結(jié)構(gòu)對(duì)比

存儲(chǔ)方式：

• 順序表用一段連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的數(shù)據(jù)元素

• 單鏈表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，用一組任意的存儲(chǔ)單元存放線性表元素

時(shí)間性能：

①查找

• 順序表O(1)

• 單鏈表O(n)

②插入和刪除

• 順序表O(n)

• 單鏈表O(1)

空間性能：

• 順序表需要預(yù)分配存儲(chǔ)空間，分大了，浪費(fèi)，分小了易發(fā)生上溢

• 單鏈表不需要預(yù)分配存儲(chǔ)空間，需要多少都可以分配，元素個(gè)數(shù)不受限制

以上是“互聯(lián)網(wǎng)中鏈表是一種采用什么存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對(duì)大家有幫助，更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！