網站首頁編程語言正文

C++超詳細分析單鏈表的實現與常見接口_C 語言

作者：程序猿教你打籃球 ? 更新時間： 2022-05-27 編程語言

相信如果看完了上期順序表的小伙伴應該發現了順序表的諸多缺點：

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

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

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

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

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

?? 那么什么是鏈表呢？—— 鏈表是一種物理存儲結構上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。

?實際中要實現的鏈表的結構非常多樣，以下情況組合起來就有8種鏈表結構：

1. 單向、雙向? ? ? ? ?2. 帶頭、不帶頭? ? ? ? ? ? 3. 循環、非循環

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

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

好的，有了上面的認識正式進入我們本期的學習??。

無頭單向非循環鏈表：結構簡單，一般不會單獨用來存數據。實際中更多是作為其他數據結構的子結構，如哈希桶、圖的鄰接表等等。另外這種結構在筆試面試中出現很多。

?我們來看到單鏈表的架構：

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

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

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

?? 首先我們還是來實現單鏈表的頭部插入數據！