C#集合本質(zhì)之鏈表的用法詳解

更新時間：2022年08月17日 08:41:58 作者：Darren?Ji

本文詳細講解了C#集合本質(zhì)之鏈表的用法，文中通過示例代碼介紹的非常詳細。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下

鏈表的由來和定義

在現(xiàn)實生活中，我們把不同的商品放在一個購物車中。而在面向?qū)ο蟮氖澜缋铮袝r候，也需要把不同類型的數(shù)據(jù)放到一起，組成一個集合。集合中的元素并不是彼此孤立的，在C#中，如何表達集合元素間的關(guān)系呢？

借助"自引用類"可以確立集合元素間的關(guān)系。比如有這樣一個自引用類：

public class Node
{
    public int Data{get;set;}
    public Node Next{get;set;}
    public Node(int dataValue)
    {}
}

Node類的最大特點是：存在一個Node類型的屬性，這個屬性指向Node的另一個實例，Next屬性也稱為"引用鏈"。放到集合的場景中來說就是：把多個Node實例放到一個集合中，每一個Node實例包含一個Next屬性指向下一個Node實例。而該集合中的最后一個Node實例會指向null。用圖表示就是：

鏈表就是自引用類對象的線性集合，即序列。

由于每個自引用對象是由引用鏈鏈接起來，所以叫鏈表。堆棧與隊列是約束版的鏈表，而二叉查找數(shù)是非線性數(shù)據(jù)結(jié)構(gòu)。

鏈表的節(jié)點或元素雖然在邏輯上是連續(xù)的、線性的，當(dāng)其內(nèi)存不是連續(xù)存儲的；數(shù)組元素在內(nèi)存中是連續(xù)的，所以我們才可以通過索引來訪問數(shù)組元素。

創(chuàng)建一個單向鏈表

首先創(chuàng)建一個節(jié)點，是一個自引用類：

namespace LinkedListLibrary
{
    public class ListNode
    {
        //當(dāng)前節(jié)點對象
        public object Data { get; private set; }
        //Next屬性也稱為鏈，指向另一個ListNode對象實例，這樣就把2個ListNode對象實例鏈接起來了
        public ListNode Next { get; set; }
        public ListNode(object dataValue): this(dataValue, null)
        {
            
        }
        public ListNode(object dataValue, ListNode nextNode)
        {
            Data = dataValue;
            Next = nextNode;
        }
    }
}

再模擬一個鏈表，如下：

namespace LinkedListLibrary
{
    public class List
    {
        private ListNode firstNode;
        private ListNode lastNode;
        private string name;
        public List(string listName)
        {
            name = listName;
            firstNode = lastNode = null;
        }
        public List() : this("list"){}
     
         ......
        //如果第一個節(jié)點是null，那就說明集合為空
        public bool IsEmpty()
        {
            return firstNode == null;
        }
    }
}

以上，如果第一個節(jié)點為null，那就說明該鏈表為空。List類提供了IsEmpty方法用來判斷鏈表是否為空。List還包含另外5個重要的方法，下面展開來說。

在鏈表的的第一個節(jié)點前插入。

        //在最前面插入元素、節(jié)點
        public void InsertAtFront(object insertItem)
        {
            if (IsEmpty())//如果集合為空，加進來一個元素，相當(dāng)于第一個節(jié)點和第二個節(jié)點相同，都是新加的元素
            {
                firstNode = lastNode = new ListNode(insertItem);
            }
            else //如果集合不為空，第一個節(jié)點就是新加的元素,原先的第一個節(jié)點變?yōu)橄乱粋€節(jié)點
            {
                firstNode = new ListNode(insertItem, firstNode);
            }
        }

以上，當(dāng)集合不為空的情況下，實際上是把新添加的節(jié)點設(shè)為第一個節(jié)點，并把新的第一個節(jié)點的引用鏈指向原先的第一個節(jié)點。

在鏈表的最后一個節(jié)點后插入。

        public void InsertAtBack(object insertItem)
        {
            if (IsEmpty())//如果原先集合為空，第一個節(jié)點和最后一個節(jié)點就是新加的節(jié)點
            {
                firstNode = lastNode = new ListNode(insertItem);
            }
            else//如果原先的集合不為空，最后一個節(jié)點的屬性值就是新加的節(jié)點
            {
                lastNode = lastNode.Next = new ListNode(insertItem);
            }
        }

以上，當(dāng)集合不為空的情況下，實際上是把新添加的節(jié)點設(shè)置成最后一個節(jié)點，并把新的最后一個節(jié)點的引用鏈指向null。

移除鏈表最前面的節(jié)點。

        //移除最前面的元素、節(jié)點
        //即重新設(shè)置第一個節(jié)點的Next屬性
        public object RemoveFromFront()
        {
            if (IsEmpty())
                throw new EmptyListException(name);
            //從第一個節(jié)點中取出節(jié)點對象
            object removeItem = firstNode.Data;
            if (firstNode == lastNode) //如果集合中只有一個元素
            {
                firstNode = lastNode = null;
            }
            else //正常情況下，把firstNode的Next屬性所指向的節(jié)點賦值給第一個節(jié)點
            {
                firstNode = firstNode.Next;
            }
            return removeItem;
        }

以上，本質(zhì)是把原先排在第二位置的節(jié)點設(shè)置成第一個節(jié)點。

移除鏈表最后面的節(jié)點。

        //移除最后面的元素、節(jié)點
        public object RemoveFromBack()
        {
            if (IsEmpty())
            {
                throw new EmptyListException();
            }
            //從最后一個節(jié)點中獲取節(jié)點對象
            object removeItem = lastNode.Data;
            if (firstNode == lastNode)//如果當(dāng)前集合只有一個節(jié)點
            {
                firstNode = lastNode = null;
            }
            else
            {
                //先把第一個節(jié)點作為當(dāng)前節(jié)點
                ListNode current = firstNode; 
                //改變除最后一個節(jié)點之外的節(jié)點的值
                while (current.Next != lastNode)
                {
                    current = current.Next;
                }
                //最后current變成倒數(shù)第二個節(jié)點
                lastNode = current;
                current.Next = null;//最后一個節(jié)點的Next屬性為null，即沒有指向另一個節(jié)點
            }
            return removeItem;
        }

以上，從第一個節(jié)點開始，一直循環(huán)到倒數(shù)第二個節(jié)點，current就像一個指針，每指到一個節(jié)點，就把該節(jié)點的下面一個節(jié)點設(shè)置為當(dāng)前節(jié)點。最后，把倒數(shù)第二個節(jié)點設(shè)置為最后一個節(jié)點。把Current的引用鏈設(shè)置為null，讓其能被垃圾回收機制回收。

打印鏈表。

        //打印顯示
        public void Display()
        {
            if (IsEmpty())
            {
                Console.WriteLine("集合" + name + "為空");
            }
            else
            {
                Console.WriteLine("集合的名稱是：" + name);
                //先把第一個節(jié)點作為當(dāng)前節(jié)點
                ListNode current = firstNode;
                while (current != null)
                {
                    //把當(dāng)前節(jié)點對象打印出來
                    Console.Write(current.Data + " ");
                    //把下一個節(jié)點設(shè)置為當(dāng)前節(jié)點
                    current = current.Next;
                }
                Console.WriteLine("\n");
            }
        }

以上，從第一個節(jié)點開始，一直循環(huán)到最后一個節(jié)點，current就像一個指針，每打印一個節(jié)點，就把當(dāng)前節(jié)點設(shè)置為下一個節(jié)點，一直循環(huán)下去。

EmptyListException用來拋出鏈表為空的異常。

namespace LinkedListLibrary
{
    public class EmptyListException : Exception
    {
        public EmptyListException() : base("當(dāng)前集合為空"){}
        public EmptyListException(string name) : base("集合" + name + "為空"){}
        public EmptyListException(string exception, Exception inner) : base(exception, inner){}
    }
}

客戶端調(diào)用：

using LinkedListLibrary;
namespace ListTest
{
    class Program
    {
        static void Main(string[] args)
        {
            List list = new List();
            bool aBoolean = true;
            char aChar = 'a';
            int anInt = 12;
            string aStr = "hi";
            list.InsertAtFront(aBoolean);
            list.Display();
            list.InsertAtFront(aChar);
            list.Display();
            list.InsertAtBack(anInt);
            list.Display();
            list.InsertAtBack(aStr);
            list.Display();
            object removeObject;
            try
            {
                removeObject = list.RemoveFromFront();
                Console.WriteLine(removeObject + "被刪除了...");
                list.Display();
                removeObject = list.RemoveFromFront();
                Console.WriteLine(removeObject + "被刪除了...");
                list.Display();
                removeObject = list.RemoveFromBack();
                Console.WriteLine(removeObject + "被刪除了...");
                list.Display();
                removeObject = list.RemoveFromBack();
                Console.WriteLine(removeObject + "被刪除了...");
                list.Display();
            }
            catch (EmptyListException emptyListException)
            {
                Console.Error.WriteLine("\n" + emptyListException);
            }
            Console.ReadKey();
        }
    }
}