關(guān)于數(shù)據(jù)結(jié)構(gòu)雙向鏈表中插入節(jié)點(diǎn)的核心步驟探討

雍巧玲

（喀什大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院,新疆 喀什 844000）

1 引言

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

2 雙向鏈表節(jié)點(diǎn)插入算法描述

2.1 基于雙向鏈表節(jié)點(diǎn)的類型定義

在雙向鏈表中，一個節(jié)點(diǎn)包括一個數(shù)據(jù)域、一個前驅(qū)和一個后繼，分別用data、prior和next表示。基于雙向鏈表的節(jié)點(diǎn)類型C語言模板如下[1]：

2.2 基于雙向鏈表的節(jié)點(diǎn)前插入算法

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

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

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

步驟①：將插入節(jié)點(diǎn)s的前驅(qū)指向插入位置節(jié)點(diǎn)p的前驅(qū)，即將指定節(jié)點(diǎn)的前驅(qū)指針作為新節(jié)點(diǎn)的前驅(qū)指針。

步驟②：將p的前驅(qū)的后繼域指向插入節(jié)點(diǎn)s，即調(diào)整新節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的后向指針。

步驟③：將插入節(jié)點(diǎn)s的后繼域指向了p節(jié)點(diǎn)，即將指定節(jié)點(diǎn)p作為新節(jié)點(diǎn)的后向指針。

步驟④：將p節(jié)點(diǎn)的前驅(qū)域指向s節(jié)點(diǎn)，即將新節(jié)點(diǎn)作為指定節(jié)點(diǎn)的前向指針。

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

2.3 基于雙向鏈表的節(jié)點(diǎn)后插入算法

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

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

步驟①：將插入節(jié)點(diǎn)s的后繼指向插入位置節(jié)點(diǎn)p的后繼，即將指定節(jié)點(diǎn)的后向指針作為新節(jié)點(diǎn)的后向指針；

步驟②：將p的next的prior域指向插入節(jié)點(diǎn)s，即調(diào)整p的next節(jié)點(diǎn)的前驅(qū)指針；

步驟③：將插入節(jié)點(diǎn)s的前驅(qū)域指向p節(jié)點(diǎn)，即將指定節(jié)點(diǎn)作為新節(jié)點(diǎn)的前向指針；

步驟④：將p的后繼域指向s節(jié)點(diǎn)，即將新節(jié)點(diǎn)作為指定節(jié)點(diǎn)的后向指針。

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

3 算法實(shí)驗(yàn)結(jié)果和分析

3.1 指針變化順序排列

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

表1 雙向鏈表插入節(jié)點(diǎn)步驟的24種排列順序

無論是節(jié)點(diǎn)前插入算法還是節(jié)點(diǎn)后插入算法，其4個操作步驟的排列順序都可由表1中的數(shù)據(jù)表示。本節(jié)需要注意的是，順序1分別代表2.2小節(jié)和2.3小節(jié)中出現(xiàn)的節(jié)點(diǎn)插入的順序，本文中也稱此順序?yàn)楣?jié)點(diǎn)插入的標(biāo)準(zhǔn)順序。

3.2 實(shí)驗(yàn)結(jié)果及分析

在本文中，實(shí)驗(yàn)對節(jié)點(diǎn)前、后插入算法的24種不同的順序分別進(jìn)行了測試，測試結(jié)果如下。

3.2.1 標(biāo)準(zhǔn)順序下的節(jié)點(diǎn)插入操作

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

圖1 順序1節(jié)點(diǎn)插入操作圖

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

使用節(jié)點(diǎn)前插入算法構(gòu)建一個雙向鏈表，其中包含“a”“b”“c”三個字符元素。假設(shè)在第二個字符位置前插入元素“k”，插入元素之后，第二個位置的字符變更為“k”，原第二個位置及之后位置的字符依次往后順延一位，即原字符順序變?yōu)椤癮kbc”。在實(shí)驗(yàn)中，輸入“abc”三個字符構(gòu)成雙向鏈表，以“$”符為結(jié)束標(biāo)識符，然后輸入不同插入位置及插入元素“k”，插入節(jié)點(diǎn)后的鏈表結(jié)果如圖2所示。

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

使用節(jié)點(diǎn)后插入算法構(gòu)建一個雙向鏈表，其中包含“a”“b”“c”三個字符元素。假設(shè)在第二個字符位置后插入元素“k”，插入元素之后，原第三個位置的字符變更為“k”，原第三個位置及之后位置的字符依次往后順延一位，即原字符順序變?yōu)椤癮bkc”。在實(shí)驗(yàn)中，輸入“abc”三個字符構(gòu)成雙向鏈表，以“$”符為結(jié)束標(biāo)識符，然后輸入不同插入位置及插入元素“k”，插入節(jié)點(diǎn)后的鏈表結(jié)果如圖3所示。

圖2 節(jié)點(diǎn)前插入結(jié)果實(shí)現(xiàn)圖

圖3 節(jié)點(diǎn)后插入結(jié)果實(shí)現(xiàn)圖

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

3.2.2 其他插入節(jié)點(diǎn)順序

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

通過實(shí)驗(yàn)測試，12種指針變化順序都能很好地完成新節(jié)點(diǎn)的插入操作，與標(biāo)準(zhǔn)順序1插入節(jié)點(diǎn)的效果一致。節(jié)點(diǎn)前插入算法插入節(jié)點(diǎn)結(jié)果實(shí)現(xiàn)圖與圖2完全一致，節(jié)點(diǎn)后插入算法插入節(jié)點(diǎn)結(jié)果實(shí)現(xiàn)圖與圖3完全一致。在本文中，經(jīng)過代碼的實(shí)現(xiàn)和測試，算法都能夠很好地完成其在雙向鏈表中的節(jié)點(diǎn)前插入操作和后插入操作。

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

3.2.3 非法操作順序

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

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

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

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

圖4 雙向鏈表節(jié)點(diǎn)插入指針替換圖

4 總結(jié)

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

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