C++如何實現(xiàn)單鏈表

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

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

概念和結(jié)構(gòu)

概念：鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)

數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈 接次序?qū)崿F(xiàn)的

圖示：

注意：

鏈表結(jié)構(gòu)在邏輯上為連續(xù)的，但是物理上（內(nèi)存中）不一定連續(xù)

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

結(jié)構(gòu)種類

鏈表具有多種結(jié)構(gòu)：單向\雙向，帶頭\不帶頭，循環(huán)\非循環(huán)

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

鏈表的實現(xiàn)

注意：這里實現(xiàn)的是無頭單向非循環(huán)鏈表

增刪查改接口

// 動態(tài)申請一個節(jié)點
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);

節(jié)點結(jié)構(gòu)體創(chuàng)建

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

節(jié)點開辟

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

參考代碼：

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

數(shù)據(jù)打印

注意：

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

2.用循環(huán)遍歷鏈表，每打印數(shù)據(jù)，需要指向下一個節(jié)點

3.依靠尾節(jié)點的址域為NULL來結(jié)束循環(huán)

代碼：

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

鏈表尾插數(shù)據(jù)

• 要尾插數(shù)據(jù)則需要遍歷找到鏈表的尾節(jié)點

• 對于不帶頭鏈表，尾插數(shù)據(jù)也可能是插在鏈表首元素的地址（當(dāng)鏈表為空），需要修改鏈表指針的內(nèi)容（故需要傳入鏈表指針的地址）

• 插入數(shù)據(jù)要開辟節(jié)點

代碼：

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

注意代碼中的assert的作用：

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

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

頭刪

注意：

• 刪除前需要保存當(dāng)前節(jié)點的址域（即保存下個節(jié)點的空間地址，以防丟失）

• 前刪數(shù)據(jù)即刪除當(dāng)前鏈表首節(jié)點，即需修改鏈表指針的內(nèi)容（故需傳入鏈表指針的地址）

• 刪除后修改鏈表指針內(nèi)容，指向新的首節(jié)點

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

代碼：

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

鏈表數(shù)據(jù)查找

注意：

• 查找時用循環(huán)遍歷鏈表

• 對于查找數(shù)據(jù)不用修改鏈表指針的內(nèi)容，故只需傳入鏈表指針就行了

• 查找到時則返回節(jié)點地址，否則返回NULL

代碼：

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

鏈表pos位置前插數(shù)據(jù)

注意：

• 想要pos位置前插數(shù)據(jù)，不僅需要找到pos位置，還需要記錄pos的前一個節(jié)點位置

• 傳入的pos為NULL則報錯

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

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

代碼：

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

鏈表pos位置后插數(shù)據(jù)

注意：

• 后插則不用關(guān)注是否為首節(jié)點

• 也不用找到遍歷找到前節(jié)點的位置

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

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

代碼：

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

鏈表pos位置數(shù)據(jù)刪除

注意：

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

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

• 循環(huán)找pos位置，沒找到則什么也不干

參考代碼:

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

鏈表節(jié)點釋放

注意:

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

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

• 循環(huán)遍歷釋放當(dāng)前節(jié)點前需保存后一個節(jié)點的地址，避免地址丟失無法釋放

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

參考代碼:

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

鏈表與順序表區(qū)別

鏈表的優(yōu)缺點

優(yōu)點

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

• 插入效率高（不用像順序表樣挪動數(shù)據(jù)）

缺點

• 不支持隨機訪問（無法用下標(biāo)直接訪問）

順序表的優(yōu)缺點

優(yōu)點

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

缺點

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

• 插入數(shù)據(jù)需要挪動數(shù)據(jù)有消耗

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