自考資料結構：[8]線性表之?

線性表中 單鏈表運算包有 查詢、插入、刪除。

方法/步驟

查詢運算之按號查詢

如單鏈表的長度為n,要查詢第i個節點，需從頭開始順著連結串列查詢。

如圖解析

查詢運算之 按值查詢

查詢連結串列中是存在值等於給定值key的結點。如果有就返回其儲存位置，否則返回null。查詢由開始節點查詢，順著鏈逐個進行比較。

如圖解析

查詢運算之 插入運算

將值為x 的新結點插入到連結串列的第i個結點位置上，即插入到ai-1到ai之間。

思路：首先找到ai-1的儲存位置p，然後生成一個新的資料域為x的新結點*s，並令結點*p的指標域指向新結點，新結點的指標域指向ai。

演算法及圖解：

刪除運算 演算法

單鏈表中將表的第i個結點刪除。

思路：單鏈表中結點ai的儲存地址是在其直接前驅ai-1的指標域（next）中，首先需要找到ai-1的儲存位置p，然後將p->next指向ai的直接後繼。最後釋放ai的空間。

刪除運算。

單鏈表插入刪除運算優點：

不需要移動結點只需要修改指標（時間複雜度為0(n)）。