?作者簡介：嵌入式入坑者，與大家一起加油，希望文章能夠幫助各位！！！！
📃個人主頁：@rivencode的個人主頁
🔥系列專欄：玩轉數據結構
💬推薦一款模擬面試、刷題神器，從基礎到大廠面試題👉點擊跳轉刷題網站進行注冊學習

創新互聯聯系熱線：028-86922220，為您提供成都網站建設網頁設計及定制高端網站建設服務，創新互聯網頁制作領域10多年，包括成都樓梯護欄等多個方面擁有豐富設計經驗，選擇創新互聯，為企業保駕護航。目錄

• 一.順序表與鏈表的對比
• 二.單鏈表的介紹
• 三.單鏈表的基本操作
• • 打印鏈表
  • 清空鏈表
  • 創建節點
  • 尾插結點
  • 頭插結點
  • 尾刪結點
  • 頭刪結點
  • 查找值為x的節點
  • 在pos前面插入一個結點
  • 刪除pos指針指向的結點
• 四.鏈表結構介紹
• 五.雙向帶頭循環鏈表
• • 創建結點
  • 鏈表初始化
  • 銷毀鏈表
  • 清空鏈表
  • 打印鏈表
  • 尾插結點
  • 頭插結點
  • 尾刪結點
  • 頭刪結點
  • 查找節點值為x的結點
  • 在pos前面插入一個結點
  • 刪除pos指針指向的結點
  • 鏈表長度
  • 六.總結

一.順序表與鏈表的對比

• 線性表
  線性表（linear list）是n個具有相同特性的數據元素的有限序列。 線性表是一種在實際中廣泛使用的數據結構，常見的線性表：順序表、鏈表、棧、隊列等，線性表在邏輯上是線性結構，也就說是連續的一條直線。但是在物理結構（存儲結構）上并不一定是連續的，線性表在物理上存儲時，通常以順序表和鏈式結構的形式存儲。

• 線性表的順序存儲—>順序表
  是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構，一般情況下采用數組存儲。在數組上完成數據的增刪查改。

• 線性表的鏈式存儲
  線性表中的數據結點在內存中的位置是任意的，即邏輯上相鄰的數據元素在物理位置（內存存儲的位置）上不一定相鄰。

鏈式存儲結構的優點：

• 空間利用率高需要一個空間就分配一個空間
• 數據元素的邏輯次序靠節點的指針來指示，插入和刪除時不需要移動數據結點,任意位置插入刪除時間復雜度為O(1)

鏈式存儲結構的缺點：

• 存儲密度小，每個結點的指針域需要額外占用存儲空間。當每個結點的數據域所占字節不多時，指針域所占空間的比重顯得很大，存儲密度大空間利用率越大。

順序表因為只有數據域，沒有指針域所以它的存儲密度為大1
不過這個問題，一個結點也就多幾個指針，最多8個字節，所以若是在現代計算機這點空間已經不算什么，不過如果是像單片機這種嵌入式設備內存較小，所以還是會有一點點影響的

• 鏈式存儲結構是非隨機存取結構，對任一結點的操作都要從頭指針依次查找到該節點，算法復雜度較高。

順序表的優點：

• 存儲密度為1最高，因為沒有指針域空間利用率高
• 隨機存取，按位置訪問元素的時間復雜度為O(1)，直接根據數組下標訪問元素

順序表的缺點：

• 動態順序表增容會付出一定性能消耗，其次可能還是會存在一定的空間浪費（不可能擴容的剛剛好）
• 在頭部或者中部左右的插入刪除，需要移動元素，時間復雜度為O(N),效率低。
  
  總結：
  順序表的缺點就是鏈表的優點，而鏈表的缺點就是順序表的優點，所以說不能說鏈表一定就比順序表高級，我們要視情況而定。

二.單鏈表的介紹

• 線性表的鏈式存儲
  線性表中的數據結點在內存中的位置是任意的，即邏輯上是線性的數據元素在物理位置（內存存儲的位置）上不一定相鄰。

結點為什么在內存中是隨機存儲的呢
因為我們產生一個結點要給他分配內存是動態分配出來的（malloc），而分配的結點的內存的地址是隨機的，所以結點的地址是隨機的，也就是說結點在內存中的存儲是隨機的。

單鏈表的一個結點


我們只要知道一個結構體的指針（地址），就能訪問該結構體的成員（如果成員里面又包含下一個結點（結構體）指針，又可以訪問下一個結點的成員）

若基礎不好的先請參考：
《指針詳解》
《結構體詳解》
其實鏈表你把結構體與指針搞明白了，鏈表真的隨便拿捏。

三.單鏈表的基本操作

不帶頭結點單向不循序鏈表：

當鏈表為空時，頭指針指向空，當鏈表不為空時頭指針必須指向第一個結點

打印鏈表

void SListPrint(SLTNode *phead)
{SLTNode *cur = phead;
	while (cur != NULL)
	{printf("%d->", cur->data);
		cur=cur->next;
	}
	printf("NULL\n");
}

清空鏈表

//清空單鏈表

void SListClear(SLTNode **pphead)
{SLTNode *cur = *pphead;
	SLTNode *next = NULL;
	while (cur != NULL)
	{next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

如果要改變頭指針的值，雖然頭指針是一個指針，但是指針一樣有它的地址，如果在一個函數中要改變它的值，照樣要傳頭指針的地址，在解引用改變頭指針的值，如果你只是值傳遞，則傳過去的只是該頭指針的臨時拷貝，一旦出函數會自動銷毀并不會影響頭指針本身的值。

創建節點

SLTNode* CreateSListNode(SLTDataType x)
{SLTNode* NewNode = (SLTNode*)malloc(sizeof(SLTNode));
	NewNode->data = x;
	NewNode->next = NULL;
	return NewNode;
}

因為插入元素時都先要創建一個新結點，所以為了避免代碼冗余，將創建新結點單獨封裝成一個函數。

尾插結點

void SListPushBack(SLTNode **pphead, SLTDataType x)
{SLTNode*NewNode = CreateSListNode(x);
	//當鏈表為空
	if (*pphead == NULL)
	{*pphead = NewNode;
	}
	else
	{SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{	tail=tail->next;
		}
		tail->next = NewNode;
	}
	
}

不要寫了if不寫else，搞得后面又插入一個結點

頭插結點

//鏈表頭部插入一個節點
void SListPushFront(SLTNode **pphead, SLTDataType x)
{SLTNode*NewNode = CreateSListNode(x);
	NewNode->next = *pphead;
	*pphead = NewNode;
}

尾刪結點

void SListPopBack(SLTNode **pphead)
{//鏈表為空
	if (*pphead == NULL)
	{return;
	}
	//只有一個節點
	else if ((*pphead)->next == NULL)
	{free(*pphead);
		*pphead = NULL;
	}
	//有多個節點
	else
	{SLTNode*prev = NULL;
		SLTNode*tail = *pphead;
		while (tail->next != NULL)
		{	prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}

}

有以下幾種情況：

• 當鏈表為空

• 只有一個結點
  
• 有多個結點
  

頭刪結點

void SListPopFront(SLTNode **pphead)
{if (*pphead == NULL)
	{return;
	}
	SLTNode *next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

查找值為x的節點

查找值為x的節點并返回節點的指針

//查找值為x的節點并返回節點的指針
SLTNode * SListFind(SLTNode *phead, SLTDataType x)
{SLTNode *cur = phead;
	while (cur != NULL)
	{if (cur->data == x)
		{	//找到返回該結點指針
			return cur;
		}
		cur = cur->next;
	}
	//找不到返回NULL指針
	return NULL;
}

在pos前面插入一個結點

在pos指針指向的結點的前一個位置插入一個結點

//在pos指針前一個插入一個節點
void SListInsert(SLTNode **pphead, SLTNode *pos, SLTDataType x)
{//pos在第一個節點，相當與頭插
	if (*pphead== pos)
	{SListPushFront(pphead, x);
	}
	else
	{SLTNode *NewNode = CreateSListNode(x);
		SLTNode *prev = *pphead;
		while (prev->next != pos)
		{	prev = prev->next;
		}
		prev->next = NewNode;
		NewNode->next = pos;
	}
	
}

如果pos的位置是第一個結點，則在第一個結點前一個插入結點則為頭插，直接調用頭插的接口函數即可。

pos在其他位置：

刪除pos指針指向的結點

void SListErese(SLTNode **pphead, SLTNode *pos)
{if (*pphead == pos)
	{SListPopFront(pphead);
	}

	else
	{SLTNode *prev = *pphead;
		while (prev->next != pos)
		{	prev = prev->next;
		}
		prev->next=pos->next;
		free(pos);
	}
		
}

一樣的如果pos的位置是第一個結點，則在第一個結點前一個刪除結點則為頭刪，直接調用頭刪的接口函數即可。

pos在其他位置：

四.鏈表結構介紹

• 頭指針

頭指針是指向鏈表中第一個結點(存儲該節點的地址)。如果鏈表中有頭結點，則頭指針指向頭結點；若鏈表中沒有頭結點，則頭指針指向鏈表中第一個數據結點。

• 頭結點
  頭結點，鏈表中第一個結點，一般不存儲任何數據，若鏈表有頭結點則頭指針一直指向頭指針。
  
  頭結點本身沒有什么作用，頭結點就起到一個站崗的作用

鏈表帶頭結點的優點：

當鏈表為空表時，插入，刪除結點都是在頭結點后面，頭結點指向了第一個帶數據的結點。

當我們單鏈表無頭結點時當我們頭插，頭插的時候，我們都需要移動頭指針的位置指向新的第一個結點，當鏈表為空時又要將頭結點置NULL，這些操作我們都需要去改變頭指針的值，而改變頭指針要傳頭指針的地址的，用二級指針來操作，無疑是增加了編程的難度，如果鏈表有頭結點，而頭指針一直指向頭結點，不管是頭刪，頭插，都是在頭結點后面增加刪除，而頭指針一直指向頭結點不用發生改變，只需要一級指針就搞定

• 循環鏈表
  循環鏈表：是一種頭尾相接的鏈表（最后一個結點的指針指向第一個結點）
  
  優點：從表中任意一節點出發可找到表中其他結點

注意：
循環鏈表中沒有NULL指針，故遍歷鏈表時，其終止條件是判斷是不是等于頭指針。

• 雙向鏈表
  前面我們用單鏈表如果我們知道一個結點但我們不能直接找到該結點前面的一個結點。

所以雙向鏈表：在單鏈表的每一個結點再增加一個指向其直接前驅的指針域prev，這樣鏈表中就形成了有兩個方向不同的鏈

• 單向不帶頭不循環
  

• 單向帶頭不循環
  

• 單向不帶頭循環
  

• 單向帶頭循環
  

• 雙向不帶頭不循環
  
  prev的值也為空

• 雙向不帶頭循環
  

• 雙向帶頭不循環
  
  prev的值也為空

• 雙向帶頭循環
  

五.雙向帶頭循環鏈表 創建結點

ListNode*CreateListNode(LTDataType x)
{ListNode*NewNode = (ListNode*)malloc(sizeof(ListNode));
	NewNode->data = x;
	NewNode->next = NULL;
	NewNode->prev = NULL;
	return NewNode;
}

一個新的結點，先將next，prev置空

鏈表初始化

//鏈表初始化
ListNode *ListInit()
{ListNode*phead = CreateListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

空表

銷毀鏈表

void ListDestory(ListNode**pphead)
{ListNode*cur = (*pphead)->next;
	while (cur != *pphead)
	  {  ListNode* next = cur->next;
		  free(cur);
		  cur = next;
	  }
	free(*pphead);
	  *pphead = NULL;
}

清空鏈表

//清空鏈表
void ListClear(ListNode*phead)
{ListNode*cur = phead->next;
	while (cur != phead)
	{ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	phead->next = phead;
	phead->prev = phead;
}

只清空的話不需要釋放頭結點，不過要將頭結點的兩個指針域都指向自己（回到空表狀態）

打印鏈表

//打印鏈表
void Listprint(ListNode*phead)
{ListNode*cur = phead->next;
	while (cur != phead)
	{printf("%d ",cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

遍歷是看是否遍歷到了頭結點才停下來。

尾插結點

//尾插
void ListPushBack(ListNode*phead, LTDataType x)
{ assert(phead != NULL);
	 ListNode*NewNode = CreateListNode(x);
	 ListNode*tail = phead->prev;
	 tail->next = NewNode;
	 NewNode->prev = tail;
	 NewNode->next = phead;
	 phead->prev = NewNode;
}

可以怎么寫：但是這里水太深你可能把握不住

頭插結點

我們只要抓住一點：把要操作的結點事先存儲起來，不管我們怎么連接結點，我們都找的到要操作的結點

//頭插
void ListPushFront(ListNode*phead, LTDataType x)
{ assert(phead != NULL);
	 ListNode*NewNode = CreateListNode(x);
	 ListNode*first = phead->next;
	 phead->next = NewNode;
	 NewNode->prev = phead;
	 NewNode->next = first;
	 first->prev = NewNode;
}

尾刪結點

//尾刪
void ListPopBack(ListNode*phead)
{  assert(phead != NULL);
	  assert(phead->next != phead);
	  ListNode*tail = phead->prev;
	  ListNode*prev = tail->prev;
	  
	  prev->next = phead;
	  phead->prev = prev;
	  free(tail);
	  tail = NULL;
}

頭刪結點

//頭刪
void ListPopFront(ListNode*phead)
{   assert(phead != NULL);
	   assert(phead->next != phead); 
	   ListNode*first = phead->next;//除掉頭結點第一個結點
	   ListNode*second = first->next;//除掉頭結點第二個結點
	   
	   phead->next = second;
	   second->prev = phead;
	   free(first);
	   first = NULL;
}

查找節點值為x的結點

查找節點值為x的結點，返回指向節點的指針

//查找節點值為x，返回指向節點的指針
ListNode* ListFind(ListNode*phead, LTDataType x)
{  ListNode*cur = phead->next;
	  while (cur != phead)
	  {  if (cur->data == x)
		  {	  return cur;
		  }
		  cur = cur->next;
	  }
	  return NULL;
}

在pos前面插入一個結點

//在pos指針指向的節點前插入一個節點
void ListInsert(ListNode*pos, LTDataType x)
{   assert(pos != NULL);
	   ListNode*NewNode = CreateListNode(x);
	   ListNode*prev = pos->prev;
	   prev->next = NewNode;
	   NewNode->prev = prev;
	   NewNode->next = pos;
	   pos->prev = NewNode;
}

刪除pos指針指向的結點

void ListErase(ListNode*pos)
{   assert(pos !=NULL);
	   ListNode*next = pos->next;
	   ListNode*prev = pos->prev;
	   prev->next = next;
	   next->prev = prev;
	   free(pos);
	   pos = NULL;
}

鏈表長度

//鏈表長度
int ListLength(ListNode*phead)
{int len = 0;
	ListNode*cur = phead->next;
	while (cur != phead)
	{len++;
		cur = cur->next;
	}
	return len;
}

六.總結

只要搞懂結構體指針，明白鏈表的概念，直接拿捏，相信很多人學完了鏈表還是不知道鏈表會用在什么地方，因為我們平時編程基本上用不到鏈表，但是鏈表在操作系統中的使用非常廣泛，所以鏈表是非常重要重要的數據結構，有興趣的可以看看在實際項目中鏈表的應用->《FreeRTOS實時操作系統-鏈表的源碼解析》

結束語：
最近發現一款刷題神器，如果大家想提升編程水平，玩轉C語言指針，還有常見的數據結構（最重要的是鏈表和隊列）后面嵌入式學習操作系統的時如freerots、RT-Thread等操作系統，鏈表與隊列知識大量使用。
大家可以點擊下面連接進入牛客網刷題
點擊跳轉進入網站(C語言方向)
點擊跳轉進入網站(數據結構算法方向)

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

當前題目：C語言鏈表超詳解-創新互聯
文章源于：http://m.newbst.com/article40/dggoho.html

成都網站建設公司_創新互聯，為您提供建站公司、自適應網站、網站收錄、網站改版、網站營銷、網站設計

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