什么是單鏈表？

單鏈表是一種常見(jiàn)的鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)和操作數(shù)據(jù)元素的集合。它由一系列的節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)包含兩個(gè)部分：數(shù)據(jù)域和指針域。

單鏈表的每個(gè)節(jié)點(diǎn)包含了存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)域，以及指向下一個(gè)節(jié)點(diǎn)的指針域。通過(guò)這些指針域，節(jié)點(diǎn)之間可以按順序連接起來(lái)，形成一個(gè)鏈?zhǔn)浇Y(jié)構(gòu)。鏈表的最后一個(gè)節(jié)點(diǎn)通常指向一個(gè)特殊的空節(jié)點(diǎn)（NULL或nullptr），表示鏈表的結(jié)束。

相比于數(shù)組，鏈表的一大優(yōu)勢(shì)是它的動(dòng)態(tài)性。在鏈表中，節(jié)點(diǎn)的添加、刪除可以通過(guò)修改指針的指向來(lái)完成，不需要像數(shù)組那樣進(jìn)行元素的移動(dòng)。這使得鏈表在插入和刪除操作頻繁的場(chǎng)景中具有更高的效率。

鏈表的一個(gè)缺點(diǎn)是訪問(wèn)節(jié)點(diǎn)需要從頭節(jié)點(diǎn)開(kāi)始依次遍歷，因?yàn)殒湵碇械墓?jié)點(diǎn)并不是在內(nèi)存中連續(xù)存儲(chǔ)的。這導(dǎo)致了鏈表的訪問(wèn)時(shí)間復(fù)雜度為O(n)，其中n是鏈表的長(zhǎng)度。相比之下，數(shù)組可以通過(guò)索引直接訪問(wèn)元素，時(shí)間復(fù)雜度為O(1)。

1. 按位查找

1. 單鏈表按位查找是指根據(jù)節(jié)點(diǎn)在鏈表中的位置（即節(jié)點(diǎn)序號(hào)或下標(biāo)）來(lái)查找節(jié)點(diǎn)的操作。通常情況下，我們需要查找的節(jié)點(diǎn)序號(hào)是從1開(kāi)始計(jì)數(shù)的，即第1個(gè)節(jié)點(diǎn)、第2個(gè)節(jié)點(diǎn)、第3個(gè)節(jié)點(diǎn)等。

2. 單鏈表按位查找的基本思路是從鏈表頭節(jié)點(diǎn)開(kāi)始，遍歷鏈表，直到找到第k個(gè)節(jié)點(diǎn)，或者鏈表遍歷結(jié)束。如果鏈表遍歷結(jié)束仍未找到第k個(gè)節(jié)點(diǎn)，則返回空指針。
   平均時(shí)間復(fù)雜度：O(n)

//按位查找
LNode *GetElem(LinkList L, int i)
{if(i < 0)     //判斷i是否合法return NULL;LNode *p;  //指針p指向當(dāng)前掃描到的結(jié)點(diǎn)int j = 0;  //當(dāng)前p指向的是第幾個(gè)結(jié)點(diǎn)p = L;     //L指向頭結(jié)點(diǎn)， 頭結(jié)點(diǎn)是第0個(gè)結(jié)點(diǎn)（不存數(shù)據(jù)）while(p != NULL && j < i) //循環(huán)找到第i個(gè)結(jié)點(diǎn){p = p->next;    //讓p指針依次往后移j++;}return p;
}

i 的值有兩種極端情況，分別是 i 取最小0 和取最大5

若 i = 0; while循環(huán)不符合，返回return p; 此時(shí)p指針會(huì)指向頭結(jié)點(diǎn), 如下圖所示

若 i = 5； j++遞增到5后，此時(shí)p指針指向鏈表末尾空指針NULL，p != NULL不滿(mǎn)足，退出while循環(huán)，p返回NULL

所以當(dāng) i 不合法時(shí)，最終返回的都是NULL, 那么當(dāng)別人調(diào)用此基本操作時(shí)，只要判斷下此次的返回值是不是NULL, 就能知道這次的按位查找是否查找成功，這樣的算法才具有健壯性。

既然我們實(shí)現(xiàn)了按位查找的操作，那么以后按位插入和按位刪除時(shí)，就可以直接調(diào)用基本操作來(lái)實(shí)現(xiàn)。如下圖所示：
基本封裝的好處：簡(jiǎn)潔易維護(hù)

2. 按值查找

時(shí)間復(fù)雜度：O（n）
單鏈表按值查找需要遍歷鏈表的每一個(gè)節(jié)點(diǎn)，直到找到節(jié)點(diǎn)的值等于目標(biāo)值，或者遍歷結(jié)束沒(méi)有找到目標(biāo)值，返回空指針。

• 在按值查找單鏈表時(shí)，需要注意以下幾點(diǎn)：

1. 單鏈表查找需要遍歷整個(gè)鏈表，時(shí)間復(fù)雜度為 O(n)，其中 n 是鏈表節(jié)點(diǎn)的個(gè)數(shù)。
2. 當(dāng)鏈表為空時(shí)，需要特別處理。
3. 如果目標(biāo)值在鏈表中不存在，可能需要額外處理，比如返回一個(gè)空指針，或者打印出 “Not Found” 等提示信息。
4. 需要根據(jù)具體問(wèn)題和代碼實(shí)現(xiàn)，特別注意鏈表頭節(jié)點(diǎn)指針的正確性，以及節(jié)點(diǎn)指針的移動(dòng)和連接等操作。

假設(shè)本例中的ElemType是int類(lèi)型

//按值查找， 找到數(shù)據(jù)域 == e 的結(jié)點(diǎn)
LNode *LocateElem(LinkList L, ElemType e) 
{LNode *p = L->next;//從第1個(gè)結(jié)點(diǎn)開(kāi)始查找數(shù)據(jù)域?yàn)閑的結(jié)點(diǎn)while(p != NULL && p->data != e)p = p->next;return p;    //找到后返回該結(jié)點(diǎn)指針，否則返回NULL
}

若e = 8, 當(dāng) p指向第一個(gè)結(jié)點(diǎn)時(shí)，5 ！= 8，p移向下一個(gè)結(jié)點(diǎn)

當(dāng)p移動(dòng)到第2個(gè)結(jié)點(diǎn)時(shí)，找到數(shù)據(jù)8，此時(shí)while循環(huán)退出，返回 return p

當(dāng)e = 6時(shí)，p指針不斷往后移，當(dāng)p指向NULl時(shí)，while循環(huán)不滿(mǎn)足，退出循環(huán)，返回return p
當(dāng)LocateElem()函數(shù)的調(diào)用者接受到NULL時(shí)，就說(shuō)明并不存在數(shù)據(jù)域等于6的結(jié)點(diǎn)。

3. 求單鏈表的長(zhǎng)度

時(shí)間復(fù)雜度：O(n)

//求表的長(zhǎng)度
int length(LinkList L)
{int len = 0; //統(tǒng)計(jì)表長(zhǎng)LNode *p = L;while(p->next != NULL){p = p->next;len++;}return len;
}

4. 知識(shí)回顧