2.4.2 单链表上的基本运算
（1）初始化单链表。
（2）判断单链表是否为空。若单链表为空，返回1；否则返回0。
（3）按序号查找操作。从单链表的头指针head出发，利用结点的指针域依次扫描链表的结点，并进行计数，直至计数为i，就找到了第i个结点。如果查找成功，返回该结点的指针，否则返回NULL表示查找失败。
查找元素时，要注意判断条件p->next!=NULL，保证p的下一个结点不为空，如果没有这个条件，就无法保证执行循环体中的p=p->next语句。
（4）按内容查找，查找元素值为e的结点。从单链表中的头指针开始，依次与e比较，如果找到，则返回该元素结点的指针，否则返回NULL。
（5）定位操作。定位操作与按内容查找类似，只是返回的是该结点的序号。从单链表的头指针出发，依次访问每个结点，并将结点的值与e比较，如果相等，则返回该序号表示成功；如果没有与e值相等的元素，则返回0表示失败。
（6）在第i个位置插入元素e。插入成功返回1，否则返回0。
假设存储元素e的结点为p，要将p指向的结点插入pre和pre->next之间，根本不需要移动其他结点，只需要让p指向结点的指针和pre指向结点的指针做一点改变即可。即先把*pre的直接后继结点变成*p的直接后继结点，然后把*p变成*pre的直接后继结点，如图2-13所示，代码如下：
p->next=pre->next;
pre->next=p;
图2-13 在*pre结点之后插入新结点*p
注 意
插入结点的两行代码不能颠倒顺序。如果先进行pre->next=p，后进行p->next=pre->next操作，则第一条代码就会覆盖pre->next的地址，pre->next的地址就变成了p的地址，执行p->next=pre->next就等于执行p->next=p，这样pre->next就与上级断开了链接，造成尴尬的局面，如图2-14所示。
图2-14 插入结点代码顺序颠倒后，*（pre->next）结点与上级断开链接
如果要在单链表的第i个位置插入一个新元素e，首先需要在链表中找到其直接前驱结点，即第i-1个结点，并由指针pre指向该结点，如图2-15所示。然后申请一个新结点空间，由p指向该结点，将值e赋值给p指向结点的数据域，最后修改*p和*pre结点的指针域，如图2-16所示。这样就完成了结点的插入操作。
图2-15 找到第i个结点的直接前驱结点
图2-16 将新结点插入第i个位置
在单链表的第i个位置插入新数据元素e的算法实现如下：
（7）删除第i个结点。假设p指向第i个结点，要将*p结点删除，只需要绕过它的直接前驱结点的指针，使其直接指向它的直接后继结点，即可删除链表的第i个结点，如图2-17所示。
图2-17 删除*pre的直接后继结点
将单链表中第i个结点删除可分为3步，第一步找到第i个结点的直接前驱结点，即第i-1个结点，并用pre指向该结点，p指向其直接后继结点，即第i个结点，如图2-18所示；第二步将*p结点的数据域赋值给e；第三步删除第i个结点，即pre->next=p->next，并释放*p结点的内存空间。删除过程如图2-19所示。
图2-18 找到第i-1个结点和第i个结点
图2-19 删除第i个结点
删除第i个结点的算法实现如下：
注 意
在查找第i-1个结点时，要注意不可遗漏判断条件pre->next->next!=NULL，确保第i个结点非空。如果没有此判断条件，而pre指针指向了单链表的最后一个结点，在执行循环后的p=pre->next、*e=p->data操作时，p指针指向的是NULL指针域，就会产生致命错误。
（8）求表长操作。
