相信如果看完了上期順序表的小伙伴應(yīng)該發(fā)現(xiàn)了順序表的諸多缺點：

? 中間/頭部的插入刪除，時間復(fù)雜度為O(N)！

? 增容需要申請新的空間，拷貝數(shù)據(jù)，釋放舊空間，會有不少的消耗。

? 增容一般是呈倍增長，勢必會有一定的空間浪費。

鏈表的OJ題會單獨出一期的哦！

那么，如何解決以上的問題呢？

? 那么什么是鏈表呢？—— 鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的 。

?實際中要實現(xiàn)的鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來就有8種鏈表結(jié)構(gòu)：

1. 單向、雙向? ? ? ? ?2. 帶頭、不帶頭? ? ? ? ? ? 3. 循環(huán)、非循環(huán)

我們只講最簡單和最復(fù)雜的，畢竟一句老話，冬天到了春天還會遠(yuǎn)嗎？?

今天我們講無頭單向非循環(huán)鏈表，下期講帶頭雙向循環(huán)鏈表 ！

好的，有了上面的認(rèn)識正式進(jìn)入我們本期的學(xué)習(xí)?。

無頭單向非循環(huán)鏈表：結(jié)構(gòu)簡單，一般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié) 構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。

?我們來看到單鏈表的架構(gòu)：

?? 單鏈表和順序表不一樣，我們是需要的時候動態(tài)申請一個節(jié)點空間就夠了！

SLTNode* BuySListNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
		return NULL;//做空指針判斷
	newnode->data = x;
	newnode->next = NULL;
 
	return newnode;
}

這里我們利用malloc函數(shù)開辟了一個SLTNode大小的空間(得用SLTNode* 來接收)，malloc和realloc一樣如果開辟失敗會返回空指針，所以這我們需要先做判斷！不為空則把數(shù)據(jù)放入data，并且把指向下一個節(jié)點的 next 置空！并且返回新節(jié)點的地址！(這里如果不明白則需要補充結(jié)構(gòu)體，指針，動態(tài)內(nèi)存開辟的知識)

? 首先我們還是來實現(xiàn)單鏈表的頭部插入數(shù)據(jù)！

這里我們可以看到，不帶哨兵位(帶頭鏈表)鏈表需要改變頭指針位置，下期我們學(xué)帶頭雙向循環(huán)鏈表就可以不用雙指針了！

? 下面是我們的單鏈表尾部插入數(shù)據(jù)！

? 接著來實現(xiàn)單鏈表頭部刪除數(shù)據(jù)！

?? 下面來到單鏈表的尾部刪除數(shù)據(jù)！

? 在指定元素前插入節(jié)點！

?這個我們首先需要找到指定節(jié)點元素的地址！

?接下來就是實現(xiàn)我們的指定元素前插入節(jié)點的函數(shù)了！

同理我們接著來實現(xiàn)刪除指定元素的節(jié)點！

最后其實還有一個修改節(jié)點數(shù)據(jù)，這個看了上期的順序表實現(xiàn)起來就很簡單，留給你們自己研究去啦！學(xué)好編程多想，多敲代碼準(zhǔn)沒錯！?

????????那么以上這就是我們無頭單向非循環(huán)鏈表的常見接口了，如果你看完感覺比較吃力看不懂的話，建議多去回顧下c語言指針，結(jié)構(gòu)體，動態(tài)內(nèi)存這幾張的內(nèi)容！當(dāng)你能把這個單鏈表理解透徹了，下一期的帶頭雙向循環(huán)鏈表也很容易理解的，代碼實現(xiàn)起來更輕松，加油吧！

最后還是那句話?我們一起快樂編程不頭禿！

gitee(碼云)：Mercury. (zzwlwp) - Gitee.com??