#数据结构#
数据结构的干货，我们已经介绍了一部分，学习了单链表的定义和如何创建单链表，接下来我们来学习如何实现单链表的基本操作，首先我们先来学习插入操作。
一、基本操作——插入操作
插入操作的三种方式
1、已知位序，按照位序，插入到单链表中
2、指定了结点，在对应节点之后进行插入操作
3、指定了结点，在对应节点之前进行插入操作
其中，按位序插入还分为带头节点与不带头结点两种。
零基础Python数据结构教程、源码及视频淘宝￥2购买已下架(1)按位序插入（带头结点）
在表L中的第i个位置上插入指定的元素e，也就是找到第i-1个结点，将新结点插入到该结点之后。
假设在第二个位置上插入新的元素，即找到下标为1的数据元素，将数据元素插入到该元素之后，并将未插入元素前的指针域连接到新元素，将下标为1的指针域连接到新元素。
假设在第一个位置上插入新元素，此时可以将头节点看成为第0个节点，则将新元素的指针域连接到第一个位置上的元素，将头结点的指针域连接到新元素上。
typedefstructLNode{
elemTypedata;
stryctLNode*next;
}LNode,*linklist;
boollistinsert(linklistL,inti,elemtypee)
{if(i1)//假设头节点为第0个节点，则i不能小于1
returnfalse;
LNode*p;//指针p指向当前位置所在的节点
intj=0;//表示当前p指向的是第几个节点
p=L;//L只想头节点，头节点相当于第0个节点，不存储数据
while(p!=NULLji-1)//执行while循环，找到i-1个结点
{p=p-next;
j++;}
if(p==NULL)//i的值不合法
returnfalse;
LNode*s=(LNode*)malloc(sizeof(LNode));//申请新的空间
s-data=e;//插入元素e存储到新申请空间的数据域
s-next=p-next;//将指针p原先所指向的指针域存储到新元素的指针域中※
p-next=s;//将原先指针p的指针域指向新元素，连接结点s到p之后
returntrue;//插入成功}
分析：
①当i=1时，即将数据元素插入到表头，此时，i-1=0，不满足指针p扫描条件，头节点不存储数据，此时的时间复杂度最好，为O(1)，要注意的是※行与行不能颠倒顺序；
②当i=3时，即将数据元素插入到表中，此时，i-1=2，执行while循环；
③当i=n时，即将数据元素插入到表尾，此时，i-1=n-1，执行while循环，最坏时间复杂度为O(n)；
④当ilength时，即数据元素所要插入的位置不在表内，此时指针指向为空，不合法。
小结论：在数据结构中，单链表按位序插入的时间复杂度，需要看所插入单链表的位置在哪，要保证数据元素插入位置合法，同时在插入数据元素时，要注意数据元素的连接，不能反向操作，不然单链表会直接断掉。
本文系作者授权百家号发表，未经许可，不得转载。