手把手教你實現(xiàn)一個C++單鏈表

更新時間：2022年11月29日 16:31:05 作者：小林同志_____

鏈表是一種數(shù)據(jù)結(jié)構(gòu)，用于數(shù)據(jù)的存儲。這篇文章主要為大家介紹了如何實現(xiàn)一個C++單鏈表，文中的示例代碼講解詳細，感興趣的小伙伴可以嘗試一下

一. 節(jié)點聲明

鏈表是一種數(shù)據(jù)結(jié)構(gòu)，用于數(shù)據(jù)的存儲。

如圖，每一個鏈表節(jié)點所在的內(nèi)存空間是不延續(xù)的，因為不是連續(xù)存儲，所以需要存入下一個節(jié)點的地址，這樣方便找到下一個數(shù)值，而最后一個鏈表指向的空間為NULL，因此我們可以聲明一個結(jié)構(gòu)體，代表一個節(jié)點。

typedef int ListDataType;

typedef struct SListNode
{
	ListDataType  data;
	struct SListNode* Next;

}SLNode;

SListNode 是我們的節(jié)點結(jié)構(gòu)體，ListDataType是存儲數(shù)據(jù)的類型。

二. 尾插

鏈表的節(jié)點建立好后，接下來我們來進行尾部插入數(shù)據(jù)。

那么我們只需要找到尾部節(jié)點，把尾部節(jié)點指向的NULL值置為新節(jié)點。新節(jié)點指向NULL

因此我們要新建一個節(jié)點，然后找到最后一個節(jié)點。

void SListPushBack(SLNode** phead, ListDataType x)
{
	//新開辟一個節(jié)點
	SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
	if (newNode == NULL)
	{
		//空間開辟失敗
		printf("SListPushBack::newNode");
		exit(-1);
	}

	//找到最后一個節(jié)點
	SLNode* cru = *phead;
	//如果cru指向NULL，說明cru是最后一個節(jié)點
	while (cru->Next != NULL)
	{
		cru = cru->Next;
	}
	//cru 指向新節(jié)點
	cru->Next = newNode; 
	//新節(jié)點指向NULL，存儲數(shù)據(jù)x
	newNode->data = x;
	newNode->Next = NULL;

}

但是這種方法，我們需要注意一種情況，那就是如果鏈表中本身沒有節(jié)點，那么cru初始就是一個空指針，而循環(huán)條件我們對空指針進行了解引用，所以我們需要判斷一下。

//尾部數(shù)據(jù)插入
void SListPushBack(SLNode** phead, ListDataType x)
{
	//新開辟一個節(jié)點
	SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
	if (newNode == NULL)
	{
		//空間開辟失敗
		printf("SListPushBack::newNode");
		exit(-1);
	}

	//新節(jié)點指向NULL，存儲數(shù)據(jù)x
	newNode->data = x;
	newNode->Next = NULL;


	if (*phead == NULL)
	{
		//當前鏈表為空，那么我直接讓新節(jié)點替代phead
		*phead = newNode;
		return;
	}

	//找到最后一個節(jié)點
	SLNode* cru = *phead;

	//如果cru指向NULL，說明cru是最后一個節(jié)點
	while (cru->Next != NULL)
	{
		cru = cru->Next;
	}
	//cru 指向新節(jié)點
	cru->Next = newNode; 
	

}

然后我們測試一下，發(fā)現(xiàn)鏈表已經(jīng)鏈接起來了

三. 鏈表打印

為了方便后面測試，我們決定先實現(xiàn)打印鏈表的函數(shù)。我們只需要依次查找節(jié)點指向的元素，直到最后一個指向NULL時，我們停下來。

//鏈表打印
void SListPrint(SLNode* head)
{
	SLNode* cru = head;
	while (cru)
	{
		printf("%d->",cru->data);
		cru = cru->Next;
	}
	printf("NULL\n");
}

四. 頭插

頭部插入和尾部插入差不多，我們只需要把新節(jié)點指向鏈表中的第一個節(jié)點，然后把頭節(jié)點換成新節(jié)點。

因為我們尾插的時候創(chuàng)建了節(jié)點，頭插又創(chuàng)建節(jié)點，太麻煩了，所以我們把創(chuàng)建節(jié)點封裝成一個函數(shù)。

//創(chuàng)建節(jié)點
SLNode* SListCreateNode(ListDataType x)
{
	//新開辟一個節(jié)點
	SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
	if (newNode == NULL)
	{
		//空間開辟失敗
		printf("SListPushBack::newNode");
		exit(-1);
	}

	//新節(jié)點指向NULL，存儲數(shù)據(jù)x
	newNode->data = x;
	newNode->Next = NULL; 
	return newNode;
}

