每天5分鐘，學習數據結構

介紹了雙鏈表的基本定義及如何新增節點，這一篇我們來學習下如何移除節點及實現一個完整的測試DEMO。

1 雙鏈表的實現（續）

雙鏈表中移除節點

示意圖

<code>public void RemoveAt(int index){    if (index == 0)    {        this.head = this.head.Next;    }    else    {        DbNode prevNode = this.GetNodeByIndex(index - 1);        if (prevNode.Next == null)        {            throw new ArgumentOutOfRangeException("index", "索引超出範圍");        }        DbNode deleteNode = prevNode.Next;        DbNode nextNode = deleteNode.Next;        prevNode.Next = nextNode;        if(nextNode != null)        {            nextNode.Prev = prevNode;        }        deleteNode = null;    }    this.count--;}/<code>

這裡只需要將前驅節點的Next指針指向待刪除節點的後繼節點，將後繼節點的Prev指針指向待刪除節點的前驅節點即可。

完整的雙鏈表實現

至此，關鍵部分的代碼已介紹完畢，下面給出完整的雙鏈表實現代碼：

<code>/// <summary>/// 雙鏈表的模擬實現/// /<summary>public class MyDoubleLinkedList{    private int count; // 字段：當前鏈表節點個數    private DbNode head; // 字段：當前鏈表的頭結點    // 屬性：當前鏈表節點個數    public int Count    {        get        {            return this.count;        }    }    // 索引器    public T this[int index]    {        get        {            return this.GetNodeByIndex(index).Item;        }        set        {            this.GetNodeByIndex(index).Item = value;        }    }    public MyDoubleLinkedList()    {        this.count = 0;        this.head = null;    }    // Method01:根據索引獲取節點    private DbNode GetNodeByIndex(int index)    {        if (index < 0 || index >= this.count)        {            throw new ArgumentOutOfRangeException("index", "索引超出範圍");        }        DbNode tempNode = this.head;        for (int i = 0; i < index; i++)        {            tempNode = tempNode.Next;        }        return tempNode;    }    // Method02:在尾節點後插入新節點    public void AddAfter(T value)    {        DbNode newNode = new DbNode(value);        if (this.head == null)        {            // 如果鏈表當前為空則置為頭結點            this.head = newNode;        }        else        {            DbNode lastNode = this.GetNodeByIndex(this.count - 1);            // 調整插入節點與前驅節點指針關係            lastNode.Next = newNode;            newNode.Prev = lastNode;        }        this.count++;    }    // Method03:在尾節點前插入新節點    public void AddBefore(T value)    {        DbNode 
 newNode = new DbNode(value);        if (this.head == null)        {            // 如果鏈表當前為空則置為頭結點            this.head = newNode;        }        else        {            DbNode lastNode = this.GetNodeByIndex(this.count - 1);            DbNode prevNode = lastNode.Prev;            // 調整倒數第2個節點與插入節點的關係            prevNode.Next = newNode;            newNode.Prev = prevNode;            // 調整倒數第1個節點與插入節點的關係            lastNode.Prev = newNode;            newNode.Next = lastNode;        }        this.count++;    }    // Method04:在指定位置後插入新節點    public void InsertAfter(int index, T value)    {        DbNode tempNode;        if (index == 0)        {            if (this.head == null)            {                tempNode = new DbNode(value);                this.head = tempNode;            }            else            {                tempNode = new DbNode(value);                tempNode.Next = this.head;                this.head.Prev = tempNode;                this.head = tempNode;            }        }        else        {            DbNode prevNode = this.GetNodeByIndex(index); // 獲得插入位置的節點            DbNode nextNode = prevNode.Next; // 獲取插入位置的後繼節點            tempNode = new DbNode(value);            // 調整插入節點與前驅節點指針關係            prevNode.Next = tempNode;            tempNode.Prev = prevNode;            // 調整插入節點與後繼節點指針關係            if (nextNode != null)            {                tempNode.Next = nextNode;                nextNode.Prev = tempNode;            }        }        this.count++;    }    // Method05:在指定位置前插入新節點    public void InsertBefore(int index, T value)    {        DbNode tempNode;        if (index == 0)        {            if (this.head == null)            {                tempNode = new DbNode(value);                this.head = tempNode;            }            else            {                tempNode = new DbNode(value);                tempNode.Next = this.head;                this.head.Prev = tempNode;                this.head = tempNode;            }        }        else        {            DbNode nextNode = this.GetNodeByIndex(index); // 獲得插入位置的節點            DbNode prevNode = nextNode.Prev; // 獲取插入位置的前驅節點            tempNode = new DbNode(value);            // 調整插入節點與前驅節點指針關係            prevNode.Next = tempNode;            tempNode.Prev = prevNode;            // 調整插入節點與後繼節點指針關係            tempNode.Next = nextNode;            nextNode.Prev = tempNode;        }        this.count++;    }    // Method06:移除指定位置的節點    public void RemoveAt(int index)    {        if (index == 0)        {            this.head = this.head.Next;        }        else        {            DbNode prevNode = this.GetNodeByIndex(index - 1);            if (prevNode.Next == null)            {                throw new ArgumentOutOfRangeException("index", "索引超出範圍");            }            DbNode deleteNode = prevNode.Next;            DbNode nextNode = deleteNode.Next;            prevNode.Next = nextNode;            if(nextNode != null)            {                nextNode.Prev = prevNode;            }            deleteNode = null;        }        this.count--;    }} 
/<code>

2 雙鏈表的測試

這裡跟單鏈表一樣，進行幾個簡單的測試：一是順序插入（默認在尾節點之後）4個新節點，二是在尾節點之前和在指定索引位置插入新節點，三是移除指定索引位置的節點，四是修改某個節點的Item值。測試代碼如下所示。

<code>static void MyDoubleLinkedListTest(){    MyDoubleLinkedList linkedList = new MyDoubleLinkedList();    // Test1:順序插入4個節點    linkedList.AddAfter(0);    linkedList.AddAfter(1);    linkedList.AddAfter(2);    linkedList.AddAfter(3);    Console.WriteLine("The nodes in the DoubleLinkedList:");    for (int i = 0; i < linkedList.Count; i++)    {        Console.Write(linkedList[i] + " ");    }    Console.WriteLine();    Console.WriteLine("----------------------------");    // Test2.1:在尾節點之前插入2個節點    linkedList.AddBefore(10);    linkedList.AddBefore(20);    Console.WriteLine("After add 10 and 20:");    for (int i = 0; i < linkedList.Count; i++)    {        Console.Write(linkedList[i] + " ");    }    Console.WriteLine();    // Test2.2:在索引為2(即第3個節點)的位置之後插入單個節點    linkedList.InsertAfter(2, 50);    Console.WriteLine("After add 50:");    for (int i = 0; i < linkedList.Count; i++)    {        Console.Write(linkedList[i] + " ");    }    Console.WriteLine();    // Test2.3:在索引為2(即第3個節點)的位置之前插入單個節點    linkedList.InsertBefore(2, 40);    Console.WriteLine("After add 40:");    for (int i = 0; i < linkedList.Count; i++)    {        Console.Write(linkedList[i] + " ");    }    Console.WriteLine();    Console.WriteLine("----------------------------");    // Test3.1:移除索引為7(即最後一個節點)的位置的節點    linkedList.RemoveAt(7);    Console.WriteLine("After remove an node in index of 7:");    for (int i = 0; i < linkedList.Count; i++)    {        Console.Write(linkedList[i] + " ");    }    Console.WriteLine();    // Test3.2:移除索引為0(即第一個節點)的位置的節點的值    linkedList.RemoveAt(0);    Console.WriteLine("After remove an node in index of 0:");    for (int i = 0; i < linkedList.Count; i++)    {        Console.Write(linkedList[i] + " ");    }    Console.WriteLine();    // Test3.3:移除索引為2(即第3個節點)的位置的節點    linkedList.RemoveAt(2);    Console.WriteLine("After remove an node in index of 2:");    for (int i = 0; i < linkedList.Count; i++)    {        Console.Write(linkedList[i] + " ");    }    Console.WriteLine();    Console.WriteLine("----------------------------");    // Test4:修改索引為2(即第3個節點)的位置的節點的值    linkedList[2] = 9;    Console.WriteLine("After update the value of node in index of 2:");    for (int i = 0; i < linkedList.Count; i++)    {        Console.Write(linkedList[i] + " ");    }    Console.WriteLine();    Console.WriteLine("----------------------------");}/<code>

測試結果如下圖所示：

運行結果

3 ListDictionary與LinkedList

在.NET中，已經為我們提供了單鏈表和雙鏈表的實現，它們分別是ListDictionary與LinkedList。從名稱我們就可以看出，單鏈表的實現ListDictionary不是泛型實現，而LinkedList是泛型實現，它們又到底有什麼區別呢，讓我們藉助反編譯工具Reflector去看看吧。

ListDictionary—基於Key/Value的單鏈表

查看ListDictionary源碼

ListDictionary位於System.Collection.Specialized下，它是基於鍵值對（Key/Value）的集合，微軟給出的建議是：通常用於包含10個或10個以下項的集合。

可以看到，它的節點的數據域是一個鍵值對，而不是一個簡單的Value。

LinkedList—神奇的泛型雙向鏈表

查看LinkedList源碼

在.NET中，LinkedList是使用地比較多的鏈表實現類，它位於System.Collections.Generic下，是一個通用的雙向鏈表類，它不支持隨機訪問（即索引訪問），但它實現了很多的新增節點的方法，例如：AddAfter、AddBefore、AddFirst以及AddLast等。其中，AddAfter是在現有節點之後添加新節點，AddBefore則是在現有節點之前添加新節點，AddFirst是在開頭處添加，而AddLast則是在末尾處添加。

4 小結

本文介紹了雙鏈表中如何移除節點及完整的實現代碼，然後通過對其進行測試查看實現的效果，最後通過反編譯工具查看了.NET中的ListDictionary與LinkedList的源碼瞭解了其實現要點。下一篇，我們將要開始學習循環鏈表。

程傑，《大話數據結構》

陳廣，《數據結構（C#語言描述）》

段恩澤，《數據結構（C#語言版）》

往期精彩

專欄：EdisonTalk（愛迪生說）

本文作者EdisonZhou，架構師，阿里雲MVP，博客園"推薦博客"博主(Top10)，Scrum聯盟認證CSM，.NET Core實踐者與佈道師，愛好閱讀與分享。

本文首發於EdisonZhou的公眾號“恰童鞋騷年”，歡迎關注，第一時間獲得更多內容分享。

閱讀更多 EdisonTalk 的文章

關鍵字: 數據結構 節點 雙鏈