链表是一种链式存储结构，其特点是用一组任意的存储单元存储数据元素。链表最重要的概念是结点，一个结点表示链表中的一个数据元素，结点由储存数据元素的信息和存放指向下一个节点的的指针（单、双链表的最后一个节点除外，它们存储的是一个空指针NULL）两部分构成 。下面用C语言为大家讲解单链表的插入数据和删除数据操作。
1. 单链表的特点
（1）逻辑上相邻的元素在物理上不一定相邻。
（2）删除和插入操效率高，随机访问效率低。
2.单链表定义
typedef struct ListNode
{
type data; //数据域，type为数据的具体类型
struct ListNode *next; //指向下一个节点的指针
}ListNode, *LinkList;
3. 单链表基本操作
（1）插入数据
//将新元素插入到i位置
int ListInsert(ListNode list, int i, type newData)
{
LinkList p = list;
int j = 0;
while (NULL != p && j < i - 1)
{
p = p->next;
j++;
}
//找到插入位置
if (NULL != p && j == i - 1)
{
LinkList newNode = (LinkList)mallock(sizeof(ListNode));
newNode->data = newData;
newNode->next = p->next;
p->next = newNode;
return 0;
}
else
{ return -1;}
}
（2）删除数据
//删除第i个元素
void ListDelete(LinkList list, int i)
{
LinkList p = list;
int j = 0;
while (NULL != p && j < i - 1)
{
p = p->next;
j++;
}
if (NULL != p && j == i - 1 && p->next != NULL)
{
LinkList pdel = p->next;
p->next = pdel->next;
free(pdel);
return 0;
}
else
{ return -1;}
}
4.顺序表和单链表比较
（1）顺序表逻辑相邻的元素物理上也相邻，单链表逻辑相邻的元素物理上不一定相邻（用指针连接）
（2）顺序表随机访问元素时间复杂度为O(1)，单链表的为O(n)
（3）顺序表插入/删除元素的时间复杂度为O(n),，单链表插入/删除的时间复杂度为O(1)
该文图片均来自网络！今天我们就讲到这里，如果有问题欢迎大家评论哦！
