数据结构双向链表实战应用(c语言源程序)

一个完整的双向链表程序(C语言版)#include <stdio.h>#include <stdlib.h>typedef struct tagDbNode{int data;struct tagDbNode * left;struct tagDbNode * right;} DbNode, * pdbNode;//创建结点pdbNode CreateNode(int data){pdbNode pnode = (pdbNode)malloc(sizeof(DbNode));pnode->data = data;pnode->left = pnode->right = pnode; //创建新结点时，让其前驱和后继指针都指向自身return pnode;}//=========================================================================//创建链表pdbNode CreateList(int head) //参数给出表头结点数据（表头结点不作为存放有意义数据的结点）{pdbNode pnode = (pdbNode)malloc(sizeof(DbNode));pnode->data = head;pnode->left = pnode->right = pnode;return pnode;}//插入新结点,总是在表尾插入; 返回表头结点pdbNode InsertNode(pdbNode node, int data) // 参数1是链表的表头结点，参数2是要插入的结点（结点数据为data）{pdbNode pnode = CreateNode(data);pdbNode ptmp = node->left;// 从左到右恢复链接node->left->right = pnode;pnode->right = node;// 从右到左恢复链接node->left = pnode;pnode->left = ptmp;return node;}//查找结点，成功则返回满足条件的结点指针，否则返回NULLpdbNode FindNode(pdbNode node, int data) // 参数1是链表的表头结点，参数2是要查找的结点（其中结点数据为data）{pdbNode pnode = node->right;while (pnode->right != node && pnode->data != data){pnode = pnode->right;}if (pnode->right == node) return NULL;return pnode;}//删除满足指定条件的结点, 返回表头结点, 删除失败返回NULL（失败的原因是不存在该结点）pdbNode DeleteNode(pdbNode node, int data) // 参数1是链表的表头结点，参数2是要删除的结点（其中结点数据为data）{pdbNode ptmp;pdbNode pnode = FindNode(node, data);if (NULL == pnode) return NULL;ptmp = pnode->left;ptmp->right = pnode->right;pnode->right->left = ptmp;free(pnode);return node;}//获取链表的长度int GetLength(pdbNode node) // 参数为链表的表头结点{int nCount = 0;pdbNode pnode = node->right;while (pnode->right != node){nCount++;}return nCount;}//打印整个链表void PrintList(pdbNode node) // 参数为链表的表头结点{pdbNode pnode;if (NULL == node) return;pnode= node->right;while (pnode != node){printf("%d ", pnode->data);pnode = pnode ->right;}printf("\n");}//将链表反序打印void ReverPrint(pdbNode node) //参数为链表的表头结点{pdbNode pnode;if (NULL == node) return;pnode= node->left;while (pnode != node){printf("%d ", pnode->data);pnode = pnode->left;printf("\n");}//删除链表void DeleteList(pdbNode node) //参数为链表表头结点{pdbNode pnode = node->right;pdbNode ptmp;if (NULL == node) return;while (pnode != node){ptmp = pnode->right;free(pnode);pnode = ptmp;}free(node);}//测试程序#include <stdio.h>#include <stdlib.h>#include "dblist.h"#define FALSE 0#define TRUE 1typedef unsigned int bool;void main(){int nChoose;int data;//int length;bool bFlag = FALSE;pdbNode pnode;pdbNode list = CreateList(0);while(FALSE == bFlag)printf("Main Menu\n");printf("1. Insert\n");printf("2. Delete Node\n");printf("3. Find\n");printf("4. Length\n");printf("5. Positive Print\n");printf("6. Negative Print\n");printf("7. Delete List\n");printf("0. quit\n\n");scanf("%d", &nChoose);switch(nChoose){case 1:printf("Input the data to insert:");scanf("%d", &data);list = InsertNode(list, data);PrintList(list);break;case 2:printf("Input the data to delete:");scanf("%d", &data);DeleteNode(list, data);break;case 3:printf("Input the data to find:");scanf("%d", &data);pnode = FindNode(list, data);if (NULL != pnode){printf("Find succeed!\n");}else{printf("Find failed!\n");}break;case 4:printf("The list's length is %d", GetLength(list)); break;case 5:PrintList(list); break;case 6:ReverPrint(list); break;case 7:DeleteList(list); break;case 0:DeleteList(list); bFlag = TRUE;}}}。

c语⾔双向链表的简单操作-创建、插⼊、删除数据结构-双向链表的创建、插⼊和删除双向链表是数据结构中重要的结构，也是线性结构中常⽤的数据结构，双向指针，⽅便⽤户从⾸结点开始沿指针链向后依次遍历每⼀个结点，结点的前驱和后继查找⽅便。

#include <stdio.h>#include <stdlib.h>//双向链表结点的定义typedef struct dbnode{int data;struct dbnode *prio, *next;}DbNode, linkdblist;//创建双向链表DbNode *creatlist(void){linkdblist *p, *q, *head;q = p = (linkdblist *)malloc(sizeof(linkdblist));p->next = NULL;head = q;p = (linkdblist *)malloc(sizeof(linkdblist));scanf("%d", &p->data);while (p->data != -1){q->next = p;p->prio = q;q = p;p = (linkdblist *)malloc(sizeof(linkdblist));scanf("%d", &p->data);}q->next = NULL;return head;}//输出双向链表void print(linkdblist *head){linkdblist *p;p = head->next;if (p == NULL)printf("空链表！\n");while (p != NULL){printf("%d ", p->data);p = p->next;}}//向双向链表中的第i个位置插⼊⼀个结点x void insertdblist(linkdblist *head, int x, int i) {linkdblist *p, *q = head;if (i == 1)q = head;else{q = q->next;int c = 1;while ((c<i - 1) && (q != NULL)){q = q->next;c++;}}if (q != NULL && q->next != NULL){p = (linkdblist *)malloc(sizeof(linkdblist)); p->data = x;p->prio = q;p->next = q->next;q->next = p;q->next->prio = p;}elseprintf("找不到插⼊的位置！");}//删除双向链表中指定位置上的⼀个结点void deletelinkdblist(linkdblist *head, int i) {linkdblist *p, *q = head;if (i == 1)q = head;else{q = q->next;int c = 1;while (c < i - 1 && q != NULL){q = q->next;c++;}}if (q != NULL && q->next != NULL){p = q->next;p->prio = q;p->prio->next = p->next;p->next->prio = p->prio;free(p);}else if (q->next == NULL){p = q;p->prio->next = NULL;free(p);}elseprintf("没有找到待删除的结点");}//双向链表的主函数void main(){linkdblist *head;head = creatlist();print(head);printf("\n\n====向双向链表的某位置插⼊⼀个值====\n"); int num, i;printf("输⼊插⼊的位置：");scanf("%d", &i);printf("\n输⼊插⼊的值：");scanf("%d", &num);insertdblist(head, num, i);print(head);printf("\n");printf("\n\n====删除双向链表的某位置上的⼀个值====\n"); int j;printf("输⼊删除的位置：");scanf("%d", &j);deletelinkdblist(head, j);print(head);system("pause");printf("\n");}。

C语⾔实现双向链表⽬前我们所学到的链表，⽆论是动态链表还是静态链表，表中各节点中都只包含⼀个指针（游标），且都统⼀指向直接后继节点，通常称这类链表为单向链表（或单链表）。

虽然使⽤单链表能 100% 解决逻辑关系为 “⼀对⼀” 数据的存储问题，但在解决某些特殊问题时，单链表并不是效率最优的存储结构。

⽐如说，如果算法中需要⼤量地找某指定结点的前趋结点，使⽤单链表⽆疑是灾难性的，因为单链表更适合 “从前往后” 找，⽽ “从后往前” 找并不是它的强项。

为了能够⾼效率解决类似的问题，本篇⽂章我们⼀起来讨论双向链表（简称双链表）。

从名字上理解双向链表，即链表是 “双向” 的,如下图所⽰：双向，指的是各节点之间的逻辑关系是双向的，但通常头指针只设置⼀个，除⾮实际情况需要。

从上图中可以看到，双向链表中各节点包含以下 3 部分信息（如下图所⽰）：指针域：⽤于指向当前节点的直接前驱节点；数据域：⽤于存储数据元素。

