C++實(shí)現(xiàn)雙向鏈表代碼分析

第C++實(shí)現(xiàn)雙向鏈表代碼分析目錄前言:一、雙向鏈表優(yōu)缺點(diǎn)二、C++實(shí)現(xiàn)分析（1）節(jié)點(diǎn)類（2）鏈表類分析（3）鏈表類構(gòu)造函數(shù)（4）isEmpty()判斷是否為空（5）size()獲取鏈表長(zhǎng)度（6）getNode()獲取節(jié)點(diǎn)（7）insert()插入節(jié)點(diǎn)（8）、remove()刪除節(jié)點(diǎn)（9）traversal()遍歷鏈表函數(shù)

前言:

前面文章分析了單向鏈表，并給出了python和C++實(shí)現(xiàn)：?jiǎn)捂湵韽脑淼綄?shí)現(xiàn)，python和C++兩個(gè)版本

本文介紹的雙向鏈表是在單向鏈表基礎(chǔ)上的一個(gè)改進(jìn)，每個(gè)節(jié)點(diǎn)指向其直接前驅(qū)和直接后繼節(jié)點(diǎn)。因此，從雙向鏈表的任意位置開(kāi)始，都能訪問(wèn)所有的節(jié)點(diǎn)。

一、雙向鏈表優(yōu)缺點(diǎn)

雙向鏈表的缺點(diǎn)：

從節(jié)點(diǎn)的結(jié)構(gòu)上可以看出，雙向鏈表的所需的存儲(chǔ)空間大于單向鏈表。同時(shí)，對(duì)于插入和刪除等操作來(lái)說(shuō)，雙向鏈表的節(jié)點(diǎn)操作更加復(fù)雜，涉及到節(jié)點(diǎn)的前后兩個(gè)節(jié)點(diǎn)。

雙向鏈表的節(jié)點(diǎn)：

對(duì)于雙向鏈表來(lái)說(shuō)，它的每個(gè)節(jié)點(diǎn)要指向直接前驅(qū)和直接后繼，所以節(jié)點(diǎn)類需要含有兩個(gè)指針域。指向直接前驅(qū)的指針使用pre表示，指向后繼的指針使用next表示。

二、C++實(shí)現(xiàn)分析

（1）節(jié)點(diǎn)類

雙向鏈表的節(jié)點(diǎn)含有兩個(gè)指針域，即直接前驅(qū)pre和直接后繼next。節(jié)點(diǎn)類采用的是模板實(shí)現(xiàn)，這樣其所存儲(chǔ)的數(shù)據(jù)就不再依賴于特定類型。

templateclassT

classNode{

public:

Node(){}

Node*pre;

Node*next;

//由于data屬性是私有的

//所以采用get和set對(duì)data進(jìn)行處理

voidsetData(Tdata){this-data=data;}

TgetData(){returnthis-data;}

private:

Tdata;

};

（2）鏈表類分析

鏈表類應(yīng)該包含基本的增、改、刪、查等操作，由于其各種功能的實(shí)現(xiàn)是很相似的，

所以下面給出了需要實(shí)現(xiàn)的典型函數(shù)：

構(gòu)造函數(shù)：isEmpty()判斷是否為空；size()返回鏈表長(zhǎng)度；insert()頭插、尾插、中間插入節(jié)點(diǎn)；delete()刪除節(jié)點(diǎn)；getNode()獲取節(jié)點(diǎn)；traversal()遍歷鏈表；

鏈表類的定義如下：

templateclassP

classDoubleLinkedList{

public:

DoubleLinkedList();

boolisEmpty();

NodeP

*getNode(intindex);

intsize();

voidinsert(intdata,intindex);

voidtraversal();

voidremove(intindex);

private:

NodeP*head;

};

（3）鏈表類構(gòu)造函數(shù)

初始化時(shí)需要?jiǎng)?chuàng)建頭節(jié)點(diǎn)，作為頭指針：

templateclassP

DoubleLinkedListP::DoubleLinkedList(){

//創(chuàng)建頭結(jié)點(diǎn)

head=newNodeP

head-pre=NULL;

head-next=NULL;

head-setData(666);

}

（4）isEmpty()判斷是否為空

對(duì)于雙向鏈表來(lái)說(shuō)，判斷是否為空只需要判斷頭指針是否指向其他Node節(jié)點(diǎn)：

templateclassP

boolDoubleLinkedListP::isEmpty(){

if(head-next==NULL){

returntrue;

}

else

{

returnfalse;

}

}

（5）size()獲取鏈表長(zhǎng)度

獲取鏈表長(zhǎng)度時(shí)需要判斷鏈表是否為空，從而確定是否采用遍歷的方式計(jì)算鏈表的長(zhǎng)度。

由于采用的不是循環(huán)鏈表，所以循環(huán)的結(jié)束條件是判斷是否指向空節(jié)點(diǎn)：

templateclassP

intDoubleLinkedListP::size(){

if(isEmpty()){

return0;

}

else{

intcount=0;

NodeP*current=head-next;

//循環(huán)結(jié)束條件

while(current!=NULL)

{

current=current-next;

count++;

}

returncount;

}

}

（6）getNode()獲取節(jié)點(diǎn)

在插入和刪除等操作中，需要頻繁的進(jìn)行節(jié)點(diǎn)獲取操作。

所以應(yīng)該封裝為單獨(dú)的函數(shù)用于節(jié)點(diǎn)獲取，如下：

templateclassP

NodeP*DoubleLinkedListP::getNode(intindex){

NodeP*current=head;

intcurrentCount=0;

//循環(huán)結(jié)束條件

while(currentCount=index)

{

current=current-next;

currentCount++;

}

returncurrent;

}

（7）insert()插入節(jié)點(diǎn)

插入節(jié)點(diǎn)依舊包含頭插法，尾插法和任意位置的插入。插入操作與單向鏈表的最大區(qū)別在于節(jié)點(diǎn)的指針移動(dòng)較為復(fù)雜，需要將插入位置前后兩個(gè)節(jié)點(diǎn)與新節(jié)點(diǎn)均建立聯(lián)系：

templateclassP

voidDoubleLinkedListP::insert(intdata,intindex){

NodeP*node=newNodeP

node-setData(data);

//1、列表為空時(shí)

if(isEmpty()){

head-next=node;

node-pre=head;

return;

}

//2、頭插法

if(index==0){

node-next=head-next;

head-next-pre=node;

node-pre=head;

head-next=node;

}

//3、尾插法

elseif(index=this-size()-1){

//printf("index%d,size%d\n",index,this-size());

NodeP*temp=this-getNode(this-size()-1);

temp-next=node;

node-pre=temp;

}

//4、任意位置插入

else

{

NodeP*pre=this-getNode(index);

NodeP*next=pre-next;

node-next=pre-next;

node-pre=pre;

pre-next=node;

node-next-pre=node;

}

}

（8）、remove()刪除節(jié)點(diǎn)

前面已經(jīng)定義了用于獲取節(jié)點(diǎn)的getNode()函數(shù)，所以remove()函數(shù)只需要進(jìn)行指針移動(dòng)操作。

將所要?jiǎng)h除的節(jié)點(diǎn)的直接前驅(qū)節(jié)點(diǎn)和直接后繼節(jié)點(diǎn)相連：

templateclassP

voidDoubleLinkedListP::remove(intindex){

//保證索引有意義

if((index(this-size()-1))(index0)){

NodeP*node=this-getNode(index);

NodeP*pre=node-

NodeP*next=node-next;

pre-next=next;

next-pre=pre;

}

}

（9）traversal()遍歷鏈表函數(shù)

雖然可以從雙向鏈表的任一個(gè)節(jié)點(diǎn)開(kāi)始遍歷整個(gè)鏈表，但是下面的實(shí)現(xiàn)依舊是從頭結(jié)點(diǎn)開(kāi)始的，循環(huán)的結(jié)束依舊是指向空指針：

templateclassP

voidDoubleLinke