双链表操作（一）
一、双链表的引入：
1、在引入双链表之前，我们先来回忆之前为什么要引入单链表介绍：它是解决的数组的数组的大小比较死板不容易扩展的问题；使用堆内存来存储数据，将数据分散到各个节点之间，其各个节点在内存中可以不相连，节点之间通过指针进行单向链接。链表中的各个节点内存不相连，有利于利用碎片化的内存。但是单链表各个节点之间只由一个指针单向链接，这样实现有一些局限性。局限性主要体现在单链表只能经由指针单向移动（一旦指针移动过某个节点就无法再回来，如果要再次操作这个节点除非从头指针开始再次遍历一次），因此单链表的某些操作就比较麻烦（算法比较有局限）。这里可以看我之前写的单链表操作文章结合一下，就能非常好理解单链表的局限性了。
2、所以为了解决单链表的局限性，就引入了双链表的概念了：听名字就可以猜到，每个节点都包含两个指针，一个指针指向上一个节点，一个指针指向下一个节点--------双向链表的节点 = 有效数据 + 2个指针（一个指向后一个节点，另一个指向前一个节点）。这里需要注意的是，第一就是头节点的一个指针指向NULL空指针（没有前驱节点），第二就是尾节点的一个指针指向NULL指针（没有后继节点））。这里我就手工画图来方便理解（因为在网上没有找到比较好的示意图让大家更容易理解，没有艺术感，画的难看，望理解）：
所以，我们在编程序的时候，这两个指针的控制就是我们的难点，因为我们始终要让这个链表保持这样的链接不管是在创建的时候、插入的时候、删除的时候等，一定要让节点的两个指针指向正确的节点。
二、代码实现：
1、创建双链表代码框架引入：
#include <stdio.h>
#include <stdlib.h>
// 双链表的节点
struct node
{
int data; // 有效数据
struct node *pPrev; // 前向指针，指向前一个节点
struct node *pNext; // 后向指针，指向后一个节点
};
struct node *create_node(int data)
{
struct node *p = (struct node *)malloc(sizeof(struct node));//分配内存
if (NULL == p)
{
printf("malloc error.\n");
return NULL;
}
p->data = data;
p->pPrev = NULL;
p->pNext = NULL; // 默认创建的节点前向后向指针都指向NULL
return p;
}
int main(void)
{
struct node *pHeader = create_node(0); // 头指针
return 0;
}
2、在双链表末尾插入一个新节点（直接看图理解来的快，就不多说了）：
#include <stdio.h>
#include <stdlib.h>
// 双链表的节点
struct node
{
int data; // 有效数据
struct node *pPrev; // 前向指针，指向前一个节点
struct node *pNext; // 后向指针，指向后一个节点
};
struct node *create_node(int data)
{
struct node *p = (struct node *)malloc(sizeof(struct node));
if (NULL == p)
{
printf("malloc error.\n");
return NULL;
}
p->data = data;
p->pPrev = NULL;
p->pNext = NULL; // 默认创建的节点前向后向指针都指向NULL
return p;
}
// 将新节点new插入到链表pH的尾部
void insert_tail(struct node *pH, struct node *new)
{
// 第一步先走到链表的尾节点
struct node *p = pH;
while (NULL != p->pNext)
{
p = p->pNext; // 第一次循环走过了头节点
}
// 循环结束后p就指向了原来的最后一个节点
// 第二步：将新节点插入到原来的尾节点的后面
p->pNext = new; // 后向指针关联好了。新节点的地址和前节点的next
new->pPrev = p; // 前向指针关联好了。新节点的prev和前节点的地址
// 前节点的prev和新节点的next指针未变动
}
int main(void)
{
struct node *pHeader = create_node(0); // 头指针
insert_tail(pHeader, create_node(7));
insert_tail(pHeader, create_node(8));
insert_tail(pHeader, create_node(9));
// 遍历
printf("node 1 data: %d.\n", pHeader->pNext->data);
printf("node 2 data: %d.\n", pHeader->pNext->pNext->data);
printf("node 3 data: %d.\n", pHeader->pNext->pNext->pNext->data);
struct node *p = pHeader->pNext->pNext->pNext; // p指向了最后一个节点
printf("node 3 data: %d.\n", p->data);
printf("node 2 data: %d.\n", p->pPrev->data);
printf("node 1 data: %d.\n", p->pPrev->pPrev->data);
return 0;
}演示效果：
3、在链表内容插入一个元素（还是看图说话）：
#include <stdio.h>
#include <stdlib.h>
// 双链表的节点
struct node
{
int data; // 有效数据
struct node *pPrev; // 前向指针，指向前一个节点
struct node *pNext; // 后向指针，指向后一个节点
};
struct node *create_node(int data)
{
struct node *p = (struct node *)malloc(sizeof(struct node));
if (NULL == p)
{
printf("malloc error.\n");
return NULL;
}
p->data = data;
p->pPrev = NULL;
p->pNext = NULL; // 默认创建的节点前向后向指针都指向NULL
return p;
}
// 将新节点new插入到链表pH的尾部
void insert_tail(struct node *pH, struct node *new)
{
// 第一步先走到链表的尾节点
struct node *p = pH;
while (NULL != p->pNext)
{
p = p->pNext; // 第一次循环走过了头节点
}
// 循环结束后p就指向了原来的最后一个节点
// 第二步：将新节点插入到原来的尾节点的后面
p->pNext = new; // 后向指针关联好了。新节点的地址和前节点的next
new->pPrev = p; // 前向指针关联好了。新节点的prev和前节点的地址
// 前节点的prev和新节点的next指针未变动
}
// 将新节点new前插入链表pH中。
// 算法参照图示进行连接，一共有4个指针需要赋值。注意的是顺序。
void insert_head(struct node *pH, struct node *new)
{
// 新节点的next指针指向原来的第1个有效节点的地址
new->pNext = pH->pNext;
// 原来第1个有效节点的prev指针指向新节点的地址
if (NULL != pH->pNext)
pH->pNext->pPrev = new;
// 头节点的next指针指向新节点地址
pH->pNext = new;
// 新节点的prev指针指向头节点的地址
new->pPrev = pH;
}
int main(void)
{
struct node *pHeader = create_node(0); // 头指针
insert_head(pHeader, create_node(7));
insert_head(pHeader, create_node(8));
insert_head(pHeader, create_node(9));
// 遍历
printf("node 1 data: %d.\n", pHeader->pNext->data);
printf("node 2 data: %d.\n", pHeader->pNext->pNext->data);
printf("node 3 data: %d.\n", pHeader->pNext->pNext->pNext->data);
struct node *p = pHeader->pNext->pNext->pNext; // p指向了最后一个节点
printf("node 3 data: %d.\n", p->data);
printf("node 2 data: %d.\n", p->pPrev->data);
printf("node 1 data: %d.\n", p->pPrev->pPrev->data);
return 0;
}
代码演示结果：
三、小结：
以上代码链接：https://github.com/1121518wo/linux-/tree/master
对于双链表内部元素插入操作，这里有一个地方需要注意，是和单向链表不同的地方，单向链表在插入节点的时候不需要判断最后一个节点是否为空，因为这不影响程序的结果，但是对于双向链表就不一样了，因为我们后面要用到最后一个节点的一个指针指向前一个节点，如果最后一个节点是空的话（就是程序中的），就不存在p->pNext了,那么程序运行到这里时就会报错，所以我们要加个判断，判断此时节点是NULL的话就不需要控制它的指针了。好了今天的分享就到这里了，后期还有双链表的删除和遍历操作都会写到甚至Linux内核链表的内容也会分享给大家的。
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-11-01，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号