指针域：⽤于指向当前节点的直接后继节点；因此，双链表的节点结构⽤ C 语⾔实现为:typedef struct Node{struct Node * prior;//指向直接前趋int data;struct Node * next;//指向直接后继}Node;双向链表的创建同单链表相⽐，双链表仅是各节点多了⼀个⽤于指向直接前驱的指针域。

因此，我们可以在单链表的基础轻松实现对双链表的创建。

需要注意的是，与单链表不同，双链表创建过程中，每创建⼀个新节点，都要与其前驱节点建⽴两次联系，分别是：1. 将新节点的 prior 指针指向直接前驱节点；2. 将直接前驱节点的 next 指针指向新节点；这⾥给出创建双向链表的 C 语⾔实现代码：Node* initNode(Node * head){head=(Node*)malloc(sizeof(Node));//创建链表第⼀个结点（⾸元结点）head->prior=NULL;head->next=NULL;head->data=1;Node * list=head;for (int i=2; i<=3; i++) {//创建并初始化⼀个新结点Node * body=(Node*)malloc(sizeof(Node));body->prior=NULL;body->next=NULL;body->data=i;list->next=body;//直接前趋结点的next指针指向新结点body->prior=list;//新结点指向直接前趋结点list=list->next;}return head;}我们可以尝试着在 main 函数中输出创建的双链表，C 语⾔代码如下：#include <stdio.h>#include <stdlib.h>//节点结构typedef struct Node{struct Node * prior;int data;struct Node * next;}Node;//双链表的创建函数Node* initNode(Node * head);//输出双链表的函数void display(Node * head);int main() {//创建⼀个头指针Node * head=NULL;//调⽤链表创建函数head=initNode(head);//输出创建好的链表display(head);//显⽰双链表的优点printf("链表中第 4 个节点的直接前驱是：%d",head->next->next->next->prior->data);return 0;}Node* initNode(Node * head){//创建⼀个⾸元节点，链表的头指针为headhead=(Node*)malloc(sizeof(Node));//对节点进⾏初始化head->prior=NULL;head->next=NULL;head->data=1;//声明⼀个指向⾸元节点的指针，⽅便后期向链表中添加新创建的节点Node * list=head;for (int i=2; i<=5; i++) {//创建新的节点并初始化Node * body=(Node*)malloc(sizeof(Node));body->prior=NULL;body->next=NULL;body->data=i;//新节点与链表最后⼀个节点建⽴关系list->next=body;body->prior=list;//list永远指向链表中最后⼀个节点list=list->next;}//返回新创建的链表return head;}void display(Node * head){Node * temp=head;while (temp) {//如果该节点⽆后继节点，说明此节点是链表的最后⼀个节点if (temp->next==NULL) {printf("%d\n",temp->data);}else{printf("%d <-> ",temp->data);}temp=temp->next;}}程序运⾏结果：1 <->2 <->3 <->4 <-> 5链表中第 4 个节点的直接前驱是：3双向链表基本操作下⾯继续讨论有关双向链表的⼀些基本操作，即如何在双向链表中添加、删除、查找或更改数据元素。

双向链表的基本操作C语⾔#include<stdio.h>#include<stdlib.h>typedef struct node* DNode;struct node {int data;DNode prior; //前⾯数据地址DNode next; //后⾯数据地址};//创建双向链表void CreatNode(DNode *head) {DNode s; //新节点指针char e;(*head) = (DNode)malloc(sizeof(struct node));//头结点(*head)->prior = (*head); //初始头结点的前驱和后驱都指向⾃⼰(*head)->next = (*head);printf("输⼊数据\n");scanf("%c", &e);while (e!='\n'){s = (DNode)malloc(sizeof(struct node)); //新节点分配空间s->data = e;s->prior = (*head); //新节点的prior连前⼀个结点s->next = (*head)->next; //新节点的next连后边结点(*head)->next->prior = s; //后⼀个结点的prior连新结点(*head)->next = s; //新节点前⾯的next连新结点scanf("%c", &e);}}//向后遍历输出void PrintList1(DNode L) {DNode p;p = L;p = p->next;while (p != L) {printf("%c", p->data);p = p->next;}printf("\n");}//向前遍历输出void PrintList2(DNode L) {DNode p;p = L->prior;while (p != L) {printf("%c", p->data);p = p->prior;}printf("\n");}//查找第i处数据的地址DNode FindPosition(DNode L,int i) {int j = 0;DNode p = L;while (p->next != L&&j < i) {p = p->next;j++;}return p;}//插⼊void InsertList(DNode L) {DNode s,p; //s为新结点 p为新节点前⼀个结点int i;char e;printf("在第⼏处插⼊:\n");scanf("%d", &i);getchar();printf("插⼊什么数据:\n");scanf("%c", &e);p = FindPosition(L, i-1); //新节点前⼀个结点地址s = (DNode)malloc(sizeof(struct node));//申请新节点空间s->data = e;s->prior = p; //新节点的prior连上前⼀个结点s->next = p->next; //新节点的next连上后⼀个结点p->next->prior = s; //新节点后的结点的prior连上新结点p->next = s; //新节点前的结点的next连上新结点}//删除void DeleteList(DNode L){DNode s,p; //s为新结点 p为要删除的结点int i;printf("删除第⼏处的数据:\n");scanf("%d", &i);p = FindPosition(L, i); //要删除结点的地址p->prior->next = p->next; //要删除的结点的前⼀个结点的next，连上要删结点后的结点 p->next->prior = p->prior;//要删除结点的后⼀个结点的prior，连上要删结点的前⼀个结点free(p);}int main() {DNode list;CreatNode(&list);//PrintList1(list);PrintList2(list);InsertList(list);PrintList2(list);DeleteList(list);PrintList2(list);}。

c实现双向链表实现双向链表：创建、插⼊、删除#include <iostream>#include <stdio.h>#include <string.h>#include <stdlib.h>using namespace std;typedef struct student{int data;struct student *next;struct student *pre;}dnode;//创建链表dnode *create(){//1. 定义变量dnode *head = NULL;dnode *p = NULL;dnode *s = NULL;int x = 0;int cycle = 1;//2. 新建headhead = (dnode*)malloc(sizeof(dnode));p = head;//3. 添加节点while(cycle){printf("input the data:");scanf("%d", &x);if (x != 0){s = (dnode*)malloc(sizeof(dnode));s->data = x;p->next = s;s->pre = p;p = s;}else{cycle = 0;}}//4. 删除 headp->next = NULL;p = head;head = head->next;free(p);p = NULL;//5. 返回 headreturn head;}//插⼊节点dnode *insert(dnode *head, int num){//1. 定义变量dnode *p0 = NULL;dnode *p1 = NULL;p1 = head;//2. 新建节点p0 = (dnode*)malloc(sizeof(dnode));p0->data = num;//3. 定位插⼊位置（升序）while(p0->data > p1->data && p1->next != NULL){p1 = p1->next;//4. 插⼊新节点if (p0->data > p1->data) //尾{p1->next = p0;p0->pre = p1;p0->next = NULL;}else{if (head == p1) //头{p0->next = p1;p1->pre = p0;head = p0;}else//中间{p1->pre->next = p0;p0->next = p1;p0->pre = p1->pre;p1->pre = p0;}}//5. 返回 headreturn head;}//删除节点dnode *del(dnode *head, int num){//1. 定义变量dnode *p = NULL;p = head;//2. 定位节点while (num != p->data && p->next != NULL) {p = p->next;}//3. 删除节点if (num != p->data){printf("not found:%d\n", num);}else{if (p == head) //头{head = p->next;head->pre = NULL;free(p);}else if (p->next == NULL) //尾{p->pre->next = NULL;free(p);}else//中间{p->next->pre = p->pre;p->pre->next = p->next;free (p);}}return head;}//计算链表长度int length(dnode *head){dnode *p;int n = 0;p = head;while(p != NULL){p = p->next;n++;printf("len:%d\n", n);return n;}//显⽰void show(dnode *head){dnode *p;int n = 0;p = head;while(p != NULL){printf("data:%d ", p->data); p = p->next;}printf("\n");}int main(){dnode *head = create();show(head);length(head);head = insert(head, 2);show(head);head = del(head, 2);show(head);}。

C语⾔双向链表的基本操作实现#include <stdio.h>#include <stdlib.h>int len;//定义双向链表的节点typedef struct Node{int data;struct Node *prior;struct Node *next;}Node;//初始化⼀个链表的节点、Node* create_node(void){Node *p;p = (Node*)malloc(sizeof(Node));if(p == NULL){printf("动态内存分配失败！\n");exit(0);}scanf("%d",&(p->data));p->prior = NULL;p->next = NULL;return (p);}//建⽴含有N个结点的双向链表Node* create_list(int n){Node *p,*new1,*head;int i;if(n >= 1) //结点的个数 >= 1 的时候，先⽣成第⼀个结点{new1 = create_node();head = new1;p = new1;}for(i = 2;i <= n;i++) //⽣成第⼀个结点以后的结点，并建⽴双向链表的关系{new1 = create_node();p->next = new1;new1->prior = p;p = new1;}len = n;if(n >= 1)return (head);elsereturn0;}//链表的长度int len_list(int len){return len;}//定位到链表的任意位置Node* pos_list(Node *head,int n){int i = 1;Node *p;if(i <= n){p = head;for(i = 2;i <= n;i++)p = p->next;}return p;}//正向遍历⼀个链表void out_front_list(Node *head){if(head == NULL){printf("输⼊的链表信息有误，链表不存在！\n"); }else{Node *p;p = head;while(p != NULL){printf("%d ",p->data);p = p->next;}}}//反向遍历⼀个链表void out_reverse_list(Node *head){if(head == NULL){printf("输⼊的链表信息有误，链表不存在！\n"); }else{int n;n = len_list(len);Node *p;p = pos_list(head,n);while(p != NULL){printf("%d ",p->data);p = p->prior;}}}//在链表的头部插⼊结点Node* start_insert_list(Node *head){Node *p;p = create_node();p->next = head;head->prior = p;head = p;len++;return (p);}//在链表的尾部插⼊结点Node* end_insert_list(Node *head){int n;n = len_list(len);Node *p,*new1;new1 = create_node();p = pos_list(head,n);p->next = new1;new1->prior = p;len++;return (head);}//插⼊到任意位置之前Node* insert_befor_list(Node *head){int a,newlen;Node *pos,*p;printf("请输⼊要插⼊结点的位置：");scanf("%d",&a);printf("请输⼊要插⼊的结点的值：");newlen = len_list(len);if(a > newlen){head = end_insert_list(head);}else{if(a <= 1){head = start_insert_list(head);}else{pos = pos_list(head,a);pos->prior->next = p;p->prior = pos->prior;p->next = pos;pos->prior = p;}}len++;return (head);}//插⼊到任意位置之后Node* insert_after_list(Node *head){int a,newlen;Node *pos,*p;printf("请输⼊要插⼊结点的位置："); scanf("%d",&a);printf("请输⼊要插⼊的结点的值："); newlen = len_list(len);if(a >= newlen){head = end_insert_list(head);}else{if(a < 1){head = start_insert_list(head); }else{pos = pos_list(head,a);p = create_node();p->next = pos->next;pos->next->prior = p;pos->next = p;p->prior = pos;}}len++;return (head);}//删除头结点Node* delect_start_list(Node *head){Node *pos;pos = head;head = head->next;head->prior = NULL;free(pos);len--;return(head);}//删除尾结点Node* delect_end_list(Node *head){Node *p,*pos;int newlen;newlen = len_list(len);pos = pos_list(head,newlen);p = pos;p = p->prior;p->next = NULL;free(pos);len--;return (head);}//删除指定位置的节点Node* delect_list(Node *head){int newlen,i;Node *pos;newlen = len_list(len);printf("请输⼊眼删除结点的位置：\n"); scanf("%d",&i);if(i <= 1)head = delect_start_list(head); else if(i >=newlen)head = delect_end_list(head); else{pos->prior->next = pos->next;pos->next->prior = pos->prior;free(pos);}len--;return(head);}int main(){//函数的声明Node* create_node(void); //定义双向链表的节点Node* create_list(int n); //建⽴含有N个结点的双向链表int len_list(int len); //链表的长度Node* pos_list(Node *head,int n); //定位到链表的任意位置 Node* tail_list(Node *head); //将指针定位在链表的尾部void out_front_list(Node *head); //正向遍历⼀个链表void out_reverse_list(Node *head); //反向遍历⼀个链表Node* start_insert_list(Node *head); //在链表的头部插⼊结点 Node* end_insert_list(Node *head); //在链表的尾部插⼊结点 Node* insert_befor_list(Node *head); //插⼊到任意位置之前 Node* insert_after_list(Node *head); //插⼊到任意位置之后Node* delect_start_list(Node *head); //删除头结点Node* delect_end_list(Node *head); //删除尾结点Node* delect_list(Node *head); //删除指定位置的节点//int newlen;Node *head;printf("请输⼊要建⽴双向链表的长度：\n");scanf("%d",&len);printf("请为双向链表赋值：\n");head = create_list(len);printf("链表的长度为：%d\n",len = len_list(len));printf("正向遍历双向链表：\n");out_front_list(head);printf("\n链表的长度为：%d",len = len_list(len));printf("\n反向遍历双向链表：\n");out_reverse_list(head);printf("\n链表的长度为：%d",len = len_list(len));printf("\n请输⼊在链表头部插⼊结点的值：\n");head = start_insert_list(head);printf("链表的长度为：%d",len = len_list(len));printf("\n正向遍历双向链表：\n");out_front_list(head);printf("\n链表的长度为：%d",len = len_list(len));printf("\n反向遍历双向链表：\n");out_reverse_list(head);printf("\n链表的长度为：%d",len = len_list(len));printf("\n请输⼊在链表尾部插⼊结点的值：\n");head = end_insert_list(head);printf("链表的长度为：%d",len = len_list(len));printf("\n正向遍历双向链表：\n");out_front_list(head);printf("\n链表的长度为：%d",len = len_list(len));printf("\n反向遍历双向链表：\n");out_reverse_list(head);printf("\n链表的长度为：%d",len = len_list(len));printf("\n插⼊到任意位置之前：\n");head = insert_befor_list(head);printf("链表的长度为：%d",len = len_list(len));printf("\n正向遍历双向链表：\n");out_front_list(head);printf("\n链表的长度为：%d",len = len_list(len));printf("\n反向遍历双向链表：\n");out_reverse_list(head);printf("\n链表的长度为：%d",len = len_list(len));printf("\n插⼊到任意位置之后：\n");head = insert_after_list(head);printf("链表的长度为：%d",len = len_list(len));printf("\n正向遍历双向链表：\n");out_front_list(head);printf("\n链表的长度为：%d",len = len_list(len));printf("\n反向遍历双向链表：\n");out_reverse_list(head);printf("\n链表的长度为：%d",len = len_list(len));printf("\n删除头结点：\n");head = delect_start_list(head);printf("链表的长度为：%d",len = len_list(len)); printf("\n正向遍历双向链表：\n");out_front_list(head);printf("\n链表的长度为：%d",len = len_list(len)); printf("\n反向遍历双向链表：\n");out_reverse_list(head);printf("\n链表的长度为：%d",len = len_list(len)); printf("\n删除尾结点：\n");head = delect_end_list(head);printf("链表的长度为：%d",len = len_list(len)); printf("\n正向遍历双向链表：\n");out_front_list(head);printf("\n链表的长度为：%d",len = len_list(len)); printf("\n反向遍历双向链表：\n");out_reverse_list(head);printf("\n链表的长度为：%d",len = len_list(len)); printf("\n删除指定位置的结点：\n");head = delect_list(head);printf("链表的长度为：%d",len = len_list(len)); printf("\n正向遍历双向链表：\n");out_front_list(head);printf("\n链表的长度为：%d",len = len_list(len)); printf("\n反向遍历双向链表：\n");out_reverse_list(head);printf("\n链表的长度为：%d",len = len_list(len)); return0;}。

双向链表的应⽤实例管理单向链表的缺点分析:1. 单向链表，查找的⽅向只能是⼀个⽅向，⽽双向链表可以向前或者向后查找。

2. 单向链表不能⾃我删除，需要靠辅助节点，⽽双向链表，则可以⾃我删除，所以前⾯我们单链表删除节点时，总是找到 temp,temp 是待删除节点的前⼀个节点。

双向链表如何完成遍历，添加，修改和删除的思路 1) 遍历：和单链表⼀样，只是可以向前，也可以向后查找 2) 添加 (默认添加到双向链表的最后) (1)先找到双向链表的最后这个节点 (2) temp.next = newNode; (3) newNode.pre = temp; 3) 修改思路和原来的单向链表⼀样 4) 删除 (1) 因为是双向链表，因此，我们可以实现⾃我删除某个节点 (2) 直接找到要删除的这个节点，⽐如 temp temp.pre.next = temp.next; temp.next.pre = temp.pre;//若删除的是最后⼀个节点，会有空指针异常代码实现1. class doublelinkedlist {2. //先初始化⼀个头节点，头节点不能动，不存放具体数据3. private hero head = new hero(-1, "", "");4.5. //添加节点6. public void add(hero h) {7. //因为head节点不能动，因此我们需要⼀个辅助变量temp8. hero temp = head;9. //遍历链表，找到最后⼀个节点10. while (true) {11. if (temp.getNext() == null) {12. break;13. }14. //如果没有到最后，将temp后移15. temp = temp.getNext();16. }17. //当退出while循环时，temp就指向了链表的最后18. //将链表的最后⼀个节点的next指向要添加的这个节点19. //将要添加的这个节点的pre指向链表的最后⼀个节点20. temp.setNext(h);21. h.setPre(temp);22. }23.24. //第⼆种⽅式在添加英雄时，根据排名将英雄插⼊到指定位置25. //(如果有这个排名，则添加失败，并给出提⽰)26. public void addByOrder(hero h) {27. //因为头节点不能动，因此我们仍然通过⼀个辅助指针(变量)来帮助找到添加的位置28. hero temp = head;29. boolean flag = false;// flag 标志添加的编号是否存在，默认为 false30. while (true) {31. if (temp.getNext() == null) {//说明 temp 已经在链表的最后32. break;33. } else if (temp.getNext().getNum() > h.getNum()) {//位置找到，就在 temp 的后⾯插⼊34. break;35. } else if (temp.getNext().getNum() == h.getNum()) {//说明希望添加的 heroNode 的编号已然存在36. flag = true;37. break;38. }39. temp = temp.getNext();//后移，遍历当前链表40. }41. if (flag) { //不能添加，说明编号存在42. System.out.println("添加的序号为" + h.getNum() + "的英雄序号已经存在，添加失败。