尾插函數(shù)調(diào)整

//尾部數(shù)據(jù)插入
void SListPushBack(SLNode** phead, ListDataType x)
{
	
	SLNode* newNode = SListCreateNode(x);

	if (*phead == NULL)
	{
		//當前鏈表為空，那么我直接讓新節(jié)點替代phead
		*phead = newNode;
		return;
	}

	//找到最后一個節(jié)點
	SLNode* cru = *phead;

	//如果cru指向NULL，說明cru是最后一個節(jié)點
	while (cru->Next != NULL)
	{
		cru = cru->Next;
	}
	//cru 指向新節(jié)點
	cru->Next = newNode; 
}

頭插函數(shù)

//頭部數(shù)據(jù)插入
void SListPushFront(SLNode** phead, ListDataType x)
{
	//新建節(jié)點
	SLNode* newNode = SListCreateNode(x);

	//讓節(jié)點指向頭
	newNode->Next = *phead;
	//頭節(jié)點更替為新節(jié)點
	*phead = newNode;
	
}

頭插測試

五. 尾刪

尾刪也就是刪除鏈表中的最后一個節(jié)點。那么我們需要找到最后一個節(jié)點，把它釋放，并且要把它的前一個節(jié)點置為空指針，否則它會變成一個野指針。

//尾部數(shù)據(jù)刪除
void SListPopBack(SLNode** phead)
{
	SLNode* cru = *phead; //最后一個節(jié)點
	SLNode* prve = NULL; //前一個節(jié)點

	//最后一個節(jié)點指向空
	while (cru->Next)
	{
		prve = cru;
		cru = cru->Next;
	}
	//cru 為最后一個節(jié)點。釋放掉
	free(cru);
	//前一個節(jié)點指向空
	prve->Next = NULL;

}

但是這個尾刪是建立在有數(shù)據(jù)的情況下的，如果沒有數(shù)據(jù)我們進行此操作，那會造成空指針prve訪問，所以我們在前面要斷言一下

void SListPopBack(SLNode** phead)
{
	//鏈表為空無法刪除
	assert(*phead);

	SLNode* cru = *phead; //最后一個節(jié)點
	SLNode* prve = NULL; //前一個節(jié)點

	//最后一個節(jié)點指向空
	while (cru->Next)
	{
		prve = cru;
		cru = cru->Next;
	}
	//cru 為最后一個節(jié)點。釋放掉
	free(cru);
	//前一個節(jié)點指向空
	prve->Next = NULL;

}

即使這樣，以上代碼依然有問題，因為當鏈表只有一個節(jié)點時，并不會進入while循環(huán)，也就導致 prve對空指針解引用，所以我們還需要判斷一下，如果鏈表只有一個節(jié)點，那么就直接釋放頭節(jié)點。

//尾部數(shù)據(jù)刪除
void SListPopBack(SLNode** phead)
{
	//鏈表為空無法刪除
	assert(*phead);

	//只有一個節(jié)點時
	if((*phead)->Next == NULL)
	{ 
		//釋放頭空間
		free(*phead);
		//置為空指針
		*phead = NULL;
		return;
	}

	SLNode* cru = *phead; //最后一個節(jié)點
	SLNode* prve = NULL; //前一個節(jié)點

	//找到最后一個節(jié)點
	while (cru->Next)
	{
		prve = cru;
		cru = cru->Next;
	}
	//cru 為最后一個節(jié)點。釋放掉
	free(cru);
	//前一個節(jié)點指向空
	prve->Next = NULL;
}

代碼測試

六. 頭刪

尾刪都會了，頭刪還遠嗎？頭刪我們只需要把頭節(jié)點指向的空間釋放，然后讓頭節(jié)點的指針指向下一個節(jié)點。

當然，如果鏈表為空，我們是無法操作的，我們也要斷言或者if判斷一下。

//頭部數(shù)據(jù)刪除
void SListPopFront(SLNode** phead)
{
	//斷言
	assert(*phead);

	//鏈表不為空，存儲下一個位置的地址
	SLNode* NextNode = (*phead)->Next;
	//釋放 *phead 
	free(*phead);
	//存儲的節(jié)點給*phead
	*phead = NextNode;
}

測試一下代碼

七. 查找值

在鏈表里查找值，我們只需要找節(jié)點，如果與找的值相等，就返回當前下標或者節(jié)點，這里我們用返回節(jié)點演示。

