@[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. 双向链表的删除
   双链表删除结点时,只需遍历链表找到要删除的结点,而后将该节点从表中摘除即可。   例如,删除元素 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. 双向链表更改节点数据
   更改双链表中指定结点数据域的操作是在查找的根底上实现的。实现过程是:通过遍历找到存储有该数据元素的结点,间接更改其数据域即可。
/更新函数,其中,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. 双向链表的查找
   通常,双向链表同单链表一样,都仅有一个头指针。因而,双链表查找指定元素的实现同单链表相似,都是从表头顺次遍历表中元素。
/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 的地位插入元素 1
head=InsertListHead(head, 5,1);
printf("在表中第 5 的地位插入元素 1\t");
PrintList(head);
// 在表中第 3 的地位插入元素 7
head=InsertListEnd(head, 3, 7);
printf("在表中第 3 的地位插入元素 7\t");
PrintList(head);
// // 表中删除元素 7
head=DeleteList(head, 7);
printf("表中删除元素 7\t\t\t");
PrintList(head);
printf("元素 1 的地位是 \t:%d\n",FindList(head,1));
// 表中第 3 个节点中的数据改为存储 6
head = ModifyList(head,3,6);
printf("表中第 3 个节点中的数据改为存储 6\t");
PrintList(head);
return 0;
}
![在这里插入图片形容](/img/bVcLGUB)
**   大家的激励是我持续创作的能源,如果感觉写的不错,欢送关注,点赞,珍藏,转发,谢谢!**
** 以上代码均为测试后的代码。如有谬误和不妥的中央,欢送指出。**
** 局部内容参考网络,如有侵权,请分割删除。**
** 如遇到排版错乱的问题,能够通过以下链接拜访我的 CSDN。**
**CSDN:[CSDN 搜寻“嵌入式与 Linux 那些事”](https://blog.csdn.net/qq_16933601?spm=1000.2115.3001.5113)**
** 欢送欢送关注我的公众号:嵌入式与 Linux 那些事,支付秋招口试面试大礼包(华为小米等大厂面经,嵌入式知识点总结,口试题目,简历模版等)和 2000G 学习材料。**