快捷導(dǎo)航

C++超詳細(xì)分析單鏈表的實(shí)現(xiàn)與常見接口

更新時(shí)間：2022年03月24日 10:28:58 作者：程序猿教你打籃球

鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的，本章帶你分析單鏈表的實(shí)現(xiàn)與常見接口

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

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

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

?? 增容一般是呈倍增長，勢(shì)必會(huì)有一定的空間浪費(fèi)。

鏈表的OJ題會(huì)單獨(dú)出一期的哦！

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

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

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

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

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

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

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

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

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

??? 單鏈表和順序表不一樣，我們是需要的時(shí)候動(dòng)態(tài)申請(qǐng)一個(gè)節(jié)點(diǎn)空間就夠了！

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

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

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

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

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

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

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

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

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

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

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

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

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

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

到此這篇關(guān)于C++超詳細(xì)分析單鏈表的實(shí)現(xiàn)與常見接口的文章就介紹到這了,更多相關(guān)C++ 單鏈表的實(shí)現(xiàn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: