單向鍊表的操作，單向鍊表的結構

單向鍊表是一種鏈式訪問資料結構，它將資料元素儲存在一組具有任意位址的儲存單元中的線性表中。 鍊表中的資料由節點表示，每個節點由：元素（資料元素的影象）+指標（表示後繼元素的儲存位置）組成，元素是儲存資料的儲存單元，指標是連線每個節點的位址資料。

單向鍊表簡介。

1.概念介紹。

鍊表中的資料由節點表示，每個節點由：元素（資料元素的影象）+指標（表示後繼元素的儲存位置）組成，元素是儲存資料的儲存單元，指標是連線每個節點的位址資料。

表示為“節點序列”的線性表稱為線性鍊表（單鏈表），單鏈表是鏈式訪問結構。

2.鏈結的儲存方法。

以鏈結模式儲存的線性表稱為鍊表。

鍊表的具體儲存表示為：

使用任意一組記憶體單元來儲存線性表的節點（這組單元可以是連續的，也可以是不連續的）。

鍊表中節點的邏輯順序和物理順序不一定相同。 為了正確表示節點之間的邏輯關係，必須將每個節點的值與指示其後續節點的位址（或位置）資訊（稱為指標或鏈結）一起儲存

鏈式儲存是最常用的儲存方式之一，它不僅可以用於表示線性表，還可以表示各種非線性資料結構。

3.節點結構。

資料字段 - 儲存節點值的資料字段。

Next Domain - 乙個指標域（鏈域），用於儲存節點的直接繼承者的位址（位置）

鍊表通過每個節點的鏈域，將線性表的n個節點按邏輯順序鏈結在一起，每個節點只有乙個鏈域的鍊表稱為單個鍊表。

磁頭、指標頭和終端節點。

單鏈表中每個節點的儲存位址都儲存在其前置節點的下乙個欄位中，並且起始節點沒有前置節點，因此應將頭指標設定為指向起始節點。 鍊表由頭指標唯一確定，單個鍊表可以由頭指標的名稱命名。

終端節點沒有後繼節點，因此終端節點的指標欄位為空，即 null。

3.節點結構。

插入操作（ ） 思想方法 插入操作是將乙個值為 x 的新節點插入到狀態表中第 i 個節點的位置，即插入 ai 和 ai 之間 具體步驟 （ 找到 AI 儲存位置 p （ 生成乙個資料字段為 x*s （ 使節點 *p 的指標字段指向新節點 （ 指標欄位新節點指向節點 AI

具體的插入過程顯示在動畫中

具體演算法實現void insertlist（linklist head datatype x int i）。

演算法分析：演算法的時間主要花在查詢操作getnode上，所以時間複雜度也是o（n）。

刪除操作（ ） 思想方法 刪除操作是刪除表的第 i 個節點 具體步驟 （ 找到 ai p 的儲存位置（因為在單鏈表中，節點 ai 的儲存位址在其直接前身節點 ai next 的指標欄位中） （使 p next 指向 ai 的直接後繼節點（即 從鏈中移除 AI）（釋放節點 AI 的空間並將其返回到儲存池。

具體操作流程請參見動畫

具體演算法實現void deletelist（linklist head int i） 注意：設單鏈表的長度為n，則第i個節點的刪除只有在i n時才有效 當i=n+時 雖然刪除的節點不存在，但其轉發節點存在 它是終端節點 因此，刪除節點的直接轉發 *p 的存在並不意味著刪除的節點必須存在如果 *p 存在（即 p！ =null），並且 *p 不是終端節點（即 p next！ =null） 來確定已刪除節點是否存在。

<>2.鍊表類的實現：建構函式、悔恨插入函式、刪除函式，判斷是否為空函式。

3. 建構函式的實現：定義頭部指標。

4、插入功能的實現思路：首先確定是否插入。

<>6.判斷是否為空的實現思路：判斷頭節點是否為0。

只要看看指標的書，了解指標、位址和記憶體的分配。

線性表的n個節點通過每個節點的鏈域按邏輯順序鏈結在一起，如果鍊表的每個節點只有乙個鏈結域，則這種鍊表稱為單鏈表。

單鏈表中每個節點的儲存位址都儲存在其前置節點的指標域中，起始節點沒有前置節點，所以頭指標應設定為指向起始節點，終端節點沒有後繼節點，因此終端節點的指標域為空， 即 null（如圖所示）。單向鍊表的結構如圖 1 和圖 2 所示。

圖 1：沒有頭節點的單鏈表示含義。

圖 2：表示前導節點的單鏈表示。

有兩個鍊表LA（A1，A2,...，an） 和 lb （b1，b2,...bm），討論以下問題：

1）LA和LB都是單鏈表，帶線索指標，衝渣後LB到LA怎麼連線？時間複雜度是多少？

答：從la的頭節點開始，將指標移動到單鏈表的最後乙個節點，即移動長度為la的節點數，最後在la之後連線LB，所以時間複雜度為o（n）。

2）LA和LB都是帶有前導節點的單週期鍊表，LA之後如何連線LB形成迴圈鍊表？

時間複雜度是多少？

答：先從LA的頭指標開始，將指標移動到圓形鍊表的最後乙個節點，移動LA長度的節點數，將指標從LB的頭指標中移動，將指標移動到LB鍊表的最後乙個節點，移動LB長度的節點數， 最後連線LB在LA之後形成乙個圓鏈，如純湮滅臺，時間複雜度為O（N M）。

2）LA和LB都是帶有頭節點和尾指標的單週期鍊表，如何實現LB與LA相連，在LA之後形成乙個迴圈鍊表？時間複雜度是多少？

答：LA和LB都是有頭節點和尾指標的單週期鍊表，只需要將LA表的尾部和LB的頭連線起來，形成乙個迴圈鍊表，所以時間複雜度為O（1）。