數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)分享之單鏈表詳解

這篇具有很好參考價(jià)值的文章主要介紹了數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)分享之單鏈表詳解。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。

1. 前言

? ? ??博主CSDN:杭電碼農(nóng)-NEO????????
?
? ? ?專欄分類(lèi):數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)分享(持續(xù)更新中??)???????
?
? 讓我們緊接上一章順序表的概念,引出鏈表,我們說(shuō)順序表每次增容需要申請(qǐng)新的空間,會(huì)產(chǎn)生很多空間碎片,代價(jià)比較高,并且我們擴(kuò)容一般是擴(kuò)兩倍,還是會(huì)有一些空間被我們浪費(fèi)掉. 所以我們基于順序表的缺點(diǎn),引出了鏈表的概念

2. 鏈表的概念以及結(jié)構(gòu)

概念:鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。我們光聽(tīng)這個(gè)概念可能有一點(diǎn)抽象,所以我們以畫(huà)圖的形式給大家說(shuō)明一下;

數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)分享之單鏈表詳解

我們畫(huà)的圖是形象圖,但是實(shí)際上我們鏈表沒(méi)有箭頭這一說(shuō)法,箭頭只是幫助大家理解它的結(jié)構(gòu),其實(shí)它的真實(shí)存儲(chǔ)結(jié)構(gòu)應(yīng)該是這樣的: ????

數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)分享之單鏈表詳解注意:

在上圖中我們可以發(fā)現(xiàn)鏈?zhǔn)浇Y(jié)構(gòu)在邏輯上是連續(xù)的(即一個(gè)節(jié)點(diǎn)鏈接著一個(gè)節(jié)點(diǎn)),但是在物理上不一定連續(xù)(即地址不連續(xù),節(jié)點(diǎn)1為A0,節(jié)點(diǎn)2為B0) ????

實(shí)際存儲(chǔ)中的節(jié)點(diǎn)是從堆上申請(qǐng)出來(lái)的,在堆上申請(qǐng)的空間是按照一定的策略來(lái)分配的,兩次手球的空間可能連續(xù)也可能不連續(xù) ????

3. 鏈表的分類(lèi)

? 實(shí)際中鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來(lái)就有8種鏈表結(jié)構(gòu) ?

單向或者雙向:

帶頭或者不帶頭(也叫做哨兵位):

循環(huán)或非循環(huán):

數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)分享之單鏈表詳解

雖然有這么多的鏈表的結(jié)構(gòu)，但是我們實(shí)際中最常用還是兩種結(jié)構(gòu)：

數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)分享之單鏈表詳解

無(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)鏈表：結(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)了就知道了??。

我們本節(jié)要介紹的就是無(wú)頭單向非循環(huán)鏈表 ??????

4.鏈表的實(shí)現(xiàn)

4.1 初始化結(jié)構(gòu)

和順序表一樣,在我們實(shí)現(xiàn)增刪查改等功能之前,我們要先在.h文件中包含常見(jiàn)的頭文件并且定義一個(gè)結(jié)構(gòu)體后將它重命名:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDateType;//想存儲(chǔ)字符型就把int改成char
typedef struct SlistNode
{
	SLTDateType data;//鏈表節(jié)點(diǎn)中存儲(chǔ)的數(shù)據(jù)
	struct SlistNode* next;//節(jié)點(diǎn)中存儲(chǔ)的下一個(gè)節(jié)點(diǎn)的地址
}SLTNode;

然后在在我們的test.c文件和Slist.c文件中包含Slist.h.不同于順序表的是我們這里在test.c文件中定義一個(gè)plist結(jié)構(gòu)體指針就可以直接開(kāi)始使用了.我們接下來(lái)先在.h文件中將我們所有的函數(shù)都聲明一遍:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDateType;
typedef struct SlistNode
{
	SLTDateType data;
	struct SlistNode* next;
}SLTNode;

void SListPrint(SLTNode** phead);//打印鏈表元素

SLTNode* BuyListNode(SLTDateType x);//開(kāi)辟空間

void SListPushBack(SLTNode** phead, SLTDateType x);//尾插

void SListPopBack(SLTNode** phead);//尾刪

void SListPushFront(SLTNode** phead, SLTDateType x);//頭插

void SListPopFront(SLTNode** phead);//頭刪

SLTNode* SListFind(SLTNode* phead, SLTDateType x);//查找

void SListInsert(SLTNode** phead, SLTNode* pos, SLTDateType x);//在pos位置前插入數(shù)據(jù)

??????

我們發(fā)現(xiàn)這里的增刪查改都是傳的二級(jí)指針,這是因?yàn)槲覀冊(cè)趖est.c中定義結(jié)構(gòu)體變量時(shí)定義的是一個(gè)結(jié)構(gòu)體指針指向我們鏈表的第一個(gè)節(jié)點(diǎn),我們?cè)谶M(jìn)行增刪查改的過(guò)程中可以會(huì)改變這個(gè)結(jié)構(gòu)體指針的指向(比如頭插后,我們的結(jié)構(gòu)體指針指向新的鏈表的頭),所以我們需要傳二級(jí)指針過(guò)去才能改變它的值.如果聽(tīng)到這兒你還不明白,可以先去我的碼云看看所有的代碼再慢慢理解gitee-杭電碼農(nóng)

4.2 尾插函數(shù)

既然是要插入數(shù)據(jù),那么與數(shù)組不同的是鏈表每插入一次數(shù)據(jù)就開(kāi)辟一塊與這個(gè)數(shù)據(jù)大小相同的空間,所以我們第一步要做的就是動(dòng)態(tài)開(kāi)辟空間:

void SListPushBack(SLTNode** phead, SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//定義一個(gè)新節(jié)點(diǎn)后動(dòng)態(tài)開(kāi)辟空間
	newnode->data = x;//將要插入的數(shù)據(jù)x賦值到節(jié)點(diǎn)的data上
	newnode->next = NULL;//將尾插后的節(jié)點(diǎn)的next置空.
}

當(dāng)我們開(kāi)辟好空間之后,我們得先找到尾,才能尾插,所以我們這里定義一個(gè)變量取遍歷鏈表來(lái)找到尾:

void SListPushBack(SLTNode** phead, SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//定義一個(gè)新節(jié)點(diǎn)后動(dòng)態(tài)開(kāi)辟空間
	newnode->data = x;//將要插入的數(shù)據(jù)x賦值到節(jié)點(diǎn)的data上
	newnode->next = NULL;//將尾插后的節(jié)點(diǎn)的next置空.

    SLTNode* cur = *phead; //定義一個(gè)變量指向鏈表得頭節(jié)點(diǎn)
    while (cur->next!=NULL)//當(dāng)cur->next等于NULL時(shí),此時(shí)cur就是最后一個(gè)節(jié)點(diǎn)
	   {
		  cur = cur->next;//cur不斷往后遍歷
	   }
	   cur->next = newnode;//這時(shí)cur已經(jīng)等于最后一個(gè)節(jié)點(diǎn)后出了while循環(huán),將最后一個(gè)節(jié)點(diǎn)與新節(jié)點(diǎn)鏈接起來(lái)
}

值得注意的是這里有一種特殊情況,就當(dāng)整個(gè)鏈表沒(méi)有存儲(chǔ)數(shù)據(jù)時(shí),我們得phead為空指針,cur也是空指針,然后我們使用了cur->next相當(dāng)于對(duì)空指針解引用了,所以這個(gè)地方得特殊情況要特殊考慮,優(yōu)化代碼后為:

void SListPushBack(SLTNode** phead, SLTDateType x)
{
    assert(*phead);//確保鏈表不為空
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = NULL;
	if (*phead == NULL)
	{
		*phead = newnode;//當(dāng)鏈表為空時(shí)直接將phead給給newnode
	}
	else
	{
	   SLTNode* cur = *phead; 
       while (cur->next)
	   {
		cur = cur->next;
	   }
	   cur->next = newnode;
	}
}

4.3 尾刪函數(shù)

和尾插類(lèi)型,先找到尾再把尾節(jié)點(diǎn)的空間給釋放掉,然后將尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的next置空使它變成新的尾節(jié)點(diǎn):

void SListPopBack(SLTNode** phead)
{
		SLTNode* cur = *phead;
		SLTNode* prev = NULL;//定義一個(gè)prev指向cur的前一個(gè)結(jié)點(diǎn)
		while (cur->next!=NULL)//當(dāng)cur->next為空時(shí)就代表cur是尾節(jié)點(diǎn)了,此時(shí)prev是尾節(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
		{
			prev = cur;//prev是cur結(jié)點(diǎn)的前面一個(gè)結(jié)點(diǎn)
			cur = cur->next;
		}
		prev->next = NULL;//將prev結(jié)點(diǎn)置空成為新的尾
		free(cur);//將要尾刪的空間給釋放掉
		cur = NULL;
}

還是和之前同一個(gè)問(wèn)題,當(dāng)我們鏈表中只有一個(gè)節(jié)點(diǎn)時(shí),我們的prev還是NULL,后面講prev->=NULL,也是對(duì)空指針解引用,也會(huì)遇見(jiàn)對(duì)空指針解引用的錯(cuò)誤操作,所以這個(gè)地方我們優(yōu)化代碼:

void SListPopBack(SLTNode** phead)
{
	if ((*phead)->next == NULL)
	{
		free(*phead);//當(dāng)鏈表中只有一個(gè)節(jié)點(diǎn)時(shí),直接free掉就行
		*phead = NULL;
	}
	else
	{
		SLTNode* cur = *phead;
		SLTNode* prev = NULL;
		while (cur->next)
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = NULL;
		free(cur);
		cur = NULL;
	}
}

4.4 頭插函數(shù)

有了前面尾插,尾刪的基礎(chǔ),這里我們直接上代碼:

void SListPushFront(SLTNode** phead, SLTDateType x)
{

	SLTNode* newhead = (SLTNode*)malloc(sizeof(SLTNode));//只要是插入數(shù)據(jù)就要開(kāi)辟新空間
	newhead->next = *phead;
	newhead->data = x;
	*phead = newhead;//把新的頭給phead
}

4.5 頭刪函數(shù)

這里頭部的刪除要考慮鏈表中是否還存在節(jié)點(diǎn),并且鏈表中只有一個(gè)節(jié)點(diǎn)的情況也要拿出來(lái)特殊考慮

void SListPopFront(SLTNode** phead)
{
	assert(*phead);//確保鏈表不為空
	if ((*phead)->next == NULL)//鏈表只有一個(gè)節(jié)點(diǎn)
	{
		free(*phead);//直接釋放掉空間后置空
		*phead = NULL;
	}
	else
	{
		SLTNode* newhead = (*phead)->next;//定義頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn),不然把頭節(jié)點(diǎn)的空間釋放掉后會(huì)找不到下一個(gè)節(jié)點(diǎn)
		free(*phead);
		*phead = newhead;//把phead給上新的頭節(jié)點(diǎn)
	}
}

4.6 開(kāi)辟新節(jié)點(diǎn)

我們發(fā)現(xiàn),在操作鏈表時(shí),只要涉及到插入數(shù)據(jù)就會(huì)用到開(kāi)辟動(dòng)態(tài)內(nèi)存這一個(gè)步驟,所以我們可以把這個(gè)步驟單獨(dú)拿出來(lái),遇見(jiàn)頭插尾插時(shí)可以在函數(shù)中調(diào)用這個(gè)開(kāi)辟空間的函數(shù):

SLTNode* BuyListNode(SLTDateType x)//返回一個(gè)節(jié)點(diǎn)的地址
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;//將插入的數(shù)據(jù)給上
	newnode->next = NULL;
	return newnode;//將開(kāi)辟好后的空間返回
}

當(dāng)我們寫(xiě)了這個(gè)函數(shù)過(guò)后,我們的頭插和尾插就可以簡(jiǎn)化一點(diǎn)了??????
比如我們的尾插可以改為:

void SListPushBack(SLTNode** phead, SLTDateType x)
{
    assert(*phead);//確保鏈表不為空
	SLTNode* newnode = BuyListNode(SLTDateType x);//定義一個(gè)節(jié)點(diǎn)來(lái)接受開(kāi)辟的空間
	if (*phead == NULL)
	{
		*phead = newnode;//當(dāng)鏈表為空時(shí)直接將phead給給newnode
	}
	else
	{
	   SLTNode* cur = *phead; 
       while (cur->next)
	   {
		cur = cur->next;
	   }
	   cur->next = newnode;
	}
}

4.7 銷(xiāo)毀鏈表

當(dāng)我們使用完鏈表后,需要銷(xiāo)毀它里面的數(shù)據(jù)和空間:

void SListDestroy(SLTNode** phead)
{
	assert(phead);
	SLTNode* cur = *phead;
	while(cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*phead = NULL;
}

5. 單鏈表OJ題目

在我的專欄單鏈表面試題分享中其實(shí)就給大家分享了很多個(gè)單鏈表面試題的題解思路以及一些衍生問(wèn)題的探討,有興趣的同學(xué)可以點(diǎn)擊前面跳轉(zhuǎn).或者如果你想自己做一遍題不想先看答案的,我給大家把這些題的鏈接放出來(lái) :

? ?????????

刪除鏈表中等于給定值 val 的所有節(jié)點(diǎn)。OJ題

反轉(zhuǎn)一個(gè)單鏈表.OJ題

給定一個(gè)帶有頭結(jié)點(diǎn) head 的非空單鏈表，返回鏈表的中間結(jié)點(diǎn)。如果有兩個(gè)中間結(jié)點(diǎn)，則返回第二個(gè)
中間結(jié)點(diǎn)。OJ題

輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)OJ題

將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回。新鏈表是通過(guò)拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成
的。OJ題

鏈表的回文結(jié)構(gòu)。OJ題

輸入兩個(gè)鏈表，找出它們的第一個(gè)公共結(jié)點(diǎn)。OJ題

給定一個(gè)鏈表，判斷鏈表中是否有環(huán)。OJ題

給定一個(gè)鏈表，返回鏈表開(kāi)始入環(huán)的第一個(gè)節(jié)點(diǎn)。如果鏈表無(wú)環(huán)，則返回 NULLOJ題

給定一個(gè)鏈表，每個(gè)節(jié)點(diǎn)包含一個(gè)額外增加的隨機(jī)指針，該指針可以指向鏈表中的任何節(jié)點(diǎn)或空節(jié)點(diǎn)。
要求返回這個(gè)鏈表的深度拷貝。OJ題

在我往期的博客當(dāng)中有這些題目的畫(huà)圖詳解,當(dāng)你們做題時(shí)遇見(jiàn)問(wèn)題可以跳轉(zhuǎn)我的專欄單鏈表面試題分享

6. 順序表和鏈表的區(qū)別

我們用一個(gè)表格來(lái)闡述:

不同點(diǎn)	順序表	鏈表
存儲(chǔ)空間上	物理上一定連續(xù)	邏輯上一定連續(xù),物理上不一定
隨機(jī)訪問(wèn)	支持O(1)	O(N)
任一位置插入或刪除	需要挪動(dòng)元素,效率低	只需要修改指針指向
插入	動(dòng)態(tài)順序表,空間不夠需擴(kuò)容	沒(méi)有容量的概念
應(yīng)用場(chǎng)景	元素高效存儲(chǔ)和快速訪問(wèn)	頻繁的任一位置插入或刪除
緩存利用率	高	低

后期遇見(jiàn)既可以用順序表作為結(jié)構(gòu)也可以用鏈表作為結(jié)構(gòu)的數(shù)據(jù)時(shí),再詳細(xì)討論到底用哪個(gè)好

7. 總結(jié)

鏈表是為了彌補(bǔ)順序表的缺陷而出現(xiàn)的一種數(shù)據(jù)結(jié)構(gòu),當(dāng)然鏈表本身也有缺陷,它不能解決所有問(wèn)題,所以我們后期還會(huì)學(xué)一些數(shù)據(jù)結(jié)構(gòu)來(lái)完善我們對(duì)于結(jié)構(gòu)的理解有關(guān)于鏈表中最簡(jiǎn)單的結(jié)構(gòu):單鏈表的實(shí)現(xiàn)我們就講到這里,如果有幫到你請(qǐng)點(diǎn)點(diǎn)贊吧.??????

?? 我的碼云:gitee-杭電碼農(nóng)-NEO??文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-430678.html

?? 下期預(yù)告:雙向帶頭循環(huán)鏈表 ??

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