一：鏈表是什么
1、鏈表是物理存儲(chǔ)單元上非連續(xù)的、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表的指針地址實(shí)現(xiàn)，有一系列結(jié)點(diǎn)（地址）組成，結(jié)點(diǎn)可動(dòng)態(tài)的生成。
2、結(jié)點(diǎn)包括兩個(gè)部分：（1）存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域（內(nèi)存空間），（2）存儲(chǔ)指向下一個(gè)結(jié)點(diǎn)地址的指針域。
3、相對(duì)于線性表順序結(jié)構(gòu)，操作復(fù)雜。
4.鏈表分為 （1）單鏈表 （2）雙鏈表 （3）單向循環(huán)鏈表 （4）雙向循環(huán)鏈表
二：鏈表的作用
1、實(shí)現(xiàn)數(shù)據(jù)元素的存儲(chǔ)按一定順序儲(chǔ)存，允許在任意位置插入和刪除結(jié)點(diǎn)。
2、包括單向結(jié)點(diǎn)，雙向結(jié)點(diǎn)，循環(huán)接點(diǎn)
三：鏈表與數(shù)組的區(qū)別
說(shuō)到鏈表那肯定要聊一下數(shù)組，為什么會(huì)出現(xiàn)鏈表呢？
（1）數(shù)組：使用一塊連續(xù)的內(nèi)存空間地址去存放數(shù)據(jù)，但
例如：
int a[5]={1,2,3,4,5}。突然我想繼續(xù)加兩個(gè)數(shù)據(jù)進(jìn)去，但是已經(jīng)定義好的數(shù)組不能往后加，只能通過(guò)定義新的數(shù)組
int b[7]={1,2,3,4,5,6,7}; ***********這樣就相當(dāng)不方便比較浪費(fèi)內(nèi)存資源,對(duì)數(shù)據(jù)的增刪不好操作。
（2）鏈表：使用多個(gè)不連續(xù)的內(nèi)存空間去存儲(chǔ)數(shù)據(jù)， 可以 節(jié)省內(nèi)存資源（只有需要存儲(chǔ)數(shù)據(jù)時(shí)，才去劃分新的空間），對(duì)數(shù)據(jù)的增刪比較方便。
四、鏈表的優(yōu)缺
優(yōu)點(diǎn):
(1)插入和刪除速度快，保留原有的物理順序，在插入或者刪除一個(gè)元素的時(shí)候，只需要改變指針指向即可。(2)沒(méi)有空間限制,存儲(chǔ)元素?zé)o上限,只與內(nèi)存空間大小有關(guān)。(3)動(dòng)態(tài)分配內(nèi)存空間，不用事先開(kāi)辟內(nèi)存
缺點(diǎn)：
(1)占用額外的空間以存儲(chǔ)指針，比較浪費(fèi)空間，不連續(xù)存儲(chǔ)，malloc函數(shù)開(kāi)辟空間碎片比較多) (2) 查找速度比較慢，因?yàn)樵诓檎視r(shí)，只能順序查找，需要循環(huán)鏈表
五、關(guān)于頭指針，頭節(jié)點(diǎn)，首元節(jié)點(diǎn)的那些事
頭指針：指向鏈表第一個(gè)節(jié)點(diǎn)的指針（不一定是頭節(jié)點(diǎn)，因?yàn)?hellip;…鏈表要是沒(méi)有頭節(jié)點(diǎn)呢？），沒(méi)有實(shí)際開(kāi)辟空間 （即沒(méi)有用malloc等動(dòng)態(tài)分配內(nèi)存） 而且必須存在，因?yàn)轭^指針不存在，就不便于對(duì)鏈表進(jìn)行操作。
頭節(jié)點(diǎn)：不是必須存在（若存在則為鏈表的第一個(gè)節(jié)點(diǎn)）其主要作用是使所有鏈表（包括空表）的頭指針?lè)强眨⑹箤?duì)單鏈表的插入、刪除操作不需要區(qū)分是否為空表或是否在第一個(gè)位置進(jìn)行（還是挺有用的）。其數(shù)據(jù)域可以不儲(chǔ)存任何數(shù)據(jù)，若儲(chǔ)存則通常是鏈表的長(zhǎng)度啥的。
首元節(jié)點(diǎn)：第一個(gè)數(shù)據(jù)域中儲(chǔ)存有效數(shù)據(jù)的節(jié)點(diǎn) 若頭節(jié)點(diǎn)不存在 則其為鏈表的第一個(gè)節(jié)點(diǎn)，是一定要存在的（除非是空表）
有關(guān)鏈表的一些操作
1.單鏈表
節(jié)點(diǎn)結(jié)構(gòu)默認(rèn)為：
struct ListNode
{
int val;
struct ListNode *next;
}
①單鏈表的創(chuàng)建
//創(chuàng)建鏈表
struct ListNode* createList()
{
struct ListNode*p=NULL,*tail=NULL,*head=NULL;//p為待開(kāi)辟的節(jié)點(diǎn)指針,tail為指向鏈表尾部的指針,head為指向鏈表頭部的指針。
//筆者喜歡在創(chuàng)建鏈表時(shí) 創(chuàng)建head tail 兩個(gè)指針 雖然不一定都用得到
int num; //將指針置空是個(gè)好習(xí)慣
scanf("%d",&num);
//尾插法 順序插法
while(num!=-1)//假設(shè)以num/val值為-1作為鏈表的結(jié)束標(biāo)志 或者你用定長(zhǎng)條件也行
{
p=(struct ListNode*)malloc(sizeof(struct ListNode));//注意此處用sizeof計(jì)算大小時(shí)在ListNode前要加struct關(guān)鍵字
p->val=num;
p->next=NULL;
if(head==NULL)//第一次循環(huán)時(shí)將頭指針head指向p
{
head=p;
}
else
{
tail->next=p;
}
tail=p;//此句放else里面也行 筆者更喜歡在第一次循環(huán)時(shí)就將tail與p與head產(chǎn)生關(guān)聯(lián)
scanf("%d",&num);
}
// 頭插法 逆序插法
// while(num!=-1)
// {
// p=(struct ListNode*)malloc(sizeof(struct ListNode));
// p->val=num;
// if(head==NULL)
// {
// head=p;
// }
// else
// {
// p->next=head;
// head=p;
// }
// }
tail->next=NULL//用p->next也行 這是尾插法
return head;//返回鏈表頭指針
}
②鏈表節(jié)點(diǎn)的插入
struct ListNode *insertList(ListNode *head,int index,int num)//index 表示在鏈表中插入的位置（從1開(kāi)始）原位置的元素接在其后 num表示要插入的數(shù)值
{
struct ListNode *p=NULL,q;//在此q為虛擬節(jié)點(diǎn) 主要方便對(duì)鏈表進(jìn)行操作
int cnt=1;//計(jì)數(shù)器從1開(kāi)始計(jì)數(shù)
if(head==NULL&&head->next==NULL)//鏈表為空 返回一個(gè)空指針
return NULL;
if(index==1)//若插在頭結(jié)點(diǎn)(在此特指鏈表的第一個(gè)節(jié)點(diǎn))的位置
{
p=(struct ListNode*)malloc(sizeof(struct ListNode));//給p開(kāi)辟實(shí)際空間 用來(lái)儲(chǔ)存操作存入的值
p->val=num;
p->next=head;
head=p;
}
else
{
q=head;
while(q->next!=NULL&&cnt<=index)//對(duì)于鏈表我們通常對(duì)當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)進(jìn)行操作
{
if(cnt+1<index)//為什么要加一呢？因?yàn)楸硎鞠乱粋€(gè)位置
{
q=q->next;
}
else
{
p=(struct ListNode *)malloc(sizeof(struct ListNode));
p->val=num;
p->next=q->next;
q->next=q;
}
}
}
if(cnt<index)//如果cnt還是 小于 index 則表明插在鏈表末尾
{
p=(struct ListNode*)malloc(sizeof(struct ListNode));
p->val=num;
p->next=NULL;
q->next=p;
}
return head;
}
③鏈表節(jié)點(diǎn)的刪除
struct ListNode *deleteList(struct ListNode *head,int num)//執(zhí)行刪除節(jié)點(diǎn)val值為num的操作
{
struct ListNode *p=NULL,*q=NULL;//p，q均為輔助指針 不給他們開(kāi)辟實(shí)際空間
if(head->val==num)//若刪除節(jié)點(diǎn)為頭結(jié)點(diǎn)
{
p=head;
head=head->next;
free(p);
}
else//若刪除節(jié)點(diǎn)為除頭結(jié)點(diǎn)外的其他節(jié)點(diǎn)
{
p=head;
while(p->next!=NULL)
{
if(p->next->val==num)
{
q=p->next;
p->next=p->next->next;
free(q);
}
else
{
p=p->next;
}
}
}
return head;
}
鏈表的遍歷
void printList(struct ListNode *head)
{
struct ListNode *p=head;//p依然為輔助指針
while(p!=NULL)//因?yàn)槭潜闅v（打印輸出）操作 所以對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行操作即可
{
printf("%d",p->val);
p=p->next;
}
}
雙向鏈表
雙向鏈表即單鏈表由單向的鏈變成了雙向的鏈（一個(gè)指針域(next)變成一前一后兩個(gè)指針域(prev,next)） 這里只演示雙向鏈表的創(chuàng)建
另：
節(jié)點(diǎn)結(jié)構(gòu)為：
struct ListNode
{
int val;
ListNode *prev;
ListNode *next;
};
雙向鏈表的創(chuàng)建
struct ListNode *createDbList()
{
struct ListNode*p=NULL,*head=NULL,*tail=NULL;
int num;
scanf("%d",&num);
while(num!=-1)//以-1作為創(chuàng)建鏈表結(jié)束的標(biāo)志
{
p=(struct ListNode*)malloc(sizeof(struct ListNode));
p->val=num;
if(head==NULL)//這里主要演示尾插法
{
head=p;
p->prev=NULL; //就不將雙向鏈表和循環(huán)鏈表相互摻和了
}
else
{
tail->next=p;
p->prev=tail;
}
tail=p;
}
tail->next=NULL;
}
循環(huán)鏈表
即將鏈表首尾相接 同樣這里只演示循環(huán)鏈表的創(chuàng)建
struct ListNode *createList()
{
struct ListNode*p,*head,*tail;
int num;
scanf("%d",&num);
while(num!=-1)
{
p=(struct ListNode*)malloc(sizeof(struct ListNode));
p->val=num;
if(head==NULL)
{
head=p;
}
else
{
tail->next=p;
}
tail=p;
}
tail->next=head;//創(chuàng)建結(jié)束后將鏈表首尾相接
}
靜態(tài)鏈表
靜態(tài)鏈表的節(jié)點(diǎn)通常用結(jié)構(gòu)體數(shù)組表示
struct staticListNode
{
int val;
int cur;//游標(biāo)cur用來(lái)儲(chǔ)存后繼節(jié)點(diǎn)的下標(biāo)
};
1.Floyd判圈法：判斷鏈表是否有環(huán)（快慢指針的應(yīng)用）
對(duì)于鏈表找環(huán)路的問(wèn)題，有一個(gè)通用的解法——快慢指針(Floyd) 。給定兩個(gè)指針， 分別命名為 slow 和 fast ，起始位置在鏈表的開(kāi)頭。每次 fast 前進(jìn)兩步， slow 前進(jìn)一步。如果 fast 可以走到盡頭，那么說(shuō)明沒(méi)有環(huán)路；如果fast 可以無(wú)限走下去，那么說(shuō)明一定有環(huán)路，且一定存 在一個(gè)時(shí)刻 slow 和 fast 相遇。當(dāng) slow 和 fast 第一次相遇時(shí)，我們將 fast 重新移動(dòng)到鏈表開(kāi)頭，并 讓 slow 和 fast 每次都前進(jìn)一步。當(dāng) slow 和 fast 第二次相遇時(shí)，相遇的節(jié)點(diǎn)即為環(huán)路的開(kāi)始點(diǎn)。
2. 判斷兩個(gè)鏈表是否相交
假設(shè)鏈表 A 的頭節(jié)點(diǎn)到相交點(diǎn)的距離是 a，鏈表 B 的頭節(jié)點(diǎn)到相交點(diǎn)的距離是 b，相交點(diǎn)到鏈表終點(diǎn)的距離為 c。我們使用兩個(gè)指針，分別指向兩個(gè)鏈表的頭節(jié)點(diǎn)，并以相同的速度前進(jìn)，若到達(dá)鏈表結(jié)尾，則移動(dòng)到另一條鏈表的頭節(jié)點(diǎn)繼續(xù)前進(jìn)。按照這種前進(jìn)方法，兩個(gè)指針會(huì)在a + b + c 次前進(jìn)后同時(shí)到達(dá)相交節(jié)點(diǎn)
————————————————
版權(quán)聲明：本文為CSDN博主「legendarykk」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請(qǐng)附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.NET/legendarykk/article/details/125592024
