typedef struct double_list { int date; struct double_list *pre; struct double_list *next; }list; 双向链表的构成： （以下示意图均摘自 来源： http://blog.csdn.net/fisherwan/ar ） 因为链表是双向的，所以可以通过第一个节点找到最后一个节点，也可以从最后一个节点找到第一个节点。因此大大提高了查找效率。 双向链表的初始化： 链表中只有一个元素，所以前驱和后驱指针均指向NULL。 双向链表的创建： 新插入节点的前驱指针pre指向前面的节点，后驱指针next指向NULL 双向链表的插入： 双向链表的插入也分三种情形： （1）在链表头部插入（修改3个指针） 新节点的next指向原链表第一个节点，原链表第一个节点的pre指向新插入的节点，头指针指向新插入的节点。 代码如下： pnew->next = head; head->pre = pnew; head = pnew; （2）在链表中间插入（修改4个指针） 找到要插入链表的前驱节点ptr，将ptr的next指向新插入的节点pnew,再将pnew的前驱指针pre指向ptr，再将ptr的下一个节点的前驱节点指向新插入的节点，最后将新插入节点的后驱节点指向原先ptr的下一个节点。 代码如下： ptr->next = pnew; pnew->pre = ptr; ptr->next->pre = pnew; pnew->next = ptr->next; （3）在链表尾部插入（修改3个指针） 原链表的最后一个节点的next指向新插入的节点，新插入节点的next指向NULL，新插入节点的pre指向原链表的最后一个节点。 代码如下： ptail->next = pnew; pnew->next =NULL; pnew->pre = ptail; 双向链表的删除： 双向链表的删除操作也分为三种情况： （1）在链表头部删除（修改2个指针） 将链表头指针指向第二个节点，此时这个这个节点为新的链表头，在将这个节点的pre指向NULL。 代码如下： first = head; head = head->next; head->pre = NULL; free(first); （2）在链表中间删除（修改2个指针） 找到要删除链表的前驱节点ptr，pdelete为ptr的后驱节点 代码如下： pdelete = ptr->next; ptr->next = pdelete->next; pdelete->next->pre = ptr; free(pdelete); （3）在链表尾部删除 将原链表的倒数第二个节点的next指向NULL，在释放掉原链表的最后一个节点的内存空间。 代码如下： ptail->pre->next = NULL free(ptail); 双向链表的C语言实现：（codeblocks完美运行） #include <stdio.h> #include <stdlib.h> #include <stdbool.h>//bool类型头文件 typedef struct double_list { int date; struct double_list *pre; struct double_list *next; }list; list* create_node() { list *node = (list*)malloc(sizeof(list)); if(node == NULL) { printf("创建头结点失败！\n"); return NULL; } node->pre = NULL; node->next = NULL; return node; } bool insert_list(list *head) { if(head == NULL) { printf("链表为空！\n"); return false; } list *p = head; //list *q = head->next; int val; printf("请输入要插入的元素："); scanf("%d",&val); list *newnode = create_node(); newnode->date = val; while(p->next != NULL) { p = p->next; //q = q->next; } //此时p->next = NULL //q->date = val; newnode->pre = p; newnode->next = NULL; p->next = newnode; return true; } int print_list(list *head) { if(head == NULL) { printf("链表为空！\n"); return ; } list *ptr = head->next; while(ptr != NULL) { printf("%d ",ptr->date); ptr = ptr->next; } } int delete_list(list *head) { if(head == NULL) { printf("链表为空！\n"); return ; } list *p = head; list *q = head->next; int val; printf("请输入要删除的元素："); scanf("%d",&val); while(p->next != NULL) { if(q->date == val) { if(q->next == NULL) { p->next = NULL; free(q); return 1; } q->next->pre = p; p->next = q->next; free(q); return 1; } p = p->next; q = q->next; } printf("没有找到该元素%d\n",val); return 0; } int update_list(list *head) { if(head == NULL) { printf("链表为空！\n"); return ; } list *temp = head; int olddate,newdate; printf("请输入要修改的值："); scanf("%d",&olddate); printf("修改为："); scanf("%d",&newdate); while(temp->next != NULL) { if(temp->next->date == olddate) { temp->next->date = newdate; return 1; } temp = temp->next; } printf("没有找到要修改的元素！\n"); return 0; } int seek_list(list *head) { if(head == NULL) { printf("链表为空！\n"); return ; } int val,i=0; list *p = head; printf("请输入要查找的元素："); scanf("%d",&val); while(p->next != NULL) { i++; if(p->next->date == val) { printf("查找到该元素%d,位置为%d\n",val,i); return 1; } p = p->next; } printf("没有找到该元素！\n"); return 0; } void menu() { system("cls");//清屏+ printf("\t\t|===============================================|\t\t\n"); printf("\t\t|==================双向链表操作=================|\t\t\n"); printf("\t\t|===================1.插入元素==================|\t\t\n"); printf("\t\t|===================2.打印链表==================|\t\t\n"); printf("\t\t|===================3.删除元素==================|\t\t\n"); printf("\t\t|===================4.修改链表==================|\t\t\n"); printf("\t\t|===================5.查找元素==================|\t\t\n"); printf("\t\t|==请输入对应的数字执行对应的功能！(输入0退出)==|\t\t\n"); printf("\t\t|====== 作者：RXX 时间：2017/07/06 ======|\t\t\n"); printf("\t\t|===============================================|\t\t\n"); } int main() { list *head = create_node(); int num; menu(); scanf("%d",&num); while(num) { switch(num) { case 1: printf("插入元素操作：\n"); if(insert_list(head)) printf("插入节点成功！\n"); else printf("插入节点失败！\n"); break; case 2: printf("打印元素操作：\n"); printf("打印双向链表：\n"); print_list(head); break; case 3: printf("删除元素操作：\n"); if(delete_list(head)) printf("删除节点成功！\n"); break; case 4: printf("修改元素操作：\n"); if(update_list(head)) printf("修改元素成功！\n"); break; case 5: printf("查找元素操作：\n"); if(seek_list(head)) printf("查找元素成功！\n"); break; } getch(); menu(); scanf("%d",&num); } printf("\t\t|================感谢使用！再见！===============|\t\t\n"); return 0; } 运行界面：