数据结构中的双向链表实现和应用场景双向链表是一种常用的数据结构，它在许多实际应用中都发挥着重要的作用。

本文将介绍双向链表的实现原理以及一些常见的应用场景。

一、双向链表的实现原理双向链表由一系列节点组成，每个节点包含两个指针，一个指向前一个节点，一个指向后一个节点。

相比于单向链表，双向链表可以实现双向遍历，提高了一些操作的效率。

1.1 节点定义双向链表的节点通常由数据域和两个指针域组成，例如：```struct Node {int data; // 节点数据Node* prev; // 前一个节点指针Node* next; // 后一个节点指针};```1.2 插入操作在双向链表中插入一个节点可以分为两种情况：在表头插入和在表尾插入。

在表头插入时，只需修改原来头节点的prev指针为新节点的地址，并将新节点的next指针指向原头节点即可。

在表尾插入时，需要先找到原来的尾节点，然后将尾节点的next指针指向新节点的地址，并将新节点的prev指针指向尾节点的地址。

1.3 删除操作删除操作与插入操作类似，同样分为在表头和表尾删除节点。

在表头删除时，只需将头节点的next指针指向新的头节点，同时将新头节点的prev指针置为空。

在表尾删除时，需要先找到尾节点的前一个节点，然后将该节点的next指针置为空。

