@[TOC]

1.双向链表的定义

上一节学习了单向链表单链表详解。明天学习双链表。学习之前先对单向链表和双向链表做个回顾。
单向链表特点：
  1.咱们能够轻松的达到下一个节点, 然而回到前一个节点是很难的.
  2.只能从头遍历到尾或者从尾遍历到头(个别从头到尾)
双向链表特点
  1.每次在插入或删除某个节点时, 须要解决四个节点的援用, 而不是两个. 实现起来要艰难一些
  2.绝对于单向链表, 必然占用内存空间更大一些.
  3.既能够从头遍历到尾, 又能够从尾遍历到头
双向链表的定义:
  双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，别离指向间接后继和间接前驱。所以，从双向链表中的任意一个结点开始，都能够很不便地拜访它的前驱结点和后继结点。下图为双向链表的结构图。

  从上中能够看到，双向链表中各节点蕴含以下 3 局部信息：
  指针域：用于指向以后节点的间接前驱节点；
  数据域：用于存储数据元素。
  指针域：用于指向以后节点的间接后继节点；

双向循环链表的定义:
  双向链表也能够进行首尾连贯，形成双向循环链表,如下图所示
在创立链表时，只须要在最初将收尾相连即可（创立链表代码中曾经标出）。其余代码稍加改变即可。

双链表的节点构造用 C 语言实现为：

/*随机数的范畴*/#define MAX 100/*节点构造*/typedef struct Node{    struct Node *pre;    int data;    struct Node *next;}Node;

2.双向链表的创立

  同单链表相比，双链表仅是各节点多了一个用于指向间接前驱的指针域。因而，咱们能够在单链表的根底轻松实现对双链表的创立。
  须要留神的是，与单链表不同，双链表创立过程中，每创立一个新节点，都要与其前驱节点建设两次分割，别离是：
  将新节点的 prior 指针指向间接前驱节点；
  将间接前驱节点的 next 指针指向新节点；
  这里给出创立双向链表的 C 语言实现代码：

