線性表 - 鏈式存儲結構- 單鏈表的運算（五）

　　插入運算

　　()思想方法

　　插入運算是將值為x的新結點插入到表的第i個結點的位置上即插入到a i 與a i 之間

　　具體步驟

　　()找到a i 存儲位置p

　　()生成一個數據域為x的新結點*s

　　()令結點*p的指針域指向新結點

　　()新結點的指針域指向結點a i

　　

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

　　()具體算法實現

　　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個結點刪去

　　具體步驟

　　()找到a i 的存儲位置p(因為在單鏈表中結點a i 的存儲地址是在其直接前趨結點a i 的指針域next中)

　　()令p>next指向a i 的直接後繼結點(即把a i 從鏈上摘下)

　　()釋放結點a i 的空間將其歸還給存儲池

　　

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

　　()具體算法實現

　　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指向被刪除的結點a i

　　p>next=r>next;//將a i 從鏈上摘下

　　free(r);//釋放結點a i 的空間給存儲池

　　}

　　注意

　　設單鏈表的長度為n則刪去第i個結點僅當≤i≤n時是合法的

　　當i=n+時雖然被刪結點不存在但其前趨結點卻存在它是終端結點因此被刪結點的直接前趨*p存在並不意味著被刪結點

　　就一定存在僅當*p存在(即p!=NULL)且*p不是終端結點(即p>next!=NULL)時才能確定被刪結點存在

　　()算法分析

　　算法的時間復雜度也是O(n)

　　鏈表上實現的插入和刪除運算無須移動結點僅需修改指針

From:http://tw.wingwit.com/Article/program/sjjg/201311/23306.html