前言

數(shù)據(jù)結(jié)構(gòu)入門 — 單鏈表詳解*
博客主頁(yè)鏈接：https://blog.csdn.net/m0_74014525
關(guān)注博主，后期持續(xù)更新系列文章
文章末尾有源碼
*****感謝觀看，希望對(duì)你有所幫助*****

系列文章

第一篇：數(shù)據(jù)結(jié)構(gòu)入門 — 鏈表詳解_單鏈表
第二篇：數(shù)據(jù)結(jié)構(gòu)入門 — 鏈表詳解_雙向鏈表
第三篇：數(shù)據(jù)結(jié)構(gòu)入門 — 鏈表詳解_循環(huán)鏈表

一、鏈表

1. 鏈表是什么

鏈表是一種數(shù)據(jù)結(jié)構(gòu)，由一系列節(jié)點(diǎn)組成，在每個(gè)節(jié)點(diǎn)中存儲(chǔ)數(shù)據(jù)和指向下一個(gè)節(jié)點(diǎn)的指針。每個(gè)節(jié)點(diǎn)只包含指向下一個(gè)節(jié)點(diǎn)的指針，不像數(shù)組那樣有預(yù)定義的大小。鏈表可以動(dòng)態(tài)地增長(zhǎng)和縮小，并且非常靈活，可以在任何位置插入或刪除節(jié)點(diǎn)。鏈表主要分為單向鏈表、雙向鏈表和循環(huán)鏈表等不同類型。

2. 優(yōu)缺點(diǎn)

鏈表的優(yōu)點(diǎn)：

1. 靈活性：由于鏈表中每個(gè)節(jié)點(diǎn)都有指向下一個(gè)節(jié)點(diǎn)的指針，因此鏈表可以在任何位置添加或移除元素，使得鏈表非常靈活。
2. 動(dòng)態(tài)性：由于鏈表的大小不是固定的，當(dāng)需要增加或刪除元素時(shí)，內(nèi)存中不需要重新分配空間，而是在鏈表中增加或刪除一個(gè)結(jié)點(diǎn)。
3. 無(wú)需占用連續(xù)的內(nèi)存空間：相較于數(shù)組等數(shù)據(jù)結(jié)構(gòu)，鏈表的每個(gè)元素之間并沒(méi)有關(guān)聯(lián)性，每個(gè)節(jié)點(diǎn)可以在內(nèi)存中的任意位置，不需要占用連續(xù)的內(nèi)存空間。

鏈表的缺點(diǎn)：

1. 沒(méi)有隨機(jī)訪問(wèn)的能力：鏈表中的元素之間沒(méi)有關(guān)聯(lián)性，無(wú)法像數(shù)組那樣通過(guò)下標(biāo)直接訪問(wèn)某個(gè)元素，需要從頭開始遍歷整個(gè)鏈表才能找到需要的元素，這會(huì)導(dǎo)致鏈表的查找效率比數(shù)組低。
2. 內(nèi)存空間的額外開銷：由于需要在每個(gè)節(jié)點(diǎn)中存儲(chǔ)指向下一個(gè)節(jié)點(diǎn)的指針，鏈表內(nèi)每個(gè)元素需要占用比其存儲(chǔ)內(nèi)容更多的內(nèi)存空間，這會(huì)導(dǎo)致鏈表沒(méi)有數(shù)組那么節(jié)省內(nèi)存。
3. 不支持常量時(shí)間內(nèi)的隨機(jī)訪問(wèn)：鏈表只能在頭尾節(jié)點(diǎn)進(jìn)行快速的插入和刪除操作，但在其他位置插入和刪除節(jié)點(diǎn)較為困難，需要先遍歷找到要操作的位置，這會(huì)導(dǎo)致鏈表操作的時(shí)間復(fù)雜度較高。

二、概念及結(jié)構(gòu)

1. 概念

鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表
中的指針鏈接次序?qū)崿F(xiàn)的。

2. 結(jié)構(gòu)

在現(xiàn)實(shí)的數(shù)據(jù)結(jié)構(gòu)中，鏈表的結(jié)構(gòu)

注意:

1. 從上圖可看出，鏈?zhǔn)浇Y(jié)構(gòu)在邏輯上是連續(xù)的，但是在物理上不一定連續(xù)
2. 現(xiàn)實(shí)中的結(jié)點(diǎn)一般都是從堆上申請(qǐng)出來(lái)的
3. 從堆上申請(qǐng)的空間，是按照一定的策略來(lái)分配的，兩次申請(qǐng)的空間可能連續(xù)，也可能不連續(xù)

三、 鏈表的分類

1. 鏈表結(jié)構(gòu)類型

鏈表可以分為單鏈表、雙向鏈表和循環(huán)鏈表三種類型。

除了這三種基本類型，還有一些派生的鏈表結(jié)構(gòu)，如帶有頭節(jié)點(diǎn)的鏈表、帶有尾指針的鏈表、帶有哨兵節(jié)點(diǎn)的鏈表等。如下圖有8種鏈表結(jié)構(gòu)
1. 單向或者雙向

2. 帶頭或者不帶頭（哨兵位）

3. 循環(huán)或者不循環(huán)

2. 常用的兩種鏈表結(jié)構(gòu)

無(wú)頭單向非循環(huán)鏈表：

無(wú)頭單向非循環(huán)鏈表：結(jié)構(gòu)簡(jiǎn)單，一般不會(huì)單獨(dú)用來(lái)存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)
構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。

帶頭雙向循環(huán)鏈表：

帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨(dú)存儲(chǔ)數(shù)據(jù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都
是帶頭雙向循環(huán)鏈表。另外這個(gè)結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實(shí)現(xiàn)以后會(huì)發(fā)現(xiàn)結(jié)構(gòu)會(huì)帶
來(lái)很多優(yōu)勢(shì)，實(shí)現(xiàn)反而簡(jiǎn)單了，后面我們代碼實(shí)現(xiàn)了就知道了。

四、單鏈表接口實(shí)現(xiàn)（代碼演示）

無(wú)頭+單向+非循環(huán)鏈表增刪查改實(shí)現(xiàn)

1. 動(dòng)態(tài)申請(qǐng)一個(gè)結(jié)點(diǎn)

SLTNode* BuySListNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("BuySListNode");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

2. 單鏈表打印

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

3. 單鏈表增刪查改

頭插：

//頭插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{

	assert(pphead);
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

尾插：

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType 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;
	}
}

頭刪：

//頭刪
void SLTPopFront(SLTNode** pphead)
{

	//空
	assert(pphead);
	assert(*pphead);
	//非空
	SLTNode* newnode = (*pphead)->next;
	free(*pphead);
	*pphead = newnode;

}

尾刪：

//尾刪
void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead);
	assert(pphead);

   //一個(gè)節(jié)點(diǎn)
	if((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;

	}
	else
	{
		SLTNode* tail = *pphead;
		SLTNode* tailPrev = NULL;
		while(tail->next != NULL)
		{
			tailPrev = tail;
			tail = tail->next;
		}

		free(tail);
		tail = NULL;
		tailPrev->next = NULL;
	}
}

查找：

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}

	return NULL;
}

在pos之前插入x：

// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{

	assert(pos);
	assert(pphead);
	if (pos == *pphead)
	{
		SLTPushFront(pphead,x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySListNode(x);

		prev->next = newnode;
		newnode->next = pos;

	}

}

在pos以后插入x：

// 在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
	
}

刪除pos位置：

// 刪除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pos);
	assert(pphead);
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != pos)
		{
			tail = tail->next;
		}
		tail->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

刪除pos的后一個(gè)位置：

// 刪除pos的后一個(gè)位置
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);

    SLTNode* posNext = pos->next;

	pos->next = posNext->next;

	pos->next = posNext->next;

	free(posNext);

	posNext = NULL;

}

4. 單鏈表銷毀

void Destory(SLTNode** pphead)
{
	assert(pphead);

	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* del = cur->next;

		free(cur);

		cur = del;
	}

	
	* pphead == NULL;
}

五、所有文件代碼

1. Gitee鏈接

***查看所有代碼***
點(diǎn)擊右邊藍(lán)色文字 DuckBro Gitee 代碼倉(cāng)庫(kù)

總結(jié)

單鏈表的重點(diǎn)包括：

1. 定義：?jiǎn)捂湵硎且环N數(shù)據(jù)結(jié)構(gòu)，它由一系列節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)和指向下一個(gè)節(jié)點(diǎn)的指針。
2. 插入操作：?jiǎn)捂湵淼牟迦氩僮餍枰日业揭迦胛恢玫那耙粋€(gè)節(jié)點(diǎn)，然后將新節(jié)點(diǎn)插入到其后。
3. 刪除操作：?jiǎn)捂湵淼膭h除操作需要先找到要?jiǎng)h除的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，然后將其指針指向下一個(gè)節(jié)點(diǎn)即可。
4. 遍歷操作：?jiǎn)捂湵硇枰獜念^節(jié)點(diǎn)開始依次遍歷各個(gè)節(jié)點(diǎn)，獲取其中存儲(chǔ)的數(shù)據(jù)。
5. 鏈表反轉(zhuǎn)：?jiǎn)捂湵淼姆崔D(zhuǎn)操作是將鏈表中的節(jié)點(diǎn)從后往前連接，最后將原來(lái)的頭節(jié)點(diǎn)變?yōu)槲补?jié)點(diǎn)。
6. 快慢指針：快慢指針是單鏈表中常用的技巧，可以用于查找鏈表中的中間節(jié)點(diǎn)、判斷是否有環(huán)等操作。
7. 環(huán)形鏈表：有些單鏈表可能存在環(huán)形結(jié)構(gòu)，即某個(gè)節(jié)點(diǎn)的指針指向之前的某個(gè)節(jié)點(diǎn)，使用快慢指針可以判斷鏈表是否為環(huán)形。
8. 鏈表排序：?jiǎn)捂湵砜梢允褂门判蛩惴ㄟM(jìn)行排序，如冒泡排序、快速排序等。
9. 鏈表的應(yīng)用：?jiǎn)捂湵韽V泛應(yīng)用于各種數(shù)據(jù)結(jié)構(gòu)和算法中，如哈希表、圖等。

如這篇博客對(duì)大家有幫助的話，希望 三連 支持一下 ?。?！ 如果有錯(cuò)誤感謝大佬的斧正 如有 其他見解發(fā)到評(píng)論區(qū)，一起學(xué)習(xí) 一起進(jìn)步。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-679644.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)入門 — 鏈表詳解_單鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！