C++实现双向链表代码分析

第C++实现双向链表代码分析目录前言:一、双向链表优缺点二、C++实现分析（1）节点类（2）链表类分析（3）链表类构造函数（4）isEmpty()判断是否为空（5）size()获取链表长度（6）getNode()获取节点（7）insert()插入节点（8）、remove()删除节点（9）traversal()遍历链表函数

前言:

前面文章分析了单向链表，并给出了python和C++实现：单链表从原理到实现，python和C++两个版本

本文介绍的双向链表是在单向链表基础上的一个改进，每个节点指向其直接前驱和直接后继节点。因此，从双向链表的任意位置开始，都能访问所有的节点。

一、双向链表优缺点

双向链表的缺点：

从节点的结构上可以看出，双向链表的所需的存储空间大于单向链表。同时，对于插入和删除等操作来说，双向链表的节点操作更加复杂，涉及到节点的前后两个节点。

双向链表的节点：

对于双向链表来说，它的每个节点要指向直接前驱和直接后继，所以节点类需要含有两个指针域。指向直接前驱的指针使用pre表示，指向后继的指针使用next表示。

二、C++实现分析

（1）节点类

双向链表的节点含有两个指针域，即直接前驱pre和直接后继next。节点类采用的是模板实现，这样其所存储的数据就不再依赖于特定类型。

templateclassT

classNode{

public:

Node(){}

Node*pre;

Node*next;

//由于data属性是私有的

//所以采用get和set对data进行处理

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

TgetData(){returnthis-data;}

private:

Tdata;

};

（2）链表类分析

链表类应该包含基本的增、改、删、查等操作，由于其各种功能的实现是很相似的，

所以下面给出了需要实现的典型函数：

构造函数：isEmpty()判断是否为空；size()返回链表长度；insert()头插、尾插、中间插入节点；delete()删除节点；getNode()获取节点；traversal()遍历链表；

链表类的定义如下：

templateclassP

classDoubleLinkedList{

public:

DoubleLinkedList();

boolisEmpty();

NodeP

*getNode(intindex);

intsize();

voidinsert(intdata,intindex);

voidtraversal();

voidremove(intindex);

private:

NodeP*head;

};

（3）链表类构造函数

初始化时需要创建头节点，作为头指针：

templateclassP

DoubleLinkedListP::DoubleLinkedList(){

//创建头结点

head=newNodeP

head-pre=NULL;

head-next=NULL;

head-setData(666);

}

（4）isEmpty()判断是否为空

对于双向链表来说，判断是否为空只需要判断头指针是否指向其他Node节点：

templateclassP

boolDoubleLinkedListP::isEmpty(){

if(head-next==NULL){

returntrue;

}

else

{

returnfalse;

}

}

（5）size()获取链表长度

获取链表长度时需要判断链表是否为空，从而确定是否采用遍历的方式计算链表的长度。

由于采用的不是循环链表，所以循环的结束条件是判断是否指向空节点：

templateclassP

intDoubleLinkedListP::size(){

if(isEmpty()){

return0;

}

else{

intcount=0;

NodeP*current=head-next;

//循环结束条件

while(current!=NULL)

{

current=current-next;

count++;

}

returncount;

}

}

（6）getNode()获取节点

在插入和删除等操作中，需要频繁的进行节点获取操作。

所以应该封装为单独的函数用于节点获取，如下：

templateclassP

NodeP*DoubleLinkedListP::getNode(intindex){

NodeP*current=head;

intcurrentCount=0;

//循环结束条件

while(currentCount=index)

{

current=current-next;

currentCount++;

}

returncurrent;

}

（7）insert()插入节点

插入节点依旧包含头插法，尾插法和任意位置的插入。插入操作与单向链表的最大区别在于节点的指针移动较为复杂，需要将插入位置前后两个节点与新节点均建立联系：

templateclassP

voidDoubleLinkedListP::insert(intdata,intindex){

NodeP*node=newNodeP

node-setData(data);

//1、列表为空时

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()删除节点

前面已经定义了用于获取节点的getNode()函数，所以remove()函数只需要进行指针移动操作。

将所要删除的节点的直接前驱节点和直接后继节点相连：

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()遍历链表函数

虽然可以从双向链表的任一个节点开始遍历整个链表，但是下面的实现依旧是从头结点开始的，循环的结束依旧是指向空指针：

templateclassP

voidDoubleLinke