如何实现单链表的插入和删除操作

单链表插入：

（1）找到位置p（a_i-1）

（2）生成新结点s，数据域赋值

（3）新结点指针域指向ai（ai的地址存放在a_{i-1的指针域}）

（4）a_i-1的指针域指向新结点s

直接上代码：

Status InsertList(LinkList head,DataType x,int i)
{
    ListNode* p;
    p=head;
    int j=1;
    while(p && j<i)
    {
        p=p->next;
        j++;
    }    //p现在是ai-1这个结点
    if(!p || j>i)
    {
        printf("Position Error!");
        return ERROR;
    }
    ListNode* s=(ListNode*)malloc(sizeof(ListNode));
    s->data=x;
    s->next=p->next
    p->next=s;
    return OK;
}

删除单链表结点：

（1）找到要删除的结点前一个结点p（原因是删除结点的位置在前一个结点的指针域）

（2）把p->next指向ai的下一个结点（把ai从链上摘除）

（3）释放ai空间

直接粗暴上代码：

Status DeleteList（LinkList head，int i）
{
    ListNode* p，*r;   //声明两个指针，一个用来找到删除结点前的结点。    一个用来存储要删除结点的后继结点的地址的。
    p=head;
    int j=1;
    while(p->next && j<i)    //这里要判断p->next得是真（也就是说得有后继结点也就是要删除的结点）。。。//不要忘了这个方式  p=p->next;   指针在移动
    {
        p=p->next;
        j++;
    }
    if(p->next ==NULL || j>i)
    {
        printf("Position Error!");
        return ERROR;
    }
    r=p->next;       //把删除结点的首地址给临时结点     这样就能把删除结点的指针域保存下来   
    p->next=r->next;  //删除结点的指针域   指向   删除结点后继结点的首地址
    free(r);          //记得释放资源
    retuen OK;
}

删除结点必须保证在连边长度内。即1<=i<=n；

删除单链表头元素：

两步：（1）保存头元素的指针域（即头元素的后继节点的首地址）

（2）头结点指针域指向头元素的后继节点。

void RemoveHead（LinkList head）
{
    ListNode * p;
    p=head->next;
    head->next=p->next;
    free(p);
}