一、引言

在現(xiàn)代的前端渲染框架中，Virtual DOM?幾乎已經(jīng)成了標(biāo)配，通過這樣一個(gè)緩沖層，我們已經(jīng)能夠?qū)崿F(xiàn)對 Real DOM 的最少操作，在大家的廣泛認(rèn)知中，操作 DOM 是比較慢的，因此 Virtual DOM 可以實(shí)現(xiàn)應(yīng)用程序的性能提升。

毫無疑問，Virtual DOM 不可能全量同步到 Real DOM，因?yàn)槟菢泳瓦`背了設(shè)計(jì) Virtual DOM 的初衷，那么Virtual DOM 同步到 Real DOM 的操作就稱之為 DOM Diff，顧名思義，計(jì)算兩個(gè) DOM Tree 之間的差異性，增量更新 Real DOM。更新動(dòng)作的原則是，能復(fù)用的節(jié)點(diǎn)絕不刪除重新創(chuàng)建。

不同框架對于 DOM Diff 的理解并不完全一致，但有一點(diǎn)可以達(dá)成共識：由于 DOM 本身是樹形（Tree）結(jié)構(gòu)，不同層級之間的節(jié)點(diǎn)（Node）沒有必要對比，因?yàn)檫@可能會(huì)帶來?O(N3)?的計(jì)算復(fù)雜度，很可能還不如直接操作 Real DOM 來的快。因此，狹義的 DOM Diff 算法，一般指的是同一層級兄弟節(jié)點(diǎn)的范圍之內(nèi)。

本文，我就對典型的幾種 DOM Diff 實(shí)現(xiàn)進(jìn)行簡單的介紹，并分析潛在的陷阱，以便從原理上理解并更好地使用相應(yīng)的框架。

二、實(shí)現(xiàn)簡介

React

大多數(shù)開發(fā)者都是從?React?上才第一次接觸到 Virtual DOM 這個(gè)概念的，雖然并非是它發(fā)明的。在幾年前 Angular 1.x 大熱的時(shí)候，“臟檢查”的原理幾乎成為了每一次面試的必考題目。很快，“臟檢查”帶來的性能上的瓶頸并很快顯現(xiàn)出來，除了“餓了么”等少數(shù)產(chǎn)品之外，鮮有團(tuán)隊(duì)敢于在C端系統(tǒng)上部署 Angular，它更多成為了后臺(tái)系統(tǒng)的效率利器，甚至有很多后端開發(fā)者也擁有了編寫后臺(tái)前端的能力，因此 Angular 帶來的開發(fā)效率上的提升還是相當(dāng)值得肯定的。

在大多數(shù)人的印象里，帶來性能革命的就是 React，連帶的 JSX、Virtual DOM 都成為了日后開發(fā)者耳熟能詳?shù)母拍睢，F(xiàn)在我們就來了解一下 React 是如何實(shí)現(xiàn) DOM Diff 的。

假設(shè)在 Real DOM 中存在下面這幾個(gè)兄弟節(jié)點(diǎn)：【A、B、C、D、E、F、G】，而現(xiàn)在 Virtual DOM 中是 【D、A、G、F、K、E】。顯然，除了順序打亂了之外，移除了B節(jié)點(diǎn)和C節(jié)點(diǎn)，新增了K節(jié)點(diǎn)。我們來一步一步演示 React 的 DOM Diff 算法。

遍歷 Virtual DOM。

首先，第1個(gè)節(jié)點(diǎn)除非要被移除，否則不會(huì)被移動(dòng)，于是首節(jié)點(diǎn)D不動(dòng)。

遍歷到節(jié)點(diǎn)A，在 Real DOM 中節(jié)點(diǎn)A在節(jié)點(diǎn)D之前，與 Virtual DOM 中的先后順序不同，因此我們把節(jié)點(diǎn)A移動(dòng)到節(jié)點(diǎn)D之后（這里使用了 DOM 元素的 insertBefore 方法）。這是第1次操作DOM，此時(shí) Real DOM 為 【B、C、D、A、E、F、G】。

遍歷到節(jié)點(diǎn)G，由于在Real DOM 中節(jié)點(diǎn)G在節(jié)點(diǎn)A（上一個(gè)遍歷到的節(jié)點(diǎn)）之后，與 Virtual DOM 順序相同，因此不動(dòng)。

遍歷到節(jié)點(diǎn)F，由于在 Real DOM 中節(jié)點(diǎn)F在節(jié)點(diǎn)G（上一個(gè)遍歷到的節(jié)點(diǎn)）之前，與 Virtual DOM 順序不同，因此我們把節(jié)點(diǎn)F移動(dòng)到節(jié)點(diǎn)G之后。這是第2次操作DOM，此時(shí) Real DOM 為 【B、C、D、A、E、G、F】。

遍歷到節(jié)點(diǎn)K，在 Real DOM 中不存在K節(jié)點(diǎn)，我們創(chuàng)建它，并放在節(jié)點(diǎn)F（上一個(gè)遍歷到的節(jié)點(diǎn)）之后。這是第3次操作DOM，此時(shí) Real DOM 為 【B、C、D、A、E、G、F、K】。

遍歷到節(jié)點(diǎn)E，由于節(jié)點(diǎn)K（上一個(gè)遍歷到的節(jié)點(diǎn)）是新創(chuàng)建的節(jié)點(diǎn)，因此我們直接把節(jié)點(diǎn)E移動(dòng)到節(jié)點(diǎn)K之后。這是第4次操作DOM，此時(shí) Real DOM 為 【B、C、D、A、G、F、K、E】。

遍歷 Real DOM

移除節(jié)點(diǎn)B和節(jié)點(diǎn)C。第5、6次操作DOM，Real DOM 為【D、A、G、F、K、E】。

一共操作了6次DOM，完成了這次 DOM Diff。

我們假設(shè)如果不使用 Virtual DOM，那么所有 DOM 節(jié)點(diǎn)都需要移除和重新創(chuàng)建，一共13次 DOM 操作，顯然我們有了50%以上的效率提升。

我們言簡意賅地總結(jié)一下 React 的 DOM Diff 算法的關(guān)鍵邏輯。

Virtual DOM 中的首個(gè)節(jié)點(diǎn)不執(zhí)行移動(dòng)操作（除非它要被移除），以該節(jié)點(diǎn)為原點(diǎn)，其它節(jié)點(diǎn)都去尋找自己的新位置；

在 Virtual DOM 的順序中，每一個(gè)節(jié)點(diǎn)與前一個(gè)節(jié)點(diǎn)的先后順序與在 Real DOM 中的順序進(jìn)行比較，如果順序相同，則不必移動(dòng)，否則就移動(dòng)到前一個(gè)節(jié)點(diǎn)的前面或后面

于是，如果不考慮節(jié)點(diǎn)的移除和創(chuàng)建，我們可以推導(dǎo)出什么樣的重新排序?qū)@套 DOM Diff 算法最不利。最不利的結(jié)果無非就是除了首個(gè)節(jié)點(diǎn)外，其它所有節(jié)點(diǎn)都需要移動(dòng)，對于有?N?個(gè)節(jié)點(diǎn)的數(shù)組，總共移動(dòng)了?N-1?次。

考慮這個(gè)序列【A、B、C、D】，如果想變成【D、C、B、A】，應(yīng)該是什么樣的過程：

節(jié)點(diǎn)D是首個(gè)節(jié)點(diǎn)，不執(zhí)行移動(dòng)。

節(jié)點(diǎn)C移動(dòng)到節(jié)點(diǎn)D后面：【A、B、D、C】；

節(jié)點(diǎn)B移動(dòng)到節(jié)點(diǎn)C后面：【A、D、C、B】；

節(jié)點(diǎn)A移動(dòng)到節(jié)點(diǎn)B后面：【D、C、B、A】。

一共3步，正是?N-1。所以，可以確定的是，如果末尾的節(jié)點(diǎn)移動(dòng)到了首位，就會(huì)引起最不利的 DOM Diff 結(jié)果。

我們用另一個(gè)例子驗(yàn)證一下，這個(gè)序列【A、B、C、D】，變成【D、A、B、C】。我們一眼看上去就知道，只要把節(jié)點(diǎn)D移動(dòng)到首位就可以了，但是我們看 React 它會(huì)怎么做：

節(jié)點(diǎn)D是首個(gè)節(jié)點(diǎn)，不執(zhí)行移動(dòng)。

節(jié)點(diǎn)A移動(dòng)到節(jié)點(diǎn)D后面：【B、C、D、A】；

節(jié)點(diǎn)B移動(dòng)到節(jié)點(diǎn)A后面：【C、D、A、B】；

節(jié)點(diǎn)C移動(dòng)到節(jié)點(diǎn)B后面：【D、A、B、C】。

還是?N-1，可見首個(gè)節(jié)點(diǎn)不執(zhí)行移動(dòng)這個(gè)特性，導(dǎo)致了只要把末尾節(jié)點(diǎn)移動(dòng)到首位，就會(huì)引起?N-1?這種最壞的 DOM Diff 過程，所以大家要盡可能避免這種重排序。

Vue

Vue 的起步晚于 React，但被廣大開發(fā)者接受的更迅速。事實(shí)上，Vue 并不能與 React 完全等價(jià)。React 只是專注于數(shù)據(jù)到視圖的轉(zhuǎn)換，而 Vue 則是典型的 MVVM，帶有雙向綁定。當(dāng)然 Vue 還具備更人性化、更方便的的工程化開發(fā)框架，這也是它為什么更容易被接受的原因，不過本文不做討論。

Vue 并未完全自主開發(fā)一套 Virtual DOM，而是借鑒了另一個(gè)開源庫snabbdom，其核心算法邏輯代碼請參考https://github.com/snabbdom/snabbdom/blob/v0.7.3/src/snabbdom.ts#L179。

下面我們還是用之前的例子來演示這套 DOM Diff 是如何運(yùn)作的，由【A、B、C、D、E、F、G】轉(zhuǎn)換成【D、A、G、F、K、E】。

設(shè)定4個(gè)指針OS（OldStart）、OE（OldEnd）、NS（NewStart）、NE（NewEnd），分別指向這兩個(gè)序列的頭尾。

A B C D E F G

? ?

OS? ? ? ? ? OE

D A G F K E

?? ? ? ? ?

NS? ? ? ? NE

現(xiàn)在我們來交叉比較，看有沒有相同的。如果OS或OE與NS相同，則移動(dòng)到NS的位置，如果OS或OE與NE相同，則移動(dòng)到NE的位置。如果都沒有相同的，則在 Real DOM 中找到NS的元素，移動(dòng)到NS位置。

可見，【A，G】與【D，E】沒有相同的，那么就找到D元素，移動(dòng)到NS的位置。這是第1次操作DOM，此時(shí) Real DOM 為 【D、A、B、C、E、F、G】，NS++，OS++，現(xiàn)在4個(gè)指針的指向?yàn)椋?/p>

D A B C E F G

? ? ?

? OS? ? ? ? OE

D A G F K E

? ?? ? ? ?

? NS? ? ? NE

然后開始第二輪比較，顯然OS與NS都是A，相同，不用執(zhí)行任何移動(dòng)操作，OS++，NS++，現(xiàn)在4個(gè)指針的指向?yàn)椋?/p>

D A B C E F G

? ? ? ?

? ? OS? ? ? OE

D A G F K E

? ? ?? ? ?

? ? NS? ? NE

現(xiàn)在開始第三輪比較，顯然OE與NS都是G，相同，現(xiàn)在需要把OE移動(dòng)到NS的位置。這是第2次操作DOM，此時(shí) Real DOM 為 【D、A、G、B、C、E、F】，OE–，NS++，現(xiàn)在4個(gè)指針的指向?yàn)椋?/p>

D A G B C E F

? ? ? ? ?

? ? ? OS? ? OE

D A G F K E

? ? ? ?? ?

? ? ? NS? NE

現(xiàn)在開始第四輪比較，顯然OE與NS都是F，相同，現(xiàn)在需要把OE移動(dòng)到NS的位置。這是第3次操作DOM，此時(shí) Real DOM 為 【D、A、G、F、B、C、E】，OE–，NS++，現(xiàn)在4個(gè)指針的指向?yàn)椋?/p>

D A G F B C E

? ? ? ? ? ?

? ? ? ? OS? OE

D A G F K E

? ? ? ? ? ?

? ? ? ? NSNE

現(xiàn)在開始第五輪比較，顯然OE與NE都是E，相同，不用執(zhí)行任何移動(dòng)操作，OE–，NE–，現(xiàn)在4個(gè)指針的指向?yàn)椋?/p>

D A G F B C E

? ? ? ? ? ?

? ? ? ? OSOE

D A G F K E

? ? ? ? ?

? ? ? ? NS=NE

現(xiàn)在開始第六輪比較，顯然NS（或NE）指向的 K 在 Real DOM 中并不存在，因此我們創(chuàng)建節(jié)點(diǎn)K，這是第4次操作DOM，此時(shí) Real DOM 為 【D、A、G、F、K、B、C、E】，NS++，現(xiàn)在4個(gè)指針的指向?yàn)椋?/p>

D A G F K B C E

? ? ? ? ? ? ?

? ? ? ? ? OSOE

D A G F K E

? ? ? ? ? ?

? ? ? ? NENS

由于NE<NS，意味著 新序列中已經(jīng)沒有可遍歷的元素，因此OS與OE閉區(qū)間內(nèi)的節(jié)點(diǎn)都需要被刪除，這是第5、6次操作DOM，此時(shí) Real DOM 為 【D、A、G、F、K、E】。

到此為止，我們用了六次DOM操作，與 React 的性能相當(dāng)。

我們還是總結(jié)一下 Vue 的 DOM Diff 算法的關(guān)鍵邏輯：

建立新序列（Virtual DOM）頭（NS）尾（NE）、老序列（Real DOM）頭（OS）尾（OE）一共4個(gè)指針，然后讓NS/NE與OS/OE比較；

如果發(fā)現(xiàn)有OS或OE的值與NS或NE相同，則把相應(yīng)節(jié)點(diǎn)移動(dòng)到NS或NE的位置。

說的簡單一點(diǎn)，其實(shí) Vue 的這個(gè) DOM Diff 過程就是一個(gè)查找排序的過程，遍歷 Virtual DOM 的節(jié)點(diǎn)，在 Real DOM 中找到對應(yīng)的節(jié)點(diǎn)，并移動(dòng)到新的位置上。不過這套算法使用了雙向遍歷的方式，加速了遍歷的速度。

從以上原理中我們可以輕易地推導(dǎo)出對該算法最不利的莫過于序列倒序。比如從【A、B、C、D】轉(zhuǎn)換為【D、C、B、A】，算法將執(zhí)行N-1次移動(dòng)，與 React 相同，并沒有更壞。

那么我們再看一眼對于 React 無法高效處理的例子，【A、B、C、D】轉(zhuǎn)換為【D、A、B、C】，看一下 Vue 的算法表現(xiàn)如何。

在第一輪比較中，Real DOM 的末尾節(jié)點(diǎn)D與 Virtual DOM 的首節(jié)點(diǎn)D相同，那么就把節(jié)點(diǎn)D移動(dòng)到首位，變成【D、A、B、C】，直接一步到位，高效完成了轉(zhuǎn)換，從這一點(diǎn)上，并沒有犯 React 的錯(cuò)。

不過值得說明的是，在匹配不成功的情況下，如何找到NS節(jié)點(diǎn)在 Real DOM 的位置，并非是順序遍歷的（否則就會(huì)導(dǎo)致?O(N2)?的復(fù)雜度），而是預(yù)先存儲(chǔ)了各個(gè)節(jié)點(diǎn)的位置，查找映射表即可，所以可以說是用一定的空間復(fù)雜度換了時(shí)間復(fù)雜度。

Inferno

Inferno 雖然在一定程度上兼容 React 語法，但它最大的賣點(diǎn)卻是其卓越的算法。如果說 React、Vue 的算法能在一定程度上能節(jié)約DOM操作的次數(shù)的話， 那么毫無夸張地說，Inferno 的算法就是能把DOM操作的次數(shù)降到最低。我們來看一下它是怎么辦到的。

下面我們還是用之前的例子來演示這套 DOM Diff 是如何運(yùn)作的，由【A、B、C、D、E、F、G】轉(zhuǎn)換成【D、A、G、F、K、E】。

首先，我們記錄 Virtual DOM 的各個(gè)元素在 Real DOM 中的序號：【3、0、6、5、-1、4】，記錄為數(shù)組maxIncrementSubSeq，其中-1表示在 Real DOM 中并不存在，需要?jiǎng)?chuàng)建。

這個(gè)數(shù)組能說明什么呢？別著急，現(xiàn)在我們來獲取該數(shù)組的“最大遞歸子序列”，當(dāng)然，僅限非負(fù)數(shù)。

這個(gè)例子有4個(gè)子序列都滿足需求：【3、5】、【3、4】、【0、5】、【0、4】，具體算法已經(jīng)很成熟，這里不關(guān)心，我們隨便取一個(gè)【3、5】。

Real DOM 在【3、5】位置上是節(jié)點(diǎn)D和節(jié)點(diǎn)G。這說明這兩個(gè)節(jié)點(diǎn)是不需要移動(dòng)位置的，其它都要移動(dòng)或刪除。

從數(shù)組?maxIncrementSubSeq?中我們已經(jīng)能夠推斷出應(yīng)該刪除的節(jié)點(diǎn)是位于位置【1、2】的兩個(gè)節(jié)點(diǎn)B和C，因?yàn)椤?、2】并未出現(xiàn)在數(shù)組?maxIncrementSubSeq?中。這是第1、2次DOM操作，此時(shí) Real DOM 為 【A、D、E、F、G】。

接下來我們從后往前遍歷 Virtual DOM：

最后一個(gè)是節(jié)點(diǎn)E，那我們就把節(jié)點(diǎn)E移動(dòng)到最后，這是第3次DOM操作，此時(shí) Real DOM 為 【A、D、F、G、E】；

遍歷到節(jié)點(diǎn)K，這是一個(gè)新節(jié)點(diǎn)，我們創(chuàng)建并插入到節(jié)點(diǎn)E（上一個(gè)遍歷到的節(jié)點(diǎn)）之前，這是第4次DOM操作，此時(shí) Real DOM 為 【A、D、F、G、K、E】；

遍歷到節(jié)點(diǎn)F，那我們就把節(jié)點(diǎn)F移動(dòng)到節(jié)點(diǎn)K之前，這是第5次DOM操作，此時(shí) Real DOM 為 【A、D、G、F、K、E】；

遍歷到節(jié)點(diǎn)G，由于節(jié)點(diǎn)G位于最大遞增子序列中，因此不需要移動(dòng)；

遍歷到節(jié)點(diǎn)A，由于節(jié)點(diǎn)A也位于最大遞增子序列中，因此也不需要移動(dòng)；

遍歷到節(jié)點(diǎn)D，那我們就把節(jié)點(diǎn)D移動(dòng)到節(jié)點(diǎn)A之前，這是第6次DOM操作，此時(shí) Real DOM 為 【D、A、G、F、K、E】。

同樣操作了六次DOM，相比于 Vue、React 好像并沒有什么優(yōu)勢，不過這是因?yàn)檫@個(gè)例子中的最大遞增子序列太短導(dǎo)致的，也就是說，能保持位置不動(dòng)的元素不夠多。

同樣再看一眼對于 React 無法高效處理的例子，【A、B、C、D】轉(zhuǎn)換為【D、A、B、C】，看一下 Inferno 的算法表現(xiàn)如何。

顯然，最大遞增子序列所代表的不需要移動(dòng)的元素是【A、B、C】，那么從后往前遍歷 Virtual DOM，先后經(jīng)歷節(jié)點(diǎn)C、B、A都不需要移動(dòng)，到節(jié)點(diǎn)D才需要移動(dòng)一次，因此對于這種特殊場景，Inferno 也只需要一次 DOM 操作，與 Vue 效率相同。

那么對于序列倒序這種特殊場景，由于最大遞增子序列的長度為1，所以也需要N-1次DOM移動(dòng)操作，與 Vue 相同。

那么有沒有能優(yōu)于 Vue 算法的場景呢？試想將【A、B、C、D、E】轉(zhuǎn)換為【C、D、E、A、B】。

對于 Inferno 而言，由于最大遞增子序列【C、D、E】的長度為3，所以只需要5-3=2次DOM操作即可完成重排序。

ABCDE

? ?

ACDEB

? ?

CDEAB

對于 Vue 而言，則依賴于算法在遇到無匹配的邏輯分支下，是決定補(bǔ)NS指針的節(jié)點(diǎn)位置還是補(bǔ)NE指針，如果是后者，則也只需要2次DOM移動(dòng)操作，如果是前者，則需要3次。從實(shí)現(xiàn)代碼上來看，是前者。

ABCDE

? ?

CABDE

? ?

CDABE

? ?

CDEAB

因此在一些比較特殊的情況下，Inferno 在節(jié)省DOM操作次數(shù)的指標(biāo)上，是可能優(yōu)于 Vue 的，不過也不多。

現(xiàn)在我們再來回想一下 React 的算法，在上面這個(gè)例子中，React 也只需要移動(dòng)2次就夠了。

ABCDE

? ?

BCDEA

? ?

CDEAB

如果你仔細(xì)回味，就會(huì)發(fā)現(xiàn)，React 的 DOM Diff 算法其實(shí)也體現(xiàn)了最大遞增子序列的概念，但是它假定這個(gè)子序列一定是從第一個(gè)位置開始的，一旦不是這樣子，算法效率就會(huì)惡化，這也是為什么它不能很好地處理末尾節(jié)點(diǎn)移動(dòng)到首位這種場景的，因?yàn)樽有蛄虚L度僅為1。

三、總結(jié)

簡單闡述了 React、Vue、Inferno 的算法梗概之后，我們統(tǒng)一總結(jié)一下：

Inferno 利用最大遞增子序列的算法達(dá)到了移動(dòng)DOM次數(shù)最少的目標(biāo)；

React 假定最大遞增子序列從0開始，在末尾節(jié)點(diǎn)移動(dòng)到首位的場景中會(huì)惡化；

Vue 利用雙向遍歷排序的方法，有可能不是最優(yōu)解，但與最優(yōu)解十分逼近；

三種算法對于倒序這種場景都降級為理論上的最少N-1次。

因此，在實(shí)際的業(yè)務(wù)開發(fā)中，序列倒序是最應(yīng)該被避免的，對于 React 還應(yīng)注意末尾節(jié)點(diǎn)的問題，除此之外，沒有什么特別需要擔(dān)心的，框架都會(huì)在足夠程度上（雖然可能不是最優(yōu)的）利用現(xiàn)有DOM而不是重新創(chuàng)建，從而實(shí)現(xiàn)性能優(yōu)化的發(fā)揮。

需要特別指出的是，包括但不限于 React、Vue、Inferno 在內(nèi)的眾多框架，在同一層級節(jié)點(diǎn)上，都希望業(yè)務(wù)指定一個(gè)key值來判定重渲染前后是否是同一個(gè)節(jié)點(diǎn)，如果連key值都不同，那么DOM節(jié)點(diǎn)是不會(huì)被重用的。

在很多“最佳實(shí)踐”文章中，都認(rèn)為用數(shù)組遍歷的序號來做key值是不可取的，不過這也取決于具體場景，典型的是，如果遍歷的數(shù)據(jù)是靜態(tài)不可變的，那么使用序號來做key并不會(huì)有什么問題。

退一步說，如果數(shù)組順序變化，依然用序號做key會(huì)有什么問題呢？這個(gè)問題需要從兩方面來回答。

首先，對于性能來講，渲染前后對于同一個(gè)序號的數(shù)據(jù)發(fā)生了變化，框架依然可能會(huì)重用節(jié)點(diǎn)，這可能會(huì)導(dǎo)致后代節(jié)點(diǎn)的大量刪除與重建。

其次，對于渲染結(jié)果正確性來講，一般也不會(huì)有問題，但有一種場景，就是DOM上的數(shù)據(jù)并沒有同步到框架中，比如 React 中的一個(gè)概念，叫做“失控組件（https://reactjs.org/docs/uncontrolled-components.html）”，那么重渲染之后，未同步的數(shù)據(jù)很可能出現(xiàn)在錯(cuò)誤的節(jié)點(diǎn)中。

這就是使用序號來做key需要注意的知識點(diǎn)。

對于 Inferno 而言，key值的邏輯并不絕對，對于靜態(tài)數(shù)組或者只是在尾部添加元素的數(shù)組，不使用key反倒在性能上更有優(yōu)勢。不過對于使用頻率高得多的 React 和 Vue，還是老老實(shí)實(shí)都添加 key 為好。

最后，還有一個(gè)問題需要回答，Inferno 的算法是否解決了將一個(gè)數(shù)組打亂成另一個(gè)數(shù)組，中間最少需要幾步的問題呢？我看不見得，大家要注意DOM有這樣一個(gè)操作：insertBefore，它的功能是在一個(gè)節(jié)點(diǎn)前面插入另一個(gè)節(jié)點(diǎn)，如果要插入的節(jié)點(diǎn)就在這個(gè)兄弟節(jié)點(diǎn)集合中，那么它還會(huì)被自動(dòng)從原來的位置移除。

數(shù)組有這樣的特性嗎？恐怕沒有。數(shù)組是順序存儲(chǔ)的，在一個(gè)位置插入數(shù)據(jù)會(huì)導(dǎo)致后面的數(shù)據(jù)全部后移，這是可觀的性能開銷。

如果換成雙向鏈表，那么我認(rèn)為應(yīng)用這幾種算法都問題不大。