單鏈表實現“插入”和“刪除”操作

   在單鏈表中，又如何實現“插入”和“刪除”操作呢？

插入操作：

   假設我們要在線性表的兩個數據元素a和b之間插入一個數據元素x，已知p為其單鏈表存儲結構中指向結點a的指針。為插入數據元素x，首先要生成一個數據域為x的結點，然后插入在單鏈表中。根據插入操作的邏輯定義，還需修改結點a中的指針域，令其指向結點x，而結點x中的指針域應該指向b結點，從而實現3個元素a，b和x之間邏輯關系的變化。

   假設s為指向結點x的指針。則上述指針修改用語句描述即為：

   s->next=p->next;

   p->next=s;

刪除操作：

   如果在線性表中刪除元素b時，為在單鏈表中實現元素a，b和c之間邏輯關系的變化，僅需要修改結點a中的指針域即可。假設p為指向結點a的指針，則修改指針的語句為：

   p->next=p->next->next;

  由以上可知，在已知鏈表中元素插入或刪除的確切位置的情況下，在單鏈表中插入或刪除一個結點時，僅需修改指針為不需要移動元素。

 插入函數ListInsert_L：要求是在已知鏈表中的確切位置插入一個結點。所以需要向函數內傳遞已知鏈表L，插入的確切位置i，以及即將插入的結點數據元素e。

  ListInsert_L(LinkList &L,int i,ElemType e)

{ 

  //第一步：將鏈表的頭結點的指針域單鏈表存儲結構的指針p

  p=L;//&L即為鏈表L的的頭結點地址

  j=0；//計數器

  //第二步：找到在將在鏈表i處，即要插入新結點的位置。

  //方法：先找到鏈表i-1處的結點。此結點的指針域即指向i處結點的指針域

 while(p&&j<i-1)

 {

  p=p->next;//p->next是指向第j+1個數據元素的指針

  ++j;//

 }

  //第三步：判斷是否越界已知鏈表

 //如果i小于1或者大于表長+1，即越界，則返回錯誤

 if(!p||j>i-1)

 return ERROP;

  //第四步：找到i出結點，新建一個結點(包括數據域和指針域)代表即將插入的結點

 //生成新結點

 s=(LinkList)malloc(sizeof(LNode));//新結點s

 s->data=e;//新結點的數據域賦值為將插入的數據元素e

 //因為原來i處結點指針域p保存著指向下一個i+1處結點的指針域。

 //要插入新結點，即原來i+1處的結點變為i+2處的幾點，新建結點變為i+1處的結點

 //即新建結點指向原來i+1處的結點的指針域，所以s->next=p->next

 //因為此時p代表的是i處的結點，p->代表i+1處的結點指針域賦值給新結點指針域

 s->next=p->next;

 //因為此時p代表的是i處的結點，p->next代表i+1處的結點指針域賦值給新結點指針域

  //完成插入操作時，新建結點s變為i+1處的結點。所以p->next指向s，即將s賦值給p->next.

 p->next=s;

 return OK;

}