一口气搞懂「链表」，就靠这20+张图了( 三 ) _链表

LinkedList LinkedListInsert(LinkedList L,int i,int x) {
Node *pre; //pre为前驱结点
pre = L;
int tempi = 0;
for (tempi = 1; tempi < i; tempi++) {
pre = pre->next; //查找第i个位置的前驱结点
}
Node *p; //插入的结点为p
p = (Node *)malloc(sizeof(Node));
p->data = https://www.isolves.com/it/cxkf/bk/2020-08-31/x;
p->next = pre->next;
pre->next = p;
return L;
}

删除操作删除元素要建立一个前驱结点和一个当前结点，当找到了我们需要删除的数据时，直接使用前驱结点跳过要删除的结点指向要删除结点的后一个结点，再将原有的结点通过free函数释放掉。如图所示：

文章插图
代码如下：
//单链表的删除，在链表中删除值为x的元素
LinkedList LinkedListDelete(LinkedList L,int x) {
Node *p,*pre; //pre为前驱结点，p为查找的结点。
p = L->next;
while(p->data != x) { //查找值为x的元素
pre = p;
p = p->next;
}
pre->next = p->next; //删除操作，将其前驱next指向其后继。
free(p);
return L;
}
双向链表
双向链表的简介以及概念单链表是指结点中只有一个指向其后继的指针，具有单向性，但是有时需要搜索大量数据的时候，就需要多次进行从头开始的遍历，这样的搜索就不是很高效了。
在单链表的基础上，对于每一个结点设计一个前驱结点，前驱结点与前一个结点相互连接，构成一个链表，就产生了双向链表的概念了。
双向链表可以简称为双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

文章插图
双向链表示意图
一个完整的双向链表应该是头结点的pre指针指为空，尾结点的next指针指向空，其余结点前后相链。

双向链表的结点设计对于每一个结点而言，有：

文章插图
其中，DATA表示数据，其可以是简单的类型也可以是复杂的结构体；
pre代表的是前驱指针，它总是指向当前结点的前一个结点，如果当前结点是头结点，则pre指针为空；
next代表的是后继指针，它总是指向当前结点的下一个结点，如果当前结点是尾结点，则next指针为空
其代码设计如下：
typedef struct line{
int data; //data
struct line *pre; //pre node
struct line *next; //next node
}line,*a;
//分别表示该结点的前驱(pre)，后继(next)，以及当前数据(data)
双链表的创建
创建双向链表需要先创建头结点，然后逐步的进行添加双向链表的头结点是有数据元素的，也就是头结点的data域中是存有数据的，这与一般的单链表是不同的。
对于逐步添加数据，先开辟一段新的内存空间作为新的结点，为这个结点进行的data进行赋值，然后将已成链表的上一个结点的next指针指向自身，自身的pre指针指向上一个结点。
其代码可以设计为：
//创建双链表
line* initLine(line * head){
int number,pos=1,input_data;
//三个变量分别代表结点数量，当前位置，输入的数据
printf("请输入创建结点的大小n");
scanf("%d",&number);
if(number<1){return ;} //输入非法直接结束
//////头结点创建///////
head=(line*)malloc(sizeof(line));
head->pre=;
head->next=;
printf("输入第%d个数据n",pos++);
scanf("%d",&input_data);
head->data=https://www.isolves.com/it/cxkf/bk/2020-08-31/input_data;
line * list=head;
while (pos<=number) {
line * body=(line*)malloc(sizeof(line));
body->pre=;
body->next=;
printf("输入第%d个数据n",pos++);
scanf("%d",&input_data);
body->data=https://www.isolves.com/it/cxkf/bk/2020-08-31/input_data;
list->next=body;
body->pre=list;
list=list->next;
}
return head;
}
双向链表创建的过程可以分为：创建头结点->创建一个新的结点->将头结点和新结点相互链接->再度创建新结点，这样会有助于理解。

双向链表的插入操作如图所示：