双向链表基本操作

双向链表的情况与单链表类似，只是增加了一个前置链（即指向前一结点的指针域）
算法等，与单链表很相似。只是需要安置好前向指针域。注意点：在写关于链表的插入删除操作时，一定要注意该结点是不是最后一个结点，以免出现 p->next == NULL，p->next->next 未定义的情况，从而导致程序在特定条件下（比如你删除最后一个节点）出错。
也就是需要注意，最后一个节点和其他节点的操作不同，需要分开写。以下是代码：

#include <iostream>using namespace std;typedef struct BNode{int data;struct BNode *pre,*next;}BListNode;/**双链表创建*/BListNode * Create_BList（int n）{int i = 1;int elem;BListNode *head, *temp, *curr;/**curr：代表一个当前节点，它的下一节点是你正要创建的。*//**temp：代表你正要创建的节点。*/head = new BListNode;head->data = n;head->pre = NULL;head->next = NULL;curr = head;while（i <= n）{cout << "Please input one elem" << endl;cin >> elem;temp = new BListNode;temp->data = elem;temp->pre = curr;temp->next = NULL;curr->next = temp;curr = temp;i++;}return head;}/**双链表输出*/void Output_BList（BListNode *head）{BListNode *temp;temp = head->next;if（NULL == temp）cout << "The BList is NULL" << endl;cout << "The BList is" << endl;while（NULL ！= temp）{cout << temp->data << " ";temp = temp->next;}cout << endl;}/**删除元素i，不知道它是第几个结点*/BListNode * Delete_node（BListNode *head,int i）{BListNode *pre_temp, *temp;temp = head->next;pre_temp = head; /**这一步必须要有，防止删除的节点是第一个节点*/if（NULL == temp）cout << "The BList is NULL" << endl;while（NULL ！= temp）{if（temp->data ！= i）{pre_temp = temp;temp = temp->next;}else{if（NULL == temp->next）/**如果删除的元素是最后一个，需要加这一步，不然按下面写，temp->next->pre会没有定义，从而出错*/{pre_temp->next = NULL;delete temp;break;}pre_temp->next = temp->next;temp->next->pre = temp->pre;delete temp;break;}}if（NULL == temp）cout << "There is no i to be delete" << endl;return head;}/**插入一个节点：在第i个节点后，插入elem*/BListNode * Insert_node（BListNode *head,int i,int elem）{int j = 0;BListNode *temp, *p;temp = head; /**这里讲temp = head 并且 j = 0，保证了节点可以插入在第一个节点前*/while（NULL ！= temp）{if（j >= i）break; /**指针停留在第i个节点前*/j++;temp = temp->next;}if（NULL == temp->next） /**当第i个节点是最后一个节点时*/{p = new BListNode;p->data = elem;p->next = NULL;p->pre = temp;temp->next = p;return head;}p = new BListNode;p->data = elem;p->next = temp->next;p->pre = temp->next->pre;temp->next->pre = p;temp->next = p;return head;}int main（）{BListNode *p;p = Create_BList（5）;Output_BList（p）;Delete_node（p,2）; /**注意可以这样写，和 p = Delete_node（p,2）;效果相同*/cout << "删除结点后" << endl;Output_BList（p）;Insert_node（p,0,6）;cout << "插入结点后" << endl;Output_BList（p）;return 0;}

结果如下：
本文永久更新链接地址：http://www.linuxidc.com/Linux/2015-07/119766.htm