Node* CreatList(Node * head,int length){    if (length == 1)    {                return( head = CreatNode(head));    }    else    {        head = CreatNode(head);        Node * list=head;        for (int i=1; i<length; i++)         /*创立并初始化一个新结点*/        {            Node * body=(Node*)malloc(sizeof(Node));            body->pre=NULL;            body->next=NULL;            body->data=rand()%MAX;            /*间接前趋结点的next指针指向新结点*/            list->next=body;            /*新结点指向间接前趋结点*/            body->pre=list;            /*把body指针给list返回*/            list=list->next;        }             }    /*加上以下两句就是双向循环链表*/    // list->next=head;    // head->prior=list;    return head;}

3.双向链表的插入

  依据数据增加到双向链表中的地位不同，可细分为以下 3 种状况：
1.增加至表头
  将新数据元素增加到表头，只须要将该元素与表头元素建设双层逻辑关系即可。
  换句话说，假如新元素节点为 temp，表头节点为 head，则须要做以下 2 步操作即可：
  temp->next=head; head->prior=temp;
  将 head 移至 temp，从新指向新的表头；
  将新元素 7 增加至双链表的表头，则实现过程如下图所示：

2.增加至表的两头地位
  同单链表增加数据相似，双向链表两头地位增加数据须要通过以下 2 个步骤，如下图所示：
  新节点先与其间接后继节点建设双层逻辑关系；
  新节点的间接前驱节点与之建设双层逻辑关系；

3.增加至表尾
  与增加到表头是一个情理，实现过程如下：
  找到双链表中最初一个节点；
  让新节点与最初一个节点进行双层逻辑关系；

/*在第add地位的后面插入data节点*/Node * InsertListHead(Node * head,int add,int data){    /*新建数据域为data的结点*/    Node * temp=(Node*)malloc(sizeof(Node));    if(head == NULL)    {        printf("malloc error!\r\n");        return NULL;    }        else    {        temp->data=data;        temp->pre=NULL;        temp->next=NULL;     }    /*插入到链表头，要非凡思考*/    if (add==1)    {        temp->next=head;        head->pre=temp;        head=temp;    }    else    {        Node * body=head;        /*找到要插入地位的前一个结点*/        for (int i=1; i<add-1; i++)        {            body=body->next;        }        /*判断条件为真，阐明插入地位为链表尾*/        if (body->next==NULL)        {            body->next=temp;            temp->pre=body;        }        else        {            body->next->pre=temp;            temp->next=body->next;            body->next=temp;            temp->pre=body;        }    }    return head;}

/在第add地位的前面插入data节点/
Node InsertListEnd(Node head,int add,int data)
{

int i = 1;/*新建数据域为data的结点*/Node * temp=(Node*)malloc(sizeof(Node));temp->data=data;temp->pre=NULL;temp->next=NULL;Node * body=head;while ((body->next)&&(i<add+1)){    body=body->next;    i++;}/*判断条件为真，阐明插入地位为链表尾*/if (body->next==NULL){    body->next=temp;    temp->pre=body;    temp->next=NULL;}else{    temp->next=body->pre->next;    temp->pre=body->pre;    temp->pre=body->pre;    body->pre->next=temp;}return head;

}

## 4.双向链表的删除&emsp;&emsp;双链表删除结点时，只需遍历链表找到要删除的结点，而后将该节点从表中摘除即可。&emsp;&emsp;例如，删除元素 2 的操作过程如图 所示：![在这里插入图片形容](/img/bVcLGUA)

Node DeleteList(Node head,int data)
{

Node * temp=head;/*遍历链表*/while (temp){    /*判断以后结点中数据域和data是否相等，若相等，摘除该结点*/    if (temp->data==data)     {        /*判断是否是头结点*/        if(temp->pre == NULL)        {            head=temp->next;            temp->next = NULL;            free(temp);            return head;        }        /*判断是否是尾节点*/        else if(temp->next == NULL)        {            temp->pre->next=NULL;            free(temp);            return head;        }        else        {            temp->pre->next=temp->next;            temp->next->pre=temp->pre;            free(temp);            return head;           }            }    temp=temp->next;}printf("Can not find %d!\r\n",data);return head;

}

## 5.双向链表更改节点数据&emsp;&emsp;更改双链表中指定结点数据域的操作是在查找的根底上实现的。实现过程是：通过遍历找到存储有该数据元素的结点，间接更改其数据域即可。

/更新函数，其中，add 示意更改结点在双链表中的地位，newElem 为新数据的值/
Node ModifyList(Node p,int add,int newElem)
{

Node * temp=p;/*遍历到被删除结点*/for (int i=1; i<add; i++) {    temp=temp->next;}temp->data=newElem;return p;

}

## 6.双向链表的查找&emsp;&emsp;通常，双向链表同单链表一样，都仅有一个头指针。因而，双链表查找指定元素的实现同单链表相似，都是从表头顺次遍历表中元素。

/head为原双链表，elem示意被查找元素/
int FindList(Node * head,int elem)
{
/新建一个指针t，初始化为头指针 head/

Node * temp=head;int i=1;while (temp) {    if (temp->data==elem)    {        return i;    }    i++;    temp=temp->next;}/*程序执行至此处，示意查找失败*/return -1;

}

## 7.双向链表的打印

/输入链表的性能函数/
void PrintList(Node * head)
{

Node * temp=head;while (temp) {    /*如果该节点无后继节点，阐明此节点是链表的最初一个节点*/    if (temp->next==NULL)     {        printf("%d\n",temp->data);    }    else    {        printf("%d->",temp->data);    }    temp=temp->next;}

}

## 8.测试函数及后果

int main()
{

Node * head=NULL;//创立双链表head=CreatList(head,5);printf("新创建双链表为\t");PrintList(head);//在表中第 5 的地位插入元素 1head=InsertListHead(head, 5,1);printf("在表中第 5 的地位插入元素 1\t");PrintList(head);//在表中第 3 的地位插入元素 7head=InsertListEnd(head, 3, 7);printf("在表中第 3 的地位插入元素 7\t");PrintList(head);// //表中删除元素 7head=DeleteList(head, 7);printf("表中删除元素 7\t\t\t");PrintList(head);printf("元素 1 的地位是\t：%d\n",FindList(head,1));//表中第 3 个节点中的数据改为存储 6head = ModifyList(head,3,6);printf("表中第 3 个节点中的数据改为存储6\t");PrintList(head);return 0;

}

![在这里插入图片形容](/img/bVcLGUB)**&emsp;&emsp;大家的激励是我持续创作的能源，如果感觉写的不错，欢送关注，点赞，珍藏，转发，谢谢！****以上代码均为测试后的代码。如有谬误和不妥的中央，欢送指出。****局部内容参考网络，如有侵权，请分割删除。****如遇到排版错乱的问题，能够通过以下链接拜访我的CSDN。****CSDN:[CSDN搜寻“嵌入式与Linux那些事”](https://blog.csdn.net/qq_16933601?spm=1000.2115.3001.5113)****欢送欢送关注我的公众号：嵌入式与Linux那些事，支付秋招口试面试大礼包（华为小米等大厂面经，嵌入式知识点总结，口试题目，简历模版等）和2000G学习材料。**