1.4 查找操作双向链表支持从前向后和从后向前两种遍历方式。

从前向后遍历时，我们可以利用节点的next指针不断向后遍历得到所有节点。

同样，从后向前遍历时，可以利用节点的prev指针不断向前遍历得到所有节点。

二、双向链表的应用场景双向链表广泛应用于各种软件和系统中，下面列举了一些常见的应用场景。

2.1 浏览器的历史记录在浏览器中，经常需要记录用户浏览过的网页历史记录。

这时可以使用双向链表来实现。

每当用户访问一个新的网页，就在双向链表中插入一个新节点，同时将新节点的next指针指向前一个节点，prev指针指向后一个节点。

C语⾔实现双向链表这个⼩代码是我凭⾃⼰对指针和链表的理解和认识，⾃⼰实现的，没有参考其他⼈的代码，如果有相同的地⽅，那真的只是巧合，代码我在ubuntu 15.04下测试通过，可能存在很多错误和漏洞．doublelist.c/*************************************************************************> File Name: doublelist.c> Author: ChenYiLiang> Mail: chenyiliangex@> Created Time: Sat 21 Mar 2015 07:32:22 PM CST************************************************************************/#include <stdio.h>#include <stdlib.h>#include <string.h>struct userdata{int userid;char username[30];struct userdata *previous;struct userdata *next;};struct userdata *header;size_t scanf_id;char scanf_name[30];int yesno;int deletePosition;int alterPosition;int alterId;char alterName[30];int searchPosition;FILE *ptr_fpid;/*向链表中插⼊数据*/int insert_list(struct userdata *header, size_t position, char name[], size_t id);/*删除链表中指定的节点*/int delete_node(struct userdata *header, size_t position);/*修改指定位置的节点信息*/int alter_node(struct userdata *header, size_t position, size_t id, char name[]);/*查找链表中的数据*/struct userdata *search_node(struct userdata *header, size_t position);/*遍历链表*/int travel_list(struct userdata *header);/*判断链表是空*/int isempty(struct userdata *header);/*将链表结构写⼊⽂件*/int write_into_file(struct userdata *header, FILE *fp);/*从⽂件读取数据放到链表中*/int read_from_file(struct userdata *header, FILE *fp);int main(){struct userdata *header_node = (struct userdata *)malloc(sizeof(struct userdata));header_node -> previous = NULL;header_node -> next = NULL;read_from_file(header_node, ptr_fpid);travel_list(header_node);while(1){//scanf("%*[^\n]");//scanf("%*c");//scanf("%*[^\n]");printf("please input id - ");scanf("%d", &scanf_id);//scanf("%*c");//scanf("%*[^\n]");printf("please input your name - ");scanf("%s", scanf_name);printf("%d - %s\n\n", scanf_id, scanf_name);//isempty(header_node);/*0表⽰默认插⼊到链表的尾部*/insert_list(header_node, 0, scanf_name, scanf_id);//write_into_file(header_node, ptr_fpid);//isempty(header_node);printf("input anymore - ");scanf("%d", &yesno);if(yesno == -1){break;}scanf("%*c");scanf("%*[^\n]");// travel_list(header_node);}getchar();//printf("delete position data - ");//scanf("%d", &deletePosition);//delete_node(header_node, deletePosition);// printf("alter data for position - ");// scanf("%d", &alterPosition);// printf("please inout new id - ");// scanf("%d",&alterId);// printf("please input new name - ");// scanf("%s", alterName);// alter_node(header_node, alterPosition, alterId, alterName);write_into_file(header_node, ptr_fpid);travel_list(header_node);printf("\n\n");printf("please input position to search - ");scanf("%d", &searchPosition);struct userdata *searchData = search_node(header_node, searchPosition);printf("%d\n", searchData -> userid);printf("%s\n", searchData -> username);return 0;}/* 插⼊节点 */int insert_list(struct userdata *header, size_t position, char name[], size_t id ){ struct userdata *temp_newuser = header;struct userdata *getMemory = (struct userdata *)malloc(sizeof(struct userdata)); getMemory -> userid = id;strncpy(getMemory -> username, name, 30);/*当position == 0时,表⽰默认插⼊到链表的尾部*/if(0 == position){if(NULL != temp_newuser -> next){while(NULL != temp_newuser -> next){temp_newuser = temp_newuser -> next;}}}/*当position > 1时则寻找合适的位置插⼊*/if(1 <= position){for(int i = 0; i <= position; i++){/*当执⾏此处的代码时表⽰,链表已经到达尾部或者是空链表*/if(NULL == temp_newuser -> next){break;}temp_newuser = temp_newuser -> next;}}getMemory -> previous = temp_newuser;if(temp_newuser -> next == NULL){temp_newuser -> next = getMemory;getMemory -> next = NULL;}else{temp_newuser -> next -> previous = getMemory;getMemory -> next = temp_newuser -> next;temp_newuser -> next = getMemory;}return 0;}/*删除链表中指定的节点*/int delete_node(struct userdata *header, size_t position){int is_empty = isempty(header);if(0 == is_empty){printf("this si a empty list!\n\n");return -1;}struct userdata *deleteNode = header;for(int i = 0; i < position; i++ ){/*当执⾏此处的代码时表⽰,链表已经到达尾部或者是空链表*/if(NULL == deleteNode -> next){break;}deleteNode = deleteNode -> next;}/**/deleteNode -> next -> previous = deleteNode -> previous;deleteNode -> previous -> next = deleteNode -> next;free(deleteNode);return 0;}/*修改指定位置的节点信息*/int alter_node(struct userdata *header, size_t position, size_t id, char name[]){ int isEmpty = isempty(header);if(0 == isEmpty){printf("this is a empty list\n\n");return -1;}struct userdata *alterNode = header;for(int i = 0; i < position; i++ ){/*当执⾏此处的代码时表⽰,链表已经到达尾部或者是空链表*/if(NULL == alterNode -> next){break;}alterNode = alterNode -> next;}alterNode -> userid = id;strncpy(alterNode -> username, name, 30);return 0;}/*查找链表中的数据*/struct userdata *search_node(struct userdata *header, size_t position){int isEmpty = isempty(header);if(0 == isEmpty){printf("this is a empty!\n");return NULL;}struct userdata *searchNode = header;for(int i = 0; i < position; i++){if(NULL == searchNode -> next){break;}searchNode = searchNode -> next;}return searchNode;}/*遍历链表*/int travel_list(struct userdata *header){struct userdata *travel = header;if(NULL == travel -> next){printf("This is a empty list!!\n");return 1;}for(travel = travel -> next ; ; travel = travel -> next){printf("%d\n",travel -> userid);printf("%s\n", travel -> username);if(NULL == travel -> next){break;}}return 1;}/*判断链表是空*/int isempty(struct userdata *header){if(header -> next == NULL){return 0;}else{return 1;}}/*将链表结构写⼊⽂件*/int write_into_file(struct userdata *header, FILE *fp){fp = fopen("listdata", "wb");if(NULL == fp){perror("open file failed when write into file!"),exit(-1);}printf("come into write!\n");for(struct userdata *move = header -> next; ; move = move -> next){fwrite(move,sizeof(struct userdata), 1, fp);if(NULL == move -> next){break;}}fclose(fp);fp = NULL;return 0;}/*从⽂件读取数据放到链表中*/int read_from_file(struct userdata *header, FILE *fp){struct userdata *readfile = header;fp = fopen("listdata", "rb");if(NULL == fp){perror("open file failed when read - ");return -1;}while(1){struct userdata *newread = (struct userdata *)malloc(sizeof(struct userdata)); fread(newread, sizeof(struct userdata), 1, fp);if(feof(fp)){/*当读取到⽂件的尾部时．跳出循环*/break;}readfile -> next = newread;newread -> next = NULL;newread -> previous = readfile;readfile = newread;}fclose(fp);fp = NULL;return 0;}C语⾔实现双向链表删除节点、插⼊节点、双向输出等操作#include<cstdio>#include<cstdlib>typedef struct DoubleLinkedList{int data;struct DoubleLinkedList *pre;struct DoubleLinkedList *next;}DlinkedList_Node;//建⽴链表DlinkedList_Node* createDLink(){DlinkedList_Node *head,*p,*s;int x;head = (DlinkedList_Node*)malloc(sizeof(DlinkedList_Node));p = head;while(1){printf("please input the data: \n");scanf("%d",&x);if(x != 65535){s = (DlinkedList_Node*)malloc(sizeof(DlinkedList_Node));s ->data = x;s-> pre = p;p->next = s;p=s;}else{printf("\n数据输⼊结束\n");break;}}p->next = NULL;head = head ->next;head->pre = NULL;return head;}//顺序、反序打印链表void printDLink(DlinkedList_Node *head){DlinkedList_Node *p,*s;p = head;printf("正序输出双向链表：\n");while(p){printf("%d ",p->data);s = p;p = p->next;}printf("\n 逆序输出双向链表: \n");while(s){printf("%d ",s->data);s = s->pre;}printf("\n \n");}//删除⼀个结点DlinkedList_Node* deleteDlinkedList_Node(DlinkedList_Node *head,int i) {DlinkedList_Node *p;p = head;if(p->data == i){head = p->next;head->pre = NULL;free(p);return head;}while(p){if(p->data == i){p->pre->next = p->next;p->next->pre = p->pre;free(p);return head;}p = p->next;}printf("没有找到想要删除的数据\n");return head;}//插⼊⼀个结点DlinkedList_Node* insertDlinkedList_Node(DlinkedList_Node *head,int i) {DlinkedList_Node *p,*temp;p = head;temp = (DlinkedList_Node*)malloc(sizeof(DlinkedList_Node));temp ->data = i;if(i < p->data)//⽐头结点数据⼩，插⼊到链表头部{head = temp;head->next = p;//此处p为原来的headhead->pre = NULL;p->pre = head;//此处p为原来的headreturn head;}while(p != NULL && i > p->data)//寻找合适的插⼊位置{p = p->next;}if(i < p->data)//在链表中间某处找到合适插⼊位置{temp ->next = p;temp ->pre = p->pre;p ->pre->next = temp;p ->pre = temp;return head;}else//没有找到合适的位置，只有将数据插⼊到链表尾部{p->next = temp; //遍历到链表尾部，p==NULLtemp ->pre = p;temp ->next = NULL;return head;}}int main(){DlinkedList_Node *head;head = createDLink();printDLink(head);head = insertDlinkedList_Node(head,1012);head = deleteDlinkedList_Node(head,1991);printDLink(head);}/*****************************运⾏结果如下：please input the data:1991please input the data:1992please input the data:2013please input the data:2014please input the data:512please input the data:420please input the data:65535数据输⼊结束正序输出双向链表：1991 1992 2013 2014 512 420逆序输出双向链表:420 512 2014 2013 1992 1991正序输出双向链表：1012 1992 2013 2014 512 420逆序输出双向链表:420 512 2014 2013 1992 1012******************************/以上就是本⽂给⼤家分享的全部内容了，希望对⼤家更加熟悉C语⾔双向链表能够有所帮助。

