相信如果看完了上期順序表的小伙伴應(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ù)雜的，畢竟一句老話，冬天到了春天還會遠嗎？??

今天我們講無頭單向非循環(huán)鏈表，下期講帶頭雙向循環(huá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??

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

最新評論