双链表的定义
关于链表的基本知识我就不多说了，可以看看这篇文章：【C++】单链表（有指针）。讲的很详细
双链表也叫双向链表，是链表的一种，它的每个 结点(node) 中都有两个指针，分别是 后继(next) 和 前驱(pre) 。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点（这就是双链表的优势）。但双链表是“以空间换时间”。（来自：百度百科）
如图：
双链表的基本操作
同单链表一样，双链表的操作也有创建，插入，删除 三种基本操作。
创建双链表
和单链表差不多，只是多了一个pre前驱结点
struct node{//双链表结构体
int data;//数据域
node *pre;//前驱指针
node *next;//后继指针
}*head;//head是头指针（不知道的往上翻）
建立：
head=new node;
p=new node;
head->pre=NULL;
head->next=p;
p->pre=head;
p->next=NULL;
//以上就形成了一个双链表；
//其中，head的pre域为空，next域指向p；
//p的pre域指向head，next域为空
//head和p的data域都没赋值，它们的默认值是……我也不知道，反正不是0
形成的双链表如图：
这里的data没赋值，应该是一个很大的随机数
赋值
for(int i=1;i<=10;i++)
{
q=new node;
q->data=i*100;
q->next=q->pre=NULL;
p->next=q;
p=q;//迭代
}
输出
void Print()
{
p=head;
p=p->next;//这一句必须有，因为头结点只是一个引导，数据域没有值
while(p->next!=NULL)
{
p=p->next;
cout<<p->data<<" ";
}
cout<<endl;
}//真的没啥说的
运行结果：
插入一个结点到双链表中
先看图，然后再看代码
具体步骤：
实现代码如下：（写的有点复杂）
void Insert(int value,int first,int second)//把value插入到first和second之间
{
r=new node;
r->data=value;
int j=0;
p=head;
while(p->data!=first)
j++,p=p->next; //找到first的位置
j--;//因为多加了，所以要减去
p=head;
for(int i=0;i<=j;i++)
p=p->next;//此时，p->data就等于first
t=new node;
t=p;
t=t->next;//t往前走一步，所以，t->data这时就等于second
p->next=r;//步骤1
r->pre=p;//步骤2
r->next=t;//步骤3
t->pre=r;//步骤4
}
删除一个结点
删除就比较好理解了，不过咱还是先看图，再看代码
画图不易
void Delete(int n)//删除数据域的值为n的结点
{
p=head;
while(p->data!=n)
p=p->next;//找到了 数据域的值为n的结点 的前一个结点
p->next=p->next->next;//跳过这个结点
}
你们最爱的完整代码(无注释)
#include<bits/stdc++.h>
using namespace std;
struct node{
int data;
node *pre;
node *next;
}*head,*p,*q,*r,*t;
void Init(int n)
{
head=new node;
p=new node;
head->pre=NULL;
head->next=p;
p->pre=head;
p->next=NULL;
for(int i=1;i<=n;i++)
{
q=new node;
q->data=i*100;
q->next=q->pre=NULL;
p->next=q;
p=q;
}
}
void Print()
{
p=head;
p=p->next;
while(p->next!=NULL)
p=p->next,cout<<p->data<<" ";
cout<<endl;
}
void Delete(int n)
{
p=head;
while(p->data!=n-100)
p=p->next;
p->next=p->next->next;
}
void Insert(int value,int first,int second)
{
r=new node;
r->data=value;
int j=0;
p=head;
while(p->data!=first)
j++,p=p->next;
j--;
p=head;
for(int i=0;i<=j;i++)
p=p->next;
cout<<p->data;
t=new node;
t=p;
t=t->next;
p->next=r;
r->pre=p;
r->next=t;
t->pre=r;
p=head;
p=p->next;
}
int main()
{
int n;
cout<<"输入结点个数:";
cin>>n;
Init(n);
cout<<"创建的双链表为:"<<endl;
Print();
cout<<endl;
int d;
cout<<"输入要删除的结点:";
cin>>d;
Delete(d);
cout<<"删除"<<d<<"之后的双链表为:"<<endl;
Print();
cout<<endl;
int jd,start,finish;
cout<<"输入要插入的结点的值及其位置:";
cin>>jd>>start>>finish;
Insert(jd,start,finish);
cout<<"在"<<start<<"和"<<finish<<"之间插入"<<jd<<"之后的双链表为:"<<endl;
Print();
return 0;
}
运行结果：
打字不易，画图也不易
而可爱的你又看得那么认真，为什么不点个赞再走呢？