c++双向链表操作⽰例（创建双向链、双向链表中查找数据、插⼊数据等）双向链表也叫双链表，是链表的⼀种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。

所以，从双向链表中的任意⼀个结点开始，都可以很⽅便地访问它的前驱结点和后继结点。

⼀般我们都构造双向循环链表。

（1）定义双向链表的基本结构复制代码代码如下:typedef struct _DOUBLE_LINK_NODE{int data;struct _DOUBLE_LINK_NODE* prev;struct _DOUBLE_LINK_NODE* next;}DOUBLE_LINK_NODE;（2）创建双向链表节点复制代码代码如下:DOUBLE_LINK_NODE* create_double_link_node(int value){DOUBLE_LINK_NODE* pDLinkNode = NULL;pDLinkNode = (DOUBLE_LINK_NODE*)malloc(sizeof(DOUBLE_LINK_NODE));assert(NULL != pDLinkNode);memset(pDLinkNode, 0, sizeof(DOUBLE_LINK_NODE));pDLinkNode->data = value;return pDLinkNode;}（3）删除双向链表复制代码代码如下:void delete_all_double_link_node(DOUBLE_LINK_NODE** pDLinkNode){DOUBLE_LINK_NODE* pNode;if(NULL == *pDLinkNode)return ;pNode = *pDLinkNode;*pDLinkNode = pNode->next;free(pNode);delete_all_double_link_node(pDLinkNode);}（4）在双向链表中查找数据复制代码代码如下:DOUBLE_LINK_NODE* find_data_in_double_link(const DOUBLE_LINK_NODE* pDLinkNode, int data){DOUBLE_LINK_NODE* pNode = NULL;if(NULL == pDLinkNode)return NULL;pNode = (DOUBLE_LINK_NODE*)pDLinkNode;while(NULL != pNode){if(data == pNode->data)return pNode;pNode = pNode ->next;}return NULL;}（5）双向链表中插⼊数据复制代码代码如下:STATUS insert_data_into_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data) {DOUBLE_LINK_NODE* pNode;DOUBLE_LINK_NODE* pIndex;if(NULL == ppDLinkNode)return FALSE;if(NULL == *ppDLinkNode){pNode = create_double_link_node(data);assert(NULL != pNode);*ppDLinkNode = pNode;(*ppDLinkNode)->prev = (*ppDLinkNode)->next = NULL;return TRUE;}if(NULL != find_data_in_double_link(*ppDLinkNode, data))return FALSE;pNode = create_double_link_node(data);assert(NULL != pNode);pIndex = *ppDLinkNode;while(NULL != pIndex->next)pIndex = pIndex->next;pNode->prev = pIndex;pNode->next = pIndex->next;pIndex->next = pNode;return TRUE;}（6）双向链表中删除数据复制代码代码如下:STATUS delete_data_from_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data) {DOUBLE_LINK_NODE* pNode;if(NULL == ppDLinkNode || NULL == *ppDLinkNode)return FALSE;pNode = find_data_in_double_link(*ppDLinkNode, data);if(NULL == pNode)return FALSE;if(pNode == *ppDLinkNode){if(NULL == (*ppDLinkNode)->next){*ppDLinkNode = NULL;}else{*ppDLinkNode = pNode->next;(*ppDLinkNode)->prev = NULL;}}else{if(pNode->next)pNode->next->prev = pNode->prev;pNode->prev->next = pNode->next;}free(pNode);return TRUE;}（7）统计双向链表中数据的个数复制代码代码如下:int count_number_in_double_link(const DOUBLE_LINK_NODE* pDLinkNode){int count = 0;DOUBLE_LINK_NODE* pNode = (DOUBLE_LINK_NODE*)pDLinkNode;while(NULL != pNode){count ++;pNode = pNode->next;}return count;}（8）打印双向链表中数据复制代码代码如下:void print_double_link_node(const DOUBLE_LINK_NODE* pDLinkNode){DOUBLE_LINK_NODE* pNode = (DOUBLE_LINK_NODE*)pDLinkNode;while(NULL != pNode){printf("%d\n", pNode->data);pNode = pNode ->next;}}今天我们讨论的双向链表是⾮循环的，⼤家可以考虑⼀下如果改成循环双向链表，应该怎么写？如果是有序的循环双向链表，⼜该怎么写？。