写在前面的话：正文开始 在单链表中，我们设了next指针，这使得我们查找下一个结点的时间复杂度为O(1)，但是如果我们想要查找的是上一个结点，那么最坏的时间复杂度为O(n)，因为我们每次都要从头开始遍历查找。
- 版权声明：本文为博主原创文章，转载请注明出处！
- 博主是一个小菜鸟，并且非常玻璃心！如果文中有什么问题，请友好地指出来，博主查证后会进行更正，啾咪~~
- 每篇文章都是博主现阶段的理解，如果理解的更深入的话，博主会不定时更新文章。
- 本文最后更新时间：2020.4.30
为了克服单向性这一缺点，便有人设计出了双向链表。双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。
【C/C++|【链表】双向链表（双向循环链表）】双向循环链表中的指针都是成对出现的：你的next指向我，我的prior指向你。
1. 定义数据结构
/* =================
定义链表数据结构
================= */
struct node
{
int num;
struct node *prior;
//prior存放上一个结点的地址
struct node *next;
//next存放下一个结点的地址
};
2. 设头结点
#include
#include /* =================
定义链表数据结构
================= */
struct node
{
int num;
struct node *prior;
//prior存放上一个结点的地址
struct node *next;
//next存放下一个结点的地址
};
typedef struct node Node;
typedef Node * Dlink;
/* ===============
功能：设头结点
返回：void
=============== */
void init_d_link(Dlink *head)
{
*head = (Dlink)malloc(sizeof(Node));
//为头结点分配空间(*head)->prior = *head;
(*head)->next = *head;
}int main()
{
Dlink head;
init_d_link(&head);
return 0;
}
3. 插入 3.1 头插
#include
#include /* =================
定义链表数据结构
================= */
struct node
{
int num;
struct node *prior;
//prior存放上一个结点的地址
struct node *next;
//next存放下一个结点的地址
};
typedef struct node Node;
typedef Node * Dlink;
/* ===============
功能：设头结点
返回：void
=============== */
void init_d_link(Dlink *head)
{
*head = (Dlink)malloc(sizeof(Node));
//为头结点分配空间(*head)->prior = *head;
(*head)->next = *head;
}/* =====================
功能：从头部插入结点
返回：void
===================== */
void insert_head_node(Dlink newnode,Dlink head)
{
newnode->next = head->next;
head->next->prior = newnode;
head->next = newnode;
newnode->prior = head;
}/* ================
功能：打印链表
返回：void
================ */
void display_link(Dlink head)
{
Dlink temp = head->next;
while (temp != head)//遍历链表
{
printf("%d\n", temp->num);
temp = temp->next;
}
}int main()
{
Dlink head;
Dlink newnode;
init_d_link(&head);
for (int i = 0;
i < 10;
i++)
{
newnode = (Dlink)malloc(sizeof(Node));
//为结点分配空间
newnode->num = i + 1;
//为结点数据域赋值
insert_head_node(newnode, head);
//头插
}printf("头插后的链表为 : \n");
display_link(head);
//打印链表return 0;
}
运行结果：
头插后的链表为 :
10
9
8
7
6
5
4
3
2
1
3.2 尾插
#include
#include /* =================
定义链表数据结构
================= */
struct node
{
int num;
struct node *prior;
//prior存放上一个结点的地址
struct node *next;
//next存放下一个结点的地址
};
typedef struct node Node;
typedef Node * Dlink;
/* ===============
功能：设头结点
返回：void
=============== */
void init_d_link(Dlink *head)
{
*head = (Dlink)malloc(sizeof(Node));
//为头结点分配空间(*head)->prior = *head;
(*head)->next = *head;
}/* =====================
功能：从尾部插入结点
返回：void
===================== */
void insert_tail_node(Dlink newnode, Dlink head)
{
head->prior->next = newnode;
newnode->prior = head->prior;
newnode->next = head;
head->prior = newnode;
}/* ================
功能：打印链表
返回：void
================ */
void display_link(Dlink head)
{
Dlink temp = head->next;
while (temp != head)//遍历链表
{
printf("%d\n", temp->num);
temp = temp->next;
}
}int main()
{
Dlink head;
Dlink newnode;
init_d_link(&head);
for (int i = 0;
i < 10;
i++)
{
newnode = (Dlink)malloc(sizeof(Node));
//为结点分配空间
newnode->num = i + 1;
//为结点数据域赋值
insert_tail_node(newnode, head);
//尾插
}printf("尾插后的链表为 : \n");
display_link(head);
//打印链表return 0;
}
运行结果：
尾插后的链表为 :
1
2
3
4
5
6
7
8
9
10
3.3 从中间插入
#include
#include /* =================
定义链表数据结构
================= */
struct node
{
int num;
struct node *prior;
//prior存放上一个结点的地址
struct node *next;
//next存放下一个结点的地址
};
typedef struct node Node;
typedef Node * Dlink;
/* ===============
功能：设头结点
返回：void
=============== */
void init_d_link(Dlink *head)
{
*head = (Dlink)malloc(sizeof(Node));
//为头结点分配空间(*head)->prior = *head;
(*head)->next = *head;
}/* =====================
功能：从尾部插入结点
返回：void
===================== */
void insert_tail_node(Dlink newnode, Dlink head)
{
head->prior->next = newnode;
newnode->prior = head->prior;
newnode->next = head;
head->prior = newnode;
}/* =====================
功能：从中间插入结点
返回：是否成功
===================== */
int insert_mid_node(Dlink newnode, Dlink head,int num)
{
Dlink temp = head->next;
while (temp != head)//遍历链表
{
if (temp->num == num)//判断是否是要找的结点
{
newnode->next = temp->next;
temp->next->prior = newnode;
temp->next = newnode;
newnode->prior = temp;
return 0;
}
temp = temp->next;
}return -1;
}/* ================
功能：打印链表
返回：void
================ */
void display_link(Dlink head)
{
Dlink temp = head->next;
while (temp != head)//遍历链表
{
printf("%d\n", temp->num);
temp = temp->next;
}
}int main()
{
Dlink head;
Dlink newnode;
init_d_link(&head);
for(int i = 0;
i < 10;
i++)
{
newnode = (Dlink)malloc(sizeof(Node));
//为结点分配空间
newnode->num = i + 1;
//为结点数据域赋值
insert_tail_node(newnode, head);
//尾插
}newnode = (Dlink)malloc(sizeof(Node));
//为新结点分配空间
newnode->num = 11;
//数据域赋值
insert_mid_node(newnode, head, 5);
//在数据域为5的结点后插入新结点printf("从中间插入后的链表为 : \n");
display_link(head);
//打印链表return 0;
}
运行结果：
从中间插入后的链表为 :
1
2
3
4
5
11
6
7
8
9
10
4. 删除结点
#include
#include /* =================
定义链表数据结构
================= */
struct node
{
int num;
struct node *prior;
//prior存放上一个结点的地址
struct node *next;
//next存放下一个结点的地址
};
typedef struct node Node;
typedef Node * Dlink;
/* ===============
功能：设头结点
返回：void
=============== */
void init_d_link(Dlink *head)
{
*head = (Dlink)malloc(sizeof(Node));
//为头结点分配空间(*head)->prior = *head;
(*head)->next = *head;
}
/* =====================
功能：从尾部插入结点
返回：void
===================== */
void insert_tail_node(Dlink newnode, Dlink head)
{
head->prior->next = newnode;
newnode->prior = head->prior;
newnode->next = head;
head->prior = newnode;
}
/* ===============
功能：删除结点
返回：是否成功
=============== */
int delete_node(int num, Dlink head)
{
Dlink temp = head->next;
while (temp != head)//遍历链表
{
if (temp->num == num)//判断是否是要删除的结点
{
temp->prior->next = temp->next;
temp->next->prior = temp->prior;
free(temp);
//释放
temp = NULL;
//置空
return 0;
}
temp = temp->next;
}
return -1;
}
/* ================
功能：打印链表
返回：void
================ */
void display_link(Dlink head)
{
Dlink temp = head->next;
while (temp != head)//遍历链表
{
printf("%d\n", temp->num);
temp = temp->next;
}
}
int main()
{
Dlink head;
Dlink newnode;
init_d_link(&head);
for(int i = 0;
i < 10;
i++)
{
newnode = (Dlink)malloc(sizeof(Node));
//为结点分配空间
newnode->num = i + 1;
//为结点数据域赋值
insert_tail_node(newnode, head);
//尾插
}delete_node(7, head);
//删除数据域为7的结点printf("删除数据域为7的结点后的链表为 : \n");
display_link(head);
//打印链表
return 0;
}
运行结果：
删除数据域为7的结点后的链表为 :
1
2
3
4
5
6
8
9
10
相关文章 【链表】单链表：不带表头结点
【链表】单链表：带表头结点
【链表】单链表：单循环链表
推荐阅读
- c/c++|知无涯之回车换行的故事
- 浙大版《C语言程序设计》第四版(何钦铭颜晖) 第8章 指针 课后习题答案
- C/C++基础知识
- 浙大版《C语言程序设计》第四版(何钦铭颜晖) 第7章 数组 课后习题答案
- 浙大版《C语言程序设计》第四版(何钦铭颜晖) 第6章 回顾数据类型和表达式 课后习题答案
- 数据结构|希尔排序——直插排序的更好优化
- c/c++|三对角矩阵的压缩
- c/c++递归打印文件夹
- 图像处理原理|详解C++标准库＜sstream＞中的类stringstream,并利用它实现OpenCV下的图片批量读取