SLNode* SListFindNode(SLNode* head, ListDataType x)
{
	SLNode* cru = head;
	//查找值
	while (cru)
	{
		//如果當前節(jié)點等于要查找的值
		if (cru->data == x)
		{
			//返回當前節(jié)點，也可以返回下標，把函數(shù)返回值改成int
			return cru;
		}
		  //下一個節(jié)點
		cru = cru->Next;
	}

	//遍歷完沒有找到， 返回空指針
	return NULL;
}

看看測試結(jié)果

鏈表里我們插入了三個值，1，2，3。然后找1的值并返回當前節(jié)點，最終提示我們找到了。

當然，也可以用返回下標的方式，然后利用下標控制查找次數(shù)。

八.指定插入

指定插入，我們這里來演示前插，也就是在一個節(jié)點的前面進行插入，我們只需要把這個節(jié)點前面的節(jié)點指向新節(jié)點，然后新節(jié)點指向這個節(jié)點。

所以我們要先創(chuàng)建一個節(jié)點，讓被插入節(jié)點之前的節(jié)點指向該節(jié)點，讓新節(jié)點指向被插入的節(jié)點。

//指定插入
void SListInsert(SLNode** phead, SLNode* pos, ListDataType x)
{
	//首先插入之前，我們必須保證被插入的pos節(jié)點存在，不然無法插入
	assert(pos);
	
	SLNode* cru = *phead; //用來查找被插入的節(jié)點

	//查找pos節(jié)點
	while (cru->Next != pos)
	{
		cru = cru->Next;
	}

	//找到后，創(chuàng)建一個新節(jié)點
	SLNode* newNode = SListCreateNode(x);
	//新節(jié)點指向pos
	newNode->Next = pos;
	//pos的前一個節(jié)點指向cru
	cru->Next = newNode;
	

}

此時這個代碼仍有問題，因為如果 pos是第一個節(jié)點時，cru->next無法判斷判斷第一個節(jié)點，所以我們要加個判斷，如果是頭節(jié)點，直接調(diào)用頭插函數(shù)。

//指定插入
void SListInsert(SLNode** phead, SLNode* pos, ListDataType x)
{
	//首先插入之前，我們必須保證被插入的pos節(jié)點存在，不然無法插入
	assert(pos);

	//頭節(jié)點就是pos
	if (*phead == pos)
	{
		//調(diào)用頭插
		SListPushFront(phead,x);
		return 0;
	}
	
	SLNode* cru = *phead; //用來查找被插入的節(jié)點

	//查找pos節(jié)點
	while (cru->Next != pos)
	{
		cru = cru->Next;
	}

	//找到后，創(chuàng)建一個新節(jié)點
	SLNode* newNode = SListCreateNode(x);
	//新節(jié)點指向pos
	newNode->Next = pos;
	//pos的前一個節(jié)點指向cru
	cru->Next = newNode;
}

代碼測試

九.指定刪除

指定刪除和指定插入差不多，我們只需要把被刪除節(jié)點的前一個節(jié)點，指向后一個節(jié)點，然后刪除節(jié)點。如果要刪除的是頭節(jié)點，直接調(diào)用頭刪函數(shù)，或者也可以再次寫一個頭刪。

//指定節(jié)點刪除
void SListEase(SLNode** phead, SLNode* pos)
{
	//pos是空指針，干掉程序
	assert(pos);

	//如果頭節(jié)點與pos相等，直接調(diào)用頭刪
	if (*phead == pos)
	{
		SListPopFront(phead);
		return;
	}

	//創(chuàng)建一個節(jié)點
	SLNode* cru = *phead;  //查找被刪除節(jié)點的前一個節(jié)點
	while (cru->Next != pos)
	{
		cru = cru->Next;
	}
	
	//cru指向 pos 后的位置
	cru->Next = pos->Next;

	//釋放pos所在空間
	free(pos);
	pos = NULL;

}

代碼測試

十.銷毀鏈表

如果這個鏈表不想用了，我們想要清空鏈表。那我們只需要把依次釋放內(nèi)存。

//銷毀鏈表
void SListDestroy(SLNode** phead)
{
	SLNode* cru = NULL;

	while (*phead)
	{
		//存儲下一個節(jié)點的地址
		cru = (*phead)->Next;+
		//當前地址置空
		*phead = NULL;
		//釋放當前空間
		free(*phead);
		//換成下一個節(jié)點繼續(xù)
		*phead = cru;
	}

}

然后我們測試一下，發(fā)現(xiàn)所有的節(jié)點都置空了