C++怎么实现双向链表

这篇“C++怎么实现双向链表”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“C++怎么实现双向链表”文章吧。前面文章分析了单向链表，并给出了python和C++实现：单链表从原理到实现，python和C++两个版本本文介绍的双向链表是在单向链表基础上的一个改进，每个节点指向其直接前驱和直接后继节点。因此，从双向链表的任意位置开始，都能访问所有的节点。双向链表的缺点：从节点的结构上可以看出，双向链表的所需的存储空间大于单向链表。同时，对免费云主机域名于插入和删除等操作来说，双向链表的节点操作更加复杂，涉及到节点的前后两个节点。双向链表的节点：对于双向链表来说，它的每个节点要指向“直接前驱”和“直接后继”，所以节点类需要含有两个指针域。指向直接前驱的指针使用pre表示，指向后继的指针使用next表示。双向链表的节点含有两个指针域，即直接前驱pre和直接后继next。节点类采用的是模板实现，这样其所存储的数据就不再依赖于特定类型。链表类应该包含基本的增、改、删、查等操作，由于其各种功能的实现是很相似的，所以下面给出了需要实现的典型函数：构造函数：isEmpty()判断是否为空；size()返回链表长度；insert()头插、尾插、中间插入节点；delete()删除节点；getNode()获取节点；traversal()遍历链表；链表类的定义如下：*getNode(intindex);
intsize();
voidinsert(intdata,intindex);
voidtraversal();
voidremove(intindex);

private:
Node*head;
};初始化时需要创建头节点，作为头指针：::DoubleLinkedList(){
//创建头结点
head=newNode();
head->pre=NULL;
head->next=NULL;
head->setData(666);
}对于双向链表来说，判断是否为空只需要判断头指针是否指向其他Node节点：::isEmpty(){
if(head->next==NULL){
returntrue;
}
else
{
returnfalse;
}
}获取链表长度时需要判断链表是否为空，从而确定是否采用遍历的方式计算链表的长度。由于采用的不是循环链表，所以循环的结束条件是判断是否指向空节点：::size(){
if(isEmpty()){
return0;
}
else{
intcount=0;
Node*current=head->next;
//循环结束条件
while(current!=NULL)
{
current=current->next;
count++;
}
returncount;
}
}在插入和删除等操作中，需要频繁的进行节点获取操作。所以应该封装为单独的函数用于节点获取，如下：*DoubleLinkedList::getNode(intindex){
Node*current=head;
intcurrentCount=0;
//循环结束条件
while(currentCountnext;
currentCount++;
}
returncurrent;
}插入节点依旧包含头插法，尾插法和任意位置的插入。插入操作与单向链表的最大区别在于节点的指针移动较为复杂，需要将插入位置前后两个节点与新节点均建立联系：::insert(intdata,intindex){
Node*node=newNode();
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%dn”,index,this->size());
Node*temp=this->getNode(this->size()-1);
temp->next=node;
node->pre=temp;
}
//4、任意位置插入
else
{
Node*pre=this->getNode(index);
Node*next=pre->next;
node->next=pre->next;
node->pre=pre;
pre->next=node;
node->next->pre=node;
}
}前面已经定义了用于获取节点的getNode()函数，所以remove()函数只需要进行指针移动操作。将所要删除的节点的直接前驱节点和直接后继节点相连：::remove(intindex){
//保证索引有意义
if((indexsize()-1))&&(index>0)){
Node*node=this->getNode(index);
Node*pre=node->pre;
Node*next=node->next;
pre->next=next;
next->pre=pre;
}
}虽然可以从双向链表的任一个节点开始遍历整个链表，但是下面的实现依旧是从头结点开始的，循环的结束依旧是指向空指针：::traversal(){
if(!isEmpty()){
Node*current=head;
while(current)
{
coutgetData()next;
}
}
}以上就是关于“C++怎么实现双向链表”这篇文章的内容，相信大家都有了一定的了解，希望小编分享的内容对大家有帮助，若想了解更多相关的知识内容，请关注百云主机行业资讯频道。

相关推荐: 如何在运行时检测Python版本

这篇文章主要介绍了如何在运行时检测Python版本，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。有时，如果当前运行的 Python 引擎低于支持的版本，我们可能不想执行我们的程序。为此，您可以使…