關于數據結構雙向鏈表中插入節點的核心步驟探討

雍巧玲

（喀什大學計算機科學與技術學院,新疆 喀什 844000）

1 引言

隨著社會的發展和科技的進步，計算機已被廣泛應用。由于計算機計算速度快，存儲容量大，使用方便，用途廣，給科技發展助力不少，不少高校設置了計算機相關專業及相關課程。其中，“數據結構”是計算機專業課程中的一門核心基礎課程，課程內容包含了數據的各種存儲結構和組織數據的方式。在數據結構中，雙向鏈表是一種典型的數據存儲結構，也是教學當中的重點案例。目前，在出版的一些數據結構相關教材中，對于雙向鏈表中節點插入的講解示例中，大多數只展示了指針方向變化的一種順序[1-4]。在雙向鏈表中，每一個節點都帶有兩個指針域和一個數據域[5]。在鏈表中，每插入一個節點，會有四個指針的指向發生變化，按照一定的操作順序，就能完成節點的插入工作。

2 雙向鏈表節點插入算法描述

2.1 基于雙向鏈表節點的類型定義

在雙向鏈表中，一個節點包括一個數據域、一個前驅和一個后繼，分別用data、prior和next表示。基于雙向鏈表的節點類型C語言模板如下[1]：

2.2 基于雙向鏈表的節點前插入算法

在雙向鏈表插入節點算法中，在第i個節點前（后）插入一個值為e的新節點s，第i個節點位置的定位可以在鏈表中從左向右方向查找到，也可以從右向左方向查找到。算法中，p為查找到的第i個節點，將待插入節點s插入到p節點之前，同時要修改s與p節點的前驅和后繼域的位置。

在鏈表中插入一個節點需要對各指針域做出修改，在單向鏈表中插入一個節點只需要對p和s兩個節點的后繼域的指向分別做出更改，而在雙向鏈表中，需要對p和s兩個節點的前驅和后繼共四個指針的指向分別做出更改。四個指針的變動，有四步操作語句，雙向鏈表前插入節點的指針變換步驟的核心C語言代碼如下[5]：

在上述代碼語句中，①②③④分別代表四個指針的變化。指針改變的具體步驟解析如下。

步驟①：將插入節點s的前驅指向插入位置節點p的前驅，即將指定節點的前驅指針作為新節點的前驅指針。

步驟②：將p的前驅的后繼域指向插入節點s，即調整新節點的前驅節點的后向指針。

步驟③：將插入節點s的后繼域指向了p節點，即將指定節點p作為新節點的后向指針。

步驟④：將p節點的前驅域指向s節點，即將新節點作為指定節點的前向指針。

通過測試，上述代碼的順序不唯一，但也不是任意的。

2.3 基于雙向鏈表的節點后插入算法

雙向鏈表中，節點后插入算法與節點前插入算法的不同之處是，節點前插入算法是將新節點插入指定節點p與前一節點之間，而節點后插入算法是將新節點插入指定節點p與后一個節點之間，其代碼執行語句也有所不同，但是同樣需要對p和s兩個節點的前驅和后繼共四個指針的指向分別做出更改。四個指針的變動，有四步操作語句，雙向鏈表后插入節點的指針變換步驟的核心C語言代碼如下：

在上述代碼語句中，①②③④分別代表四個指針的變化。指針改變的具體步驟解析如下：

步驟①：將插入節點s的后繼指向插入位置節點p的后繼，即將指定節點的后向指針作為新節點的后向指針；

步驟②：將p的next的prior域指向插入節點s，即調整p的next節點的前驅指針；

步驟③：將插入節點s的前驅域指向p節點，即將指定節點作為新節點的前向指針；

步驟④：將p的后繼域指向s節點，即將新節點作為指定節點的后向指針。

通過測試，上述代碼的順序不唯一，但也不是任意的。

3 算法實驗結果和分析

3.1 指針變化順序排列

由2.2小節和2.3小節可知，編號①②③④分別代表雙向鏈表中插入新節點的指針變化的四個操作步驟，雙向鏈表插入節點的核心步驟的所有排列組合有24種，本節將對其分別做實驗測試，其中，24種排列操作順序如表1所示。

表1 雙向鏈表插入節點步驟的24種排列順序

無論是節點前插入算法還是節點后插入算法，其4個操作步驟的排列順序都可由表1中的數據表示。本節需要注意的是，順序1分別代表2.2小節和2.3小節中出現的節點插入的順序，本文中也稱此順序為節點插入的標準順序。

3.2 實驗結果及分析

在本文中，實驗對節點前、后插入算法的24種不同的順序分別進行了測試，測試結果如下。

3.2.1 標準順序下的節點插入操作

對于表1中的順序1，無論是節點前插入算法還是節點后插入算法，均是教材中普遍出現的一種節點插入操作算法。在2.2小節和2.3小節中已給出其具體的C語言模板，其操作邏輯圖如圖1所示。

圖1 順序1節點插入操作圖

由圖1（a）可知，在元素a與b之間插入元素e，即在p節點之前插入s節點。在圖1中，由①②③④四條虛線箭頭和一個節點s完全替換a元素與b元素所屬節點之間的雙向實線箭頭，從而順利完成節點的前插入操作。由圖1（b）可知，p指向了a元素所屬節點，由于指定的p節點的位置不同，導致圖1（a）與圖1（b）中的虛線順序有所不同，其目的都是改變指針指向完成節點的插入。

使用節點前插入算法構建一個雙向鏈表，其中包含“a”“b”“c”三個字符元素。假設在第二個字符位置前插入元素“k”，插入元素之后，第二個位置的字符變更為“k”，原第二個位置及之后位置的字符依次往后順延一位，即原字符順序變為“akbc”。在實驗中，輸入“abc”三個字符構成雙向鏈表，以“$”符為結束標識符，然后輸入不同插入位置及插入元素“k”，插入節點后的鏈表結果如圖2所示。

圖2中的（a）—（c）分別代表第一、二和三個位置前插入元素“k”的實驗結果，插入結果分別為“kabc”“akbc”“abkc”，由于本實驗是節點前插入操作，所以無法實現在尾字符“c”之后插入元素節點。

使用節點后插入算法構建一個雙向鏈表，其中包含“a”“b”“c”三個字符元素。假設在第二個字符位置后插入元素“k”，插入元素之后，原第三個位置的字符變更為“k”，原第三個位置及之后位置的字符依次往后順延一位，即原字符順序變為“abkc”。在實驗中，輸入“abc”三個字符構成雙向鏈表，以“$”符為結束標識符，然后輸入不同插入位置及插入元素“k”，插入節點后的鏈表結果如圖3所示。

圖2 節點前插入結果實現圖

圖3 節點后插入結果實現圖

圖3中的（a）—（c）分別代表第一、二和三個位置后插入元素“k”的實驗結果，插入后的結果分別為“akbc”“abkc”“abck”，由于是節點后插入算法，所以無法實現在首字符“a”之前插入元素節點。

3.2.2 其他插入節點順序

參照標準順序1，在其基礎之上改變指針指向的運算順序，在表1中，節點前插入算法除了順序1，還有順序2、3、7、8、9、10、11、12、13、15和16，共計12種操作順序可以完成節點的前插入操作，在節點后插入算法中除了順序1，還有順序2、3、4、5、6、7、8、9、13、14和15，但這些操作順序在眾多教材中出現的示例并不多。

通過實驗測試，12種指針變化順序都能很好地完成新節點的插入操作，與標準順序1插入節點的效果一致。節點前插入算法插入節點結果實現圖與圖2完全一致，節點后插入算法插入節點結果實現圖與圖3完全一致。在本文中，經過代碼的實現和測試，算法都能夠很好地完成其在雙向鏈表中的節點前插入操作和后插入操作。

從上述歸納的12種操作順序中可以分析得出，在節點前插入算法中，語句④必須在語句②之后，在節點后插入算法中，語句④必須在語句①之后，否則無法完成雙向鏈表中的節點插入操作。

3.2.3 非法操作順序

對于節點前插入算法，若語句④在語句②之前，則程序先執行語句④“p->prior=s;”，后執行語句②“p->prior->next=s;”。例如操作順序“①④②③”，先執行語句“①④”，同時替換掉鏈L1，即鏈L1斷開。接著執行語句②，由于鏈L1已斷開，無法找到“p->prior”節點，即無法找到圖4（a）中a元素所屬節點，將無法完成節點的插入操作。若想將a元素所屬節點與s節點相連接，則執行語句“s->prior->next=s;”可以完成，但是這又違背了原代碼語句的描述。

其他節點前插入算法中，不能插入節點的操作順序的原理與以上所述一致。

對于節點后插入算法，若語句④在語句①之前，則程序先執行語句④“p->next=s;”，后執行語句①“s->next=p->next;”。例如操作順序“②③④①”，語句④在語句①之前，完成了p的后繼的指向，再執行語句①時，s的后繼只能指向自己，無法指向原p節點的后繼，即圖4（b）中b元素所屬的節點，從而無法完成節點的插入操作。

其他節點后插入算法中，不能插入節點的操作順序的原理與以上所述一致。

圖4 雙向鏈表節點插入指針替換圖

4 總結

本文描述了雙向鏈表中前、后插入節點的過程，其中，插入節點時四個指針的改變有不同的順序。經過實驗測試出，無論是節點前插入操作還是節點后插入操作，都有12種不同的操作順序，同時也有12種不成立的順序。從實驗結果中分析出，節點前插入算法中，步驟②必須要在語句④之前，節點后插入算法中，步驟①必須要在語句④之前，否則指針指向會發生錯誤，會丟失存儲的指針，從而導致算法無法完成節點插入。

在教學當中，可以讓學生深入學習雙向鏈表的節點類定義，以及鏈表的創建、節點的插入、刪除等操作。在實驗過程中，測試雙向鏈表插入節點的基準運算順序，同時也測試不同的運算順序，讓學生對這一知識點有更深入的了解和學習，可以拋出假設性問題，引起學生對這一知識點的好奇心和探究心理，激發學生的創新思維與學科交叉意識，從而提升學生的學習興趣，并學以致用，讓學生在不斷探究的過程中收獲知識，同時也可以加深其對知識點的記憶，從而達到由量變到質變的效果。