链表初解（二）——双链表的创建、删除、插入

本文主要是介绍链表初解（二）——双链表的创建、删除、插入，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

下面是基本的双链表操作，由于双链表有两个方向，所以在删除和插入节点时，可以节省一个指针，只用一个链表上的指针和一个待操作的指针即可完成插入和删除；同时也要注意在编写双链表时对情况的判断要仔细，否则很容易出错~

#include<iostream>
using namespace std;typedef struct student
{int data;struct student *next;struct student *pre;
}dnode;//建立双链表
dnode *create()
{dnode *head, *p, *s;int x;head = (dnode *)malloc(sizeof(dnode));p = head;cout<<"\nInput the data : ";while(1){if(scanf("%d", &x) != EOF && x != 0){s = (dnode *)malloc(sizeof(dnode));s->data = x;p->next = s;s->pre = p;p = s;}else break;}head = head->next;head->pre = NULL;p->next = NULL;return head;
}//双链表删除节点
dnode *del(dnode *head, int num)
{dnode *p1;p1 = head;while(num != p1->data && p1->next != NULL)p1 = p1->next;if(num == p1->data){if(head == p1){head = head->next;head->pre = NULL;}/*此处的处理与单链表不同，因为双链表有两个方向，所以在定义时仅定义一个指针，这使得当出现删除链表尾部时，由于NULL没有前驱，导致无法连接，所以要分开讨论。*/else if(p1->next == NULL) p1->pre->next = NULL;else{//p1为最后一个节点，如没有上一个分支，则第二个语句会出错。p1->pre->next = p1->next;p1->next->pre = p1->pre;}free(p1);	//释放}else cout<<"There is no %d "<<num;return head;
}//双链表插入节点
dnode *insert(dnode *head, int num)
{dnode *p0, *p1;p1 = head;p0 = (dnode *)malloc(sizeof(dnode));p0->data = num;while(num > p1->data && p1->next != NULL)p1 = p1->next;if(num <= p1->data){if(head == p1){p0->next = p1;p1->pre = p0;head = p0;}else{p1->pre->next = p0;p0->pre = p1->pre;p0->next = p1;p1->pre = p0;}}else{//插入尾部~p1->next = p0;p0->next = NULL;p0->pre = p1;}return head;
}//计算表长
int length(dnode *head)
{int n = 0;while(head != NULL){head = head->next;n++;}return n;
}
//打印双链表
void print(dnode *head)
{int n = length(head);cout<<"Output the DoubleList ("<<n<<" records~) : ";while(head != NULL){if(head->next == NULL) cout<<head->data<<endl;else cout<<head->data<<"<->";head = head->next;}
}
//排序函数同单链表，此处省略了~，默认输入为递增哈~
int main()
{dnode *head;//创建head = create();print(head);//删除int numD;cout<<"\nDelete : ";cin>>numD;print(del(head, numD));//插入int numS;cout<<"\nInsert : ";cin>>numS;print(insert(head, numS));return 0;
}