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

链表的初始化初始化主要完成以下工作：创建一个单链表的前置节点并向后逐步添加节点，一般指的是申请结点的空间，同时对一个结点赋空值，其代码可以表示为：
LinkedList listinit{
Node *L;
L=(Node*)malloc(sizeof(Node)); //开辟空间
if(L==){ //判断是否开辟空间失败，这一步很有必要
printf("申请空间失败");
//exit(0); //开辟空间失败可以考虑直接结束程序
}
L->next=; //指针指向空
}
注意：一定要判断是否开辟空间失败，否则生产中由于未知的情况造成空间开辟失败，仍然在继续执行代码，后果将不堪设想啦，因此养成这样的判断是很有必要的。

头插入法创建单链表利用指针指向下一个结点元素的方式进行逐个创建，使用头插入法最终得到的结果是逆序的。如图所示：

文章插图
从一个空表开始，生成新结点，并将读取到的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后。
//头插法建立单链表
LinkedList LinkedListCreatH {
Node *L;
L = (Node *)malloc(sizeof(Node)); //申请头结点空间
L->next = ; //初始化一个空链表
int x; //x为链表数据域中的数据
while(scanf("%d",&x) != EOF) {
Node *p;
p = (Node *)malloc(sizeof(Node)); //申请新的结点
p->data = https://www.isolves.com/it/cxkf/bk/2020-08-31/x; //结点数据域赋值
p->next = L->next; //将结点插入到表头L-->|2|-->|1|-->
L->next = p;
}
return L;
}

尾插入法创建单链表如图所示为尾插入法的创建过程。

文章插图
头插法生成的链表中，结点的次序和输入数据的顺序不一致。若希望两者次序一致，则需要尾插法。
该方法是将新结点逐个插入到当前链表的表尾上，为此必须增加一个尾指针r, 使其始终指向当前链表的尾结点，代码如下：
  //尾插法建立单链表
LinkedList LinkedListCreatT {
Node *L;
L = (Node *)malloc(sizeof(Node)); //申请头结点空间
L->next = ; //初始化一个空链表
Node *r;
r = L; //r始终指向终端结点，开始时指向头结点
int x; //x为链表数据域中的数据
while(scanf("%d",&x) != EOF) {
Node *p;
p = (Node *)malloc(sizeof(Node)); //申请新的结点
p->data = https://www.isolves.com/it/cxkf/bk/2020-08-31/x; //结点数据域赋值
r->next = p; //将结点插入到表头L-->|1|-->|2|-->
r = p;
}
r->next = ;
return L;
}

遍历单链表如打印、修改从链表的头开始，逐步向后进行每一个元素的访问，称为遍历。
对于遍历操作，我们可以衍生出很多常用的数据操作，比如查询元素，修改元素，获取元素个数，打印整个链表数据等等。
进行遍历的思路极其简单，只需要建立一个指向链表L的结点，然后沿着链表L逐个向后搜索即可，代码如下：
  //便利输出单链表
void printList(LinkedList L){
Node *p=L->next;
int i=0;
while(p){
printf("第%d个元素的值为:%dn",++i,p->data);
p=p->next;
}
}
对于元素修改操作，以下是代码实现：
  //链表内容的修改，在链表中修改值为x的元素变为为k 。
LinkedList LinkedListReplace(LinkedList L,int x,int k) {
Node *p=L->next;
int i=0;
while(p){
if(p->data=https://www.isolves.com/it/cxkf/bk/2020-08-31/=x){
p->data=https://www.isolves.com/it/cxkf/bk/2020-08-31/k;
}
p=p->next;
}
return L;
}
简单的遍历设计的函数只需要void无参即可，而当涉及到元素操作时，可以设计一个LinkedList类型的函数，使其返回一个操作后的新链表。

插入操作链表的插入操作主要分为查找到第i个位置，将该位置的next指针修改为指向我们新插入的结点，而新插入的结点next指针指向我们i+1个位置的结点。
其操作方式可以设置一个前驱结点，利用循环找到第i个位置，再进行插入。
如图，在DATA1和DATA2数据结点之中插入一个NEW_DATA数据结点：
从原来的链表状态：
到新的链表状态：
代码实现如下：
  //单链表的插入，在链表的第i个位置插入x的元素