1. 双向链表的插入操作
如图所示：
对于每一次的双向链表的插入操作，我们首先需要创建一个独立的结点并通过malloc操作开辟相应的空间，其次我们选中这个新创建的独立节点，将其的pre指针指向所需插入位置的前一个结点，同时，其所需插入的前一个结点的next指针修改指向为该新的结点，同理，该新的结点的next指针将会指向一个原本的下一个结点，而修改下一个结点的pre指针为指向新结点自身，这样的一个操作我们称之为双向链表的插入操作。
其代码可以表示为：
//插入数据
line * insertLine(line * head,int data,int add){
//三个参数分别为：进行此操作的双链表，插入的数据，插入的位置
//新建数据域为data的结点
line * temp=(line*)malloc(sizeof(line));
temp->data=data;
temp->pre=NULL;
temp->next=NULL;
//插入到链表头，要特殊考虑
if (add==1) {
temp->next=head;
head->pre=temp;
head=temp;
}else{
line * 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;
}2. 双向链表的删除操作
如图：
删除操作的过程是：选择需要删除的结点，选中这个结点的前一个结点，将前一个结点的next指针指向自己的下一个结点，同时，选中该节点的下一个结点，将下一个结点的pre指针修改指向为自己的上一个结点，这样产生的效果就是在进行遍历的时候直接将这一个结点给跳过了。
在这样的指针修改操作之后，我们释放删除结点，归还空间给内存，这样的操作我们称之为双链表的删除操作。
其代码可以表示为：
//删除元素
line * deleteLine(line * head,int data){
//输入的参数分别为进行此操作的双链表，需要删除的数据
line * list=head;
//遍历链表
while (list) {
//判断是否与此元素相等
//删除该点方法为将该结点前一结点的next指向该节点后一结点
//同时将该结点的后一结点的pre指向该节点的前一结点
if (list->data==data) {
list->pre->next=list->next;
list->next->pre=list->pre;
free(list);
printf("--删除成功--\n");
return head;
}
list=list->next;
}
printf("Error:没有找到该元素，没有产生删除\n");
return head;
}3 双向链表的遍历
如同单链表的遍历一样，利用next指针逐步向后进行索引即可，注意判断这里，我们既可以用while(list)的操作直接判断是否链表为空，也可以使用while(list->next)的操作判断该链表是否为空，其下一节点为空和本结点是否为空的判断条件是一样的效果，当然了，善用双向链表的pre指针进行有效的遍历也是值得去尝试的。
其简单的代码可以表示为：
//遍历双链表,同时打印元素数据
void printLine(line *head){
line *list = head;
int pos=1;
while(list){
printf("第%d个数据是:%d\n",pos++,list->data);
list=list->next;
}
}4. 配套练习题目
双向链表的单独训练数据并不是很多，在网上的资料相比单链表也是偏少，不过我们在熟悉原理之后可以同单链表的题目，可以尝试使用双链表进行做题，如下题：
5. 本题目案例代码
#include<stdio.h>
#include<stdlib.h>
typedef struct line{
int data; //data
struct line *pre; //pre node
struct line *next; //next node
}line;
//分别表示该结点的前驱(pre)，后继(next)，以及当前数据(data)
//遍历双链表,同时打印元素数据
void printLine(line *head){
line *list = head;
int pos=1;
while(list){
printf("第%d个数据是:%d\n",pos++,list->data);
list=list->next;
}
}
//创建双链表
line* initLine(line * head){
int number,pos=1,input_data;
printf("请输入创建结点的大小\n");
scanf("%d",&number);
if(number<1){return NULL;} //输入非法直接结束
//////头结点创建///////
head=(line*)malloc(sizeof(line));
head->pre=NULL;
head->next=NULL;
printf("输入第%d个数据\n",pos++);
scanf("%d",&input_data);
head->data=input_data;
line * list=head;
while (pos<=number) {
line * body=(line*)malloc(sizeof(line));
body->pre=NULL;
body->next=NULL;
printf("输入第%d个数据\n",pos++);
scanf("%d",&input_data);
body->data=input_data;
list->next=body;
body->pre=list;
list=list->next;
}
return head;
}
//插入数据
line * insertLine(line * head,int data,int add){
//三个参数分别为：进行此操作的双链表，插入的数据，插入的位置
//新建数据域为data的结点
line * temp=(line*)malloc(sizeof(line));
temp->data=data;
temp->pre=NULL;
temp->next=NULL;
//插入到链表头，要特殊考虑
if (add==1) {
temp->next=head;
head->pre=temp;
head=temp;
}else{
line * 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;
}
//删除元素
line * deleteLine(line * head,int data){
//输入的参数分别为进行此操作的双链表，需要删除的数据
line * list=head;
//遍历链表
while (list) {
//判断是否与此元素相等
//删除该点方法为将该结点前一结点的next指向该节点后一结点
//同时将该结点的后一结点的pre指向该节点的前一结点
if (list->data==data) {
list->pre->next=list->next;
list->next->pre=list->pre;
free(list);
printf("--删除成功--\n");
return head;
}
list=list->next;
}
printf("Error:没有找到该元素，没有产生删除\n");
return head;
}
int main(){
line *head=NULL;
printf("创建双链表操作\n");
head=initLine(head);
printLine(head);
//////////create line////////////
printf("插入操作\n");
head=insertLine(head,40,2); //为了简化直接写参数了
printLine(head);
//////////insert Line////////////
printf("删除操作\n");
head=deleteLine(head,2); //为了简化直接写参数了
printLine(head);
//////////delete Line////////////
return 0;
}
| 1585 | 蓝桥杯算法训练VIP-链表数据求和操作 |
| 1676 | 数据结构-链表的基本操作 |
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程