第C語言深入講解鏈表的使用目錄一、鏈表的概念二、鏈表的分類1.單向或者雙向鏈表2.帶頭或者不帶頭(是否有自帶哨兵位頭結點)3.循環或者非循環鏈表4.無頭單向非循環鏈表和帶頭雙向循環鏈表3、鏈表的實現(代碼和注釋)4、鏈表oj題(小試牛刀)總結現實生活中的火車就像一個完整的鏈表，現在我們來深入理解一下鏈表這個數據結構。

一、鏈表的概念

概念：鏈表是一種物理存儲結構上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。

注：

1、從上圖中可看出，鏈式結構在邏輯上是連續的，但是在物理上不一定連續。

2、從現實中的結點一般是通過malloc函數申請的，所以其內存分配是在堆區。

3、從堆上申請的空間，是按照一定的策略來分配的，則一個節點的大小為8個字節。

二、鏈表的分類

實際中鏈表的結構非常多樣，以下情況組合起來就有8種鏈表結構：

1.單向或者雙向鏈表

2.帶頭或者不帶頭(是否有自帶哨兵位頭結點)

第二個鏈表的d1指向了我們的哨兵位頭結點。

3.循環或者非循環鏈表

4.無頭單向非循環鏈表和帶頭雙向循環鏈表

1.無頭單向非循環鏈表：結構簡單，一般不會單獨用來存數據。實際中更多是作為其他數據結構的子結構，如哈希桶、圖的鄰接表等等。另外這種結構在筆試面試中出現很多。

2.帶頭雙向循環鏈表：結構最復雜，一般用在單獨存儲數據。實際中使用的鏈表數據結構，都是帶頭雙向循環鏈表。另外這個結構雖然結構復雜，但是使用代碼實現以后會發現結構會帶來很多優勢，實現反而簡單了。

3、鏈表的實現(代碼和注釋)

無頭+單向+非循環鏈表增刪查改實現

頭文件：

#pragmaonce

#includestdio.h

#includestdlib.h

#includeassert.h

//要求存儲的數據從0開始，依次存儲

//靜態的順序表

//問題：開小了，不夠用，開大了，存在浪費。

//structSeqList

//inta[N];

//intsize;//記錄存儲了多少個數據。

typedefintSLDateType;//宏定義我們的SLDateType是int類型的

//動態的順序表

typedefstructSeqList

SLDateType*a;

intsize;//存儲數據個數

intcapacity;//存儲空間大小

}SL,SeqList;

voidSeqListPrint(SeqList*psl);//鏈表的打印

voidSeqListInit(SeqList*psl);//鏈表的初始化

voidSeqListDestroy(SeqList*psl);//鏈表的銷毀

voidSeqListCheckCapacity(SeqList*psl);//檢查內存空間是否足夠

//時間復雜度是o(1)

voidSeqListPushBack(SeqList*psl,SLDateTypex);//鏈表的尾插

voidSeqListPopBack(SeqList*psl);//鏈表的尾刪

//時間復雜度是o(n)

voidSeqListPushFront(SeqList*psl,SLDateTypex);//鏈表的頭插

voidSeqListPopFront(SeqList*psl);//鏈表的頭刪

voidSeqListInsert(SeqList*psl,size_tpos,SLDateTypex);

//刪除pos位置的數據

voidSeqListErase(SeqList*psl,size_tpos);

//順序表查找

intSeqListFind(SeqList*psl,SLDateTypex);

鏈表的函數實現部分的代碼：

#include"SeqList.h"

#includeassert.h

voidSeqListPrint(SeqList*psl)//結構體指針傳參

for(inti=0;ipsl-size;++i)

printf("%d",psl-a[i]);

printf("\n");

voidSeqListInit(SeqList*psl)

assert(psl);//斷言psl不為空

psl-a=NULL;//a就相當于是鏈表的頭

psl-size=0;

psl-capacity=0;

voidSeqListDestroy(SeqList*psl)//鏈表的刪除

assert(psl);

