导言
顺序表是有缺点的，其中最大的缺点就是插入和删除时需要移动大量元素，这显然很浪费时间，这时候需要找另一种逻辑结构的线性表来替换它。
1. 链表存储结构
线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。每个数据元素除了存储数据外，还需要存储一个指示其直接后继的信息（即直接后继的存储位置）。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像，称为结点（Node）。
1.1 单链表
n个结点链构成一个链表，即为线性表的链式存储结构，因为连接的每个结点中只包含一个指针域，所以叫做单链表。
1.2 单链表存储结构代码描述
单链表中，我们在C语言中可用结构体来描述。
1 /*线性表的单链表存储结构*/ 2 typedef struct Node{ 3 int data; 4 struct Node *next; 5 6 }Node, *LinkList;
我们定义的结点结构如上，其中data是一个整型的数据域，next是一个Node*指针域，它们合并在一个结构体里表示一个Node结点。
1.3 单链表的操作
我们约定，头结点的序号为0，且头结点的数据域是有效数据域。
常见的单链表操作有创建，插入，删除，遍历，查找，销毁等，这些操作都是单链表最基础的部分，有了这些基础的操作就可以实现其他的操作，比如更新一个结点的数据，我们可以通过key值（比如结点的位置）来查找到某个结点，再修改里面的数据。
1.3.1 单链表的创建
1 void InitList(LinkList *head){ 2 *head = NULL; 3 }
这里只是单纯为了好理解，我们封装了单链表的头结点初始化，表示最开始创建的单链表是一个空链表。需要注意的是，由于我们采用函数参数来充当返回值，并且返回的是一个头结点head，是一个LinkList，所以我们需要把head的地址当做参数，其类型也就是LinkList*。
1.3.2 单链表的插入
1 /* 2 参数： 3 head -- 头结点的地址 4 node -- 插入结点的地址 5 index -- 结点要插入的位置 6 描述： 7 把一个结点node插入到单链表head的index个位置上。 8 返回值： 9 成功返回 OK，失败返回 ERROR。 10 */ 11 int ListInsert(LinkList *head, Node *node, int index){ 12 //如果链表为空，且要插入的位置是第0个节点 13 if(*head == NULL){ 14 if(index != 0){ 15 return ERROR; 16 } 17 *head = node; 18 return OK; 19 } 20 21 //如果链表不为空，且要插入的位置是第0个节点 22 if(index == 0){ 23 node->next = *head; 24 *head = node; 25 return OK; 26 } 27 28 //如果链表不为空，且要插入的位置是非第0个结点 29 Node *current_node = *head; 30 int count = 0; 31 while(current_node->next != NULL && count < index - 1){ 32 current_node = current_node->next; 33 count++; 34 } 35 36 if(count == index - 1){ 37 node->next = current_node->next; 38 current_node->next = node; 39 return OK; 40 }else{ 41 return ERROR; 42 } 43 }
首先，根据插入位置和是否是第一次插入，我们可以把单链表的插入情况分为有三种：
1）第一次插入且插入序号必须是为0；
2）非第一次插入且序号为0；
3）非第一次插入且序号不为0.
原文：https://www.cnblogs.com/ydqblogs/p/13713540.html