单向链表的插入操作

插入一个数据元素为x的结点。已知q为指向结点a的指针，在具体实现插入操作时，首先要生成一个数据元素为x的结点，假设p为指向结点x的指针，然后使结点x的指针域指向结点b，操作语句为p->next=q->next；再使结点a的指针域指向结点x，操作语句为q->next=p；

在单向链表中插入结点示意图

要点：

首先要找到插入位置第i个结点的前驱结点(第i-1个结点)，程序中用指针变量q指向第i-1个结点。为使第i个结点作为新结点的直接后继，就要使新结点与第i个结点链接，然后再使第i-1个结点与新结点链接，使新结点作为第i-1个结点的直接后继。如果颠倒了顺序则会破坏原链表，而导致无法插入。

步骤：

用遍历法找到i结点的前驱(第i-1个结点)的指针，使新结点的指针域指向第i个结点，第i-1个结点的指针域指向新结点。

在单向链表的第i个结点之前插入新结点x的算法。(1≤i≤n+1)

带注解的完整程序：int insert(NODE *head,int x,int i){NODE *q,*p;int j;q=head;j=0;while((q!=NULL)&&(jnext;j++;} /*寻找第i-1个结点*/if(q==NULL) return(0); /*原链表为空 */p=(NODE *)malloc(sizeof(NODE));p->data=x; /*给新结点赋值*/p->next=q->next; /*输入*/q->next=p;return(1); /*返回正常输入的标志 ！*/}

单向链表的删除操作

要在一个带头结点的单向链表中，删除结点x。设x的直接前驱结点为a，直接后继结点为b，指针q指向结点a。删除方法是：令结点a的指针域(q->next)直接指向结点b，则结点x脱离了当前链表，然后将结点x的存储空间释放。操作时另设一个指针变量p，使它指向结点x，删除语句如下：

p=q->next；q->next=p->next;

上一个语句使p指向被删除结点，下一个语句使a结点的指针域指向x的后继结点b。

在单向链表删除结点的示意图

在具有头结点的单向链表中删除第i个结点。

带注解的完整程序：int delete(NODE *head,int i){NODE *p,*q;int j;q=head;j=0;while((q!=NULL)&&(jnext;}if(q==NULL)return(0);p=q->next; /*p指向要删除的第i个结点*/q->next=p->next;free(p);return(1);}