C++如何實現單鏈表

小編給大家分享一下C++如何實現單鏈表，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

單鏈表的實現(從入門到熟練)

概念和結構

概念：鏈表是一種物理存儲結構上非連續、非順序的存儲結構

數據元素的邏輯順序是通過鏈表中的指針鏈 接次序實現的

圖示：

注意：

鏈表結構在邏輯上為連續的，但是物理上（內存中）不一定連續

鏈表節點都是在堆上申請出來的，申請空間按一定策略分配

結構種類

鏈表具有多種結構：單向\雙向，帶頭\不帶頭，循環\非循環

實際上最常用的是：無頭單向非循環鏈表，帶頭雙向循環鏈表

鏈表的實現

注意：這里實現的是無頭單向非循環鏈表

增刪查改接口

// 動態申請一個節點
SListNode* BuySListNode(SLTDateType x);
// 單鏈表打印
void SListPrint(SListNode* plist);
// 單鏈表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 單鏈表的頭插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 單鏈表的尾刪
void SListPopBack(SListNode** pplist);
// 單鏈表頭刪
void SListPopFront(SListNode** pplist);
// 單鏈表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 單鏈表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 單鏈表刪除pos位置之后的值
void SListEraseAfter(SListNode* pos);

節點結構體創建

typedef int SLTDateType;
typedef struct SListNode
{
 SLTDateType data;
 struct SListNode* next; 
}SListNode;

節點開辟

對于鏈表來說，每需要空間就需要進行開辟，這里我們將之封裝成一個函數，便于后續調用直接使用（開辟的同時進行賦值）

參考代碼：

//鏈表節點開辟
SLTNode* BuySListNode(SLTDateType x)
{
	//動態分配一個節點
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		//分配失敗則打印錯誤信息并結束進程
		perror("newnode fail:");
		exit(-1);
	}
	//成功則進行賦值
	newnode->data = x;
	newnode->next = NULL;
	//返回節點地址，以便后續操作
	return newnode;
}

數據打印

注意：

1.對于不帶頭的鏈表來說，打印數據不需要修改鏈表首節點地址（故只要傳鏈表指針）

2.用循環遍歷鏈表，每打印數據，需要指向下一個節點

3.依靠尾節點的址域為NULL來結束循環

代碼：

//鏈表數據打印
void SListPrint(SLTNode* phead)//一級指針接收一級指針（打印不需改變指針本身內容）
{
	//創建一個尋址指針
	SLTNode* cur = phead;
	while (cur!=NULL)//后續還有節點
	{
		//打印數據并指向下一個節點
		printf("%d->", cur->data);
		cur = cur->next;
	}
	//最后打印空指針
	printf("NULL\n");
	return;
}

鏈表尾插數據

• 要尾插數據則需要遍歷找到鏈表的尾節點

• 對于不帶頭鏈表，尾插數據也可能是插在鏈表首元素的地址（當鏈表為空），需要修改鏈表指針的內容（故需要傳入鏈表指針的地址）

• 插入數據要開辟節點

代碼：

//鏈表尾插數據
void SListPushBack(SLTNode** pphead, SLTDateType x)//二級指針接收一級指針（尾插存在需改變鏈表指針本身內容）
{
	//避免傳入錯誤(直接報錯便于找到錯誤位置)
	assert(pphead);
	//接收新節點的地址
	SLTNode* newnode=BuySListNode(x);
	//頭節點為空
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾節點
		SLTNode* tail = *pphead;//創建尋址節點
		//兩個及以上節點的情況
		while (tail->next != NULL)
		{
			//指向下一個節點
			tail = tail->next;	
		}
		//找到了
		tail->next = newnode;
	}
	return;
}

注意代碼中的assert的作用：

• 正確傳入鏈表指針的地址是不會為空的

• 但是對于非正常傳入鏈表指針（不是鏈表指針的地址）且此時鏈表指針為空則會發生報錯（assert報錯會告訴錯誤位置），告訴程序員應該傳入鏈表指針的地址

頭刪

注意：

• 刪除前需要保存當前節點的址域（即保存下個節點的空間地址，以防丟失）

• 前刪數據即刪除當前鏈表首節點，即需修改鏈表指針的內容（故需傳入鏈表指針的地址）

• 刪除后修改鏈表指針內容，指向新的首節點

• 如果鏈表為空時無法刪除（保存下個節點地址會造成非法訪問）

代碼：

//鏈表前刪數據
void SListPopFront(SLTNode** pphead)
{
	//避免傳入錯誤(直接報錯便于找到錯誤位置)
	assert(pphead);
	//鏈表為空的情況
	if (*pphead == NULL)
	{
		return;
	}
	//創建指針保存第二個節點地址
	SLTNode* next = (*pphead)->next;
	//釋放當前頭結點空間
	free(*pphead);
	//更新頭結點數據
	*pphead = next;
	return;
}

鏈表數據查找

注意：

• 查找時用循環遍歷鏈表

• 對于查找數據不用修改鏈表指針的內容，故只需傳入鏈表指針就行了

• 查找到時則返回節點地址，否則返回NULL

代碼：

//鏈表數據查找
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
	//創建尋址指針
	SLTNode* cur = phead;
	while (cur!=NULL)
	{
		if (cur->data == x)//找到數據符合節點
		{
			return cur;//返回節點地址（好處：以便后續再尋找或修改）
		}
		else
		{
			//找下一個節點
			cur = cur->next;
		}
	}
	//未找到數據符合節點
	return NULL;
}

鏈表pos位置前插數據

注意：

• 想要pos位置前插數據，不僅需要找到pos位置，還需要記錄pos的前一個節點位置

• 傳入的pos為NULL則報錯

• 進行修改前節點的址域成新節點，并讓新節點的址域修改成pos，這才是一個成功的pos位置前插數據

• 循環遍歷鏈表查找pos位置，沒有找到pos位置則什么也不干

代碼：

//鏈表pos位置往前插入(較難)（還有在pos位置之后插入，簡單點）
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	//避免傳入錯誤(直接報錯便于找到錯誤位置)
	assert(pphead);
	assert(pos);
	SLTNode* newnode = BuySListNode(x);
	//首結點符合的情況
	if (*pphead == pos)
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}
	else
	{
		//創建尋址指針
		SLTNode* cur = *pphead;
		while (cur !=NULL)
		{
			if (cur->next!= pos)
			{
				cur = cur->next;//找到下一節點
			}
			else // 找到對應空間
			{
				cur->next = newnode;
				newnode->next = pos;
				return;//結束尋找（否則會一直插入，造成死循環）
			}
		}
	}
	//未找到則什么也不干
	return;
}

鏈表pos位置后插數據

注意：

• 后插則不用關注是否為首節點

• 也不用找到遍歷找到前節點的位置

• 后插則先將新節點址域改成pos后節點地址再將pos的址域改成新節點地址

ps:一定要注意修改鏈接節點址域的先后，避免地址的丟失

代碼：

//鏈表pos位置往后插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
	return;
}

鏈表pos位置數據刪除

注意：

• 考慮刪除首節點的情況，可能修改鏈表指針的內容，故需要傳入鏈表指針的地址

• 對于刪除節點，需要先保存pos位置下一個節點地址，將pos位置釋放，再將pos位置前節點的址域改成pos位置后節點的地址，這才是成功的刪除pos位置節點

• 循環找pos位置，沒找到則什么也不干

參考代碼:

//鏈表pos位置刪除
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	//避免傳入錯誤(直接報錯便于找到錯誤位置)
	assert(pphead);
	assert(pos);
	//頭結點符合的情況
	if (*pphead == pos)
	{
		*pphead = (*pphead)->next;
		free(pos);
	}
	else
	{
		//創建尋址指針
		SLTNode* cur = *pphead;
		while (cur != NULL)
		{
			if (cur->next != pos)
			{
				cur = cur->next;//找到下一節點
			}
			else // 找到對應空間
			{
				SLTNode* next = cur->next->next;
				free(cur->next);
				cur->next = next;
				return;//結束尋找
			}
		}
	}
	//未找到則什么也不干
	return;
}

鏈表節點釋放

注意:

• 對于動態開辟的內存空間，在使用后一定要記得的進行釋放（避免造成內存泄漏）

• 因為鏈表節點是一個個開辟的，同樣的釋放也需要一個個進行釋放

• 循環遍歷釋放當前節點前需保存后一個節點的地址，避免地址丟失無法釋放

• 釋放完后，還需將鏈表指針給置空（避免使用野指針）

參考代碼:

//鏈表節點釋放
void SListDestory(SLTNode** pphead)
{
	//避免傳入錯誤(直接報錯便于找到錯誤位置)
	assert(pphead);
	//遍歷釋放
	SLTNode* cur = *pphead;
	while (cur)
	{
		//保存下一個地址
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	//置空
	*pphead = NULL;
	return;
}

鏈表與順序表區別

鏈表的優缺點

優點

• 按需申請空間（空間使用合理）

• 插入效率高（不用像順序表樣挪動數據）

缺點

• 不支持隨機訪問（無法用下標直接訪問）

順序表的優缺點

優點

• 支持隨機訪問 (有些算法需要結構支持隨機訪問：二分查找，快排等)

缺點

• 擴容空間有消耗（空間碎片化以及空間浪費）

• 插入數據需要挪動數據有消耗

以上是“C++如何實現單鏈表”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！