free(psl-//free掉鏈表中a這個節點的位置

psl-a=NULL;//將a指向空

psl-capacity=psl-size=0;//將鏈表的內存大小置為0

voidSeqListCheckCapacity(SeqList*psl)//檢查鏈表的內存，如果不夠就增容。

assert(psl);

if(psl-size==psl-capacity)

//capacity==0,所以要先特判一下capacity的值

size_tnewCapacity=psl-capacity==04:psl-capacity*2;//初始節點數為4，如果內存現在為0就擴大一倍

SLDateType*tmp=realloc(psl-a,sizeof(SLDateType)*newCapacity);//申請空間

if(tmp==NULL)

printf("reallocfail\n");

exit(-1);

else

psl-a=tmp;

psl-capacity=newCapacity;//原來的空間變為新空間

voidSeqListPushBack(SeqList*psl,SLDateTypex)

//如果滿了，要擴容

if(psl-size==psl-capacity)

//capacity==0,所以要先特判一下capacity的值

size_tnewCapacity=psl-capacity==04:psl-capacity*2;

SLDateType*tmp=realloc(psl-a,sizeof(SLDateType)*newCapacity);

if(tmp==NULL)

printf("reallocfail\n");

exit(-1);

else

psl-a=tmp;

psl-capacity=newCapacity;

psl-a[psl-size]=x;

psl-size++;

voidSeqListPopBack(SeqList*psl)

assert(psl);

if(psl-size0)

psl-size--;//尾刪就size--就好了

voidSeqListPushFront(SeqList*psl,SLDateTypex)

assert(psl);

SeqListCheckCapacity(psl);

intend=psl-size-1;

while(end=0)//所有的數據往后挪1位

psl-a[end+1]=psl-a[end];

--end;

psl-a[0]=x;//兩種操作是等價的

psl-size++;

//SeqListInsert(psl,0,x);在頭部插入。

voidSeqListPopFront(SeqList*psl)

assert(psl);

if(psl-size0)

intbegin=1;

while(psl-sizebegin)

psl-a[begin-1]=psl-a[begin];

++begin;

--psl-size;

voidSeqListInsert(SeqList*psl,size_tpos,SLDateTypex)

//暴力檢查

assert(psl);

//溫和檢查

if(pospsl-size)

printf("pos越界：%d\n",pos);

return;

//exit(-1);

//暴力檢查

//assert(pos=psl-size);

SeqListCheckCapacity(psl);

//intend=psl-size-1;

//while(end=(int)pos)

//psl-a[end+1]=psl-a[end];

//--end;

size_tend=psl-size;

while(endpos)

psl-a[end]=psl-a[end-1];

--end;

psl-a[pos]=x;

psl-size++;

}

4、鏈表oj題(小試牛刀)

1、leetcode203移除鏈表元素力扣

包含三種情況

畫個圖分析：

思路：情況一和情況二都可以用prev和cur指針遍歷數組的兩個元素，ifcur指針不等于6，prev指針和cur指針都往前走，如果cur=6，prev跳到cur的下一個位置

如果是第三種情況，則需先找到head!=val的位置，再重復進行如上操作。

代碼示例：

structListNode*removeElements(structListNode*head,intval)

structListNode*prev=NULL;

structListNode*cur=head;

while(cur)

if(cur-val!=val)//當cur這個位置的值不等于val時往下走

prev=cur;//prev跳到cur位置

cur=cur-next;//cur指針繼續往下走

else

structListNode*next=cur-next;//定義一個新的指針

if(prev==NULL)//頭刪，head為空的狀態

free(cur);

head=next;//繼續往后面走

cur=next;

else

free(cur);//free掉cur這個節點

prev-next=next;//跳過了cur這個點

cur=next;//cur繼續往后走

returnhead;

}

2、leetcode206反轉鏈表力扣

思路1：反轉指針方向

思路二：用三個指針，n1,n2,n3分別存放NULL,head,head-next;

代碼示例：

structListNode*reverseList(structListNode*head)

if(head==NULL)returnNULL;

structListNode*n1,*n2,*n3;

n1=NULL;

n2=head;

n3=n2-next;//n3的地址是n2的下一位

while(n2)

n2-next=n1;//n2的下一位指向n1;起到掉頭的作用

n1=n2;

n2=n3;

if(n3)

n3=n3-next;

returnn1;

}

方法2：頭插法

殊途同歸。newhead相當于之前的n1,cur=n2,next=n3;

structListNode*reverseList(structListNode*head)

structListNode*NewHead=NULL;

structListNode*cur=head;

while(cur)

structListNode*next=cur-next;

//頭插

cur-next=NewHead;//代表鏈表的指向方向。

NewHead=cur;//接著把地址傳過來(更新)

cur=next;//（更新）

returnNewHead;

}

3、leetcode876鏈表的中間結點力扣

思路：快慢指針法

structLis