每天5分鐘用C#學習數據結構（8）循環鏈表 Part 2

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

上一篇介紹了循環鏈表的基礎知識與節點定義實現，這一篇我們來學習下循環鏈表如何移除節點並給出一個完整的DEMO代碼示例。

1 循環鏈表的實現（續）

循環鏈表的節點移除

<code>public void Remove()
{
    if (this.tail == null)
    {
        throw new NullReferenceException("鏈表中沒有任何元素");
    }
    else if (this.count == 1)
    {
        // 只有一個元素時將兩個指針置為空
        this.tail = null;
        this.currentPrev = null;
    }
    else
    {
        if (this.currentPrev.Next == this.tail)
        {
            this.tail = this.currentPrev;
        }
        // 移除當前節點
        this.currentPrev.Next = this.currentPrev.Next.Next;
    }

    this.count--;
}/<code> 

這裡考慮到刪除節點時必須尋找其前驅節點會導致鏈表進行遍歷，故使用了當前節點的前驅節點來標識這個當前節點。移除當前節點只需要currentPrev.Next = currentPrev.Next.Next即可。

循環鏈表的完整實現

以下是單循環鏈表的完整模擬實現代碼，需要注意的是該CircularLinkedList主要是為後續會介紹到的約瑟夫問題而設計，故只實現了一些很簡單的功能：

<code>/// <summary>
/// 單向循環鏈表的模擬實現
/// /<summary>
public class MyCircularLinkedList
{
    private int count; // 字段：記錄數據元素個數
    private CirNode tail; // 字段：記錄尾節點的指針
    private CirNode currentPrev; // 字段：使用前驅節點標識當前節點

    // 屬性：指示鏈表中元素的個數
    public int Count
    {
        get
        { 

            return this.count;
        }
    }

    // 屬性：指示當前節點中的元素值
    public T CurrentItem
    {
        get
        {
            return this.currentPrev.Next.Item;
        }
    }

    public MyCircularLinkedList()
    {
        this.count = 0;
        this.tail = null;
    }

    public bool IsEmpty()
    {
        return this.tail == null;
    }

    // Method01:根據索引獲取節點
    private CirNode GetNodeByIndex(int index)
    {
        if (index < 0 || index >= this.count)
        {
            throw new ArgumentOutOfRangeException("index", "索引超出範圍");
        }

        CirNode tempNode = this.tail.Next;
        for (int i = 0; i < index; i++)
        {
            tempNode = tempNode.Next;
        }

        return tempNode;
    }

    // Method02:在尾節點後插入新節點
    public void Add(T value)
    {
        CirNode 
 newNode = new CirNode(value);
        if (this.tail == null)
        {
            // 如果鏈表當前為空則新元素既是尾頭結點也是頭結點
            this.tail = newNode;
            this.tail.Next = newNode;
            this.currentPrev = newNode;
        }
        else
        {
            // 插入到鏈表末尾處
            newNode.Next = this.tail.Next;
            this.tail.Next = newNode;
            // 改變當前節點
            if (this.currentPrev == this.tail)
            {
                this.currentPrev = newNode;
            }
            // 重新指向新的尾節點
            this.tail = newNode;
        }

        this.count++;
    }

    // Method03:移除當前所在節點
    public void Remove()
    {
        if (this.tail == null)
        {
            throw new NullReferenceException("鏈表中沒有任何元素");
        }
        else if (this.count == 1)
        {
            // 只有一個元素時將兩個指針置為空
            this.tail = null;
            this.currentPrev = null;
        }
        else
        {
            if (this.currentPrev.Next == this.tail)
            { 

                // 當刪除的是尾指針所指向的節點時
                this.tail = this.currentPrev;
            }
            // 移除當前節點
            this.currentPrev.Next = this.currentPrev.Next.Next;
        }

        this.count--;
    }

    // Method04:獲取所有節點信息
    public string GetAllNodes()
    {
        if (this.count == 0)
        {
            throw new NullReferenceException("鏈表中沒有任何元素");
        }
        else
        {
            CirNode tempNode = this.tail.Next;
            string result = string.Empty;
            for (int i = 0; i < this.count; i++)
            {
                result += tempNode.Item + " ";
                tempNode = tempNode.Next;
            }

            return result;
        }
    }
}/<code>

2 循環鏈表的簡單測試

這裡的簡單測試主要涉及：

1.順序插入5個節點，看節點元素是否正確；

2.查看當前節點是否正確；

3.移除某個元素，查看當前節點是否正確；

完整測試代碼如下所示：

<code>static void MyCircularLinkedListTest()
{
    MyCircularLinkedList linkedList = new MyCircularLinkedList();
    // 順序插入5個節點
    linkedList.Add(1);
    linkedList.Add(2);
    linkedList.Add(3);
    linkedList.Add(4);
    linkedList.Add(5);

    Console.WriteLine("All nodes in the circular linked list:");
    Console.WriteLine(linkedList.GetAllNodes());
    Console.WriteLine("--------------------------------------");
    // 當前節點：第一個節點
    Console.WriteLine("Current node in the circular linked list:");
    Console.WriteLine(linkedList.CurrentItem);
    Console.WriteLine("--------------------------------------");
    // 移除當前節點(第一個節點)
    linkedList.Remove();
    Console.WriteLine("After remove the current node:");
    Console.WriteLine(linkedList.GetAllNodes());
    Console.WriteLine("Current node in the circular linked list:");
    Console.WriteLine(linkedList.CurrentItem);
    // 移除當前節點(第二個節點)
    linkedList.Remove();
    Console.WriteLine("After remove the current node:");
    Console.WriteLine(linkedList.GetAllNodes());
    Console.WriteLine("Current node in the circular linked list:"); 

    Console.WriteLine(linkedList.CurrentItem);
    Console.WriteLine("--------------------------------------");

    Console.WriteLine();
}/<code>

測試結果如下圖所示：

運行結果

3 小結

本文介紹了循環鏈表的節點移除及完整DEMO測試。下一篇，我們會學習一下一個經典的約瑟夫問題。

程傑，《大話數據結構》

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

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

往期精彩

專欄：EdisonTalk（愛迪生說）

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

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

閱讀更多 EdisonTalk 的文章

關鍵字: 節點 數據結構 前驅