單鏈表的運算之插入運算

插入運算
（）思想方法
    　插入運算是將值為x的新結點插入到表的第i個結點的位置上即插入到ai與ai之間
具體步驟
    　（）找到ai存儲位置p
    　（）生成一個數據域為x的新結點*s
    　（）令結點*p的指針域指向新結點
    　（）新結點的指針域指向結點ai

具體插入過程【參見動畫演示】

（）具體算法實現
    void InsertList(LinkList headDataType xint i)
      {//將值為x的新結點插入到帶頭結點的單鏈表head的第i個結點的位置上
        ListNode *p;
        p=GetNode(headi);//尋找第i個結點
        if (p==NULL)//i<或i>n+時插入位置i有錯
           Error(position error)
        s=(ListNode *)malloc(sizeof(ListNode));
        s>data=x;s>next=p>next;p>next=s;
      }   

（）算法分析
    　算法的時間主要耗費在查找操作GetNode上故時間復雜度亦為O(n)

刪除運算
（）思想方法
   　 刪除運算是將表的第i個結點刪去
具體步驟
   　（）找到ai的存儲位置p（因為在單鏈表中結點ai的存儲地址是在其直接前趨結點ai的指針域next中）
   　（）令p＞next指向ai的直接後繼結點（即把ai從鏈上摘下）
   　（）釋放結點ai的空間將其歸還給存儲池

具體操作過程【參見動畫演示】

（）具體算法實現
    void DeleteList(LinkList headint i)
      {//刪除帶頭結點的單鏈表head上的第i個結點
         ListNode *p*r;
         p=GetNode(headi);//找到第i個結點
         if (p==NULL||p>next==NULL)//i<或i>n時刪除位置錯
              Error(position error);//退出程序運行
         r=p>next;//使r指向被刪除的結點ai
         p>next=r>next;//將ai從鏈上摘下
         free(r);//釋放結點ai的空間給存儲池
       }
注意
    　設單鏈表的長度為n則刪去第i個結點僅當≤i≤n時是合法的
   　 當i=n+時雖然被刪結點不存在但其前趨結點卻存在它是終端結點因此被刪結點的直接前趨*p存在並不意味著被刪結點就一定存在僅當*p存在（即p！=NULL）且*p不是終端結點（即p＞next！=NULL）時才能確定被刪結點存在

（）算法分析
    　算法的時間復雜度也是O（n）
    　鏈表上實現的插入和刪除運算無須移動結點僅需修改指針