資料結構之Array、ArrayList、List、LinkedList對比分析-有解無憂

一、前言：

　　在c#資料結構中，集合的應用非常廣泛，無論是做BS架構還是CS架構開發，都離不開集合的使用，比如我們常見的集合包括：Array、ArrayList、List、LinkedList等，這一些資料集合，在功能上都能夠實作集合的存取，但是他們內部有什么區別，在使用時需要注意一些什么呢？下面根據個人的經驗，對這一些集合資料的使用做一個簡單的小結，如果說的不對的地方，歡迎指出，多多交流改進，

二、Array集合簡介

　　Array集合，也就是陣列，是最簡單的資料結構，其存盤的資料在記憶體空間是連續的，陣列有一下一些特點

1.資料存盤是連續的
2.陣列長度在定義時就必須制定
3.陣列存盤的資料型別都是同一型別
4.陣列可以直接通過小標訪問

　　優缺點：
　 優點：
　　1、可以根據索引直接訪問，訪問速度快
　 2、資料是安全的，由于資料型別一致性，在存盤使用程序中不涉及
　　缺點：
　　1、由于資料是連續存盤的，導致插入效率變慢
　 2、由于陣列長度大小固定，那么對預期非固定長度的數字不好處理

　　練習實體代碼：

    /// <summary>
    /// 陣列練習操作 
    /// </summary>
    public class ArrayTest
    {
        /// 陣列 Array 對于大家來說一點都不陌生
        /// 陣列是在記憶體連續分配的存盤空間，這也導致陣列有一下一些特點
        /// 1.資料存盤是連續的
        /// 2.陣列長度在定義時就必須制定
        /// 3.陣列存盤的資料型別都是同一型別
        /// 4.陣列可以直接通過小標訪問
        /// 
        /// 優缺點：
        /// 優點：
        ///     1、可以根據索引直接訪問，訪問速度快
        ///     2、資料是安全的，由于資料型別一致性，在存盤使用程序中不涉及到裝箱拆箱操作
        /// 缺點：
        ///     1、由于資料是連續存盤的，導致插入效率變慢
        ///     2、由于陣列長度大小固定，那么對預期非固定長度的數字不好處理

        /// int型別的陣列操作 
        public static void IntArrayTest()
        {

            //// 定義一個秒表，執行獲取執行時間
            Stopwatch st = new Stopwatch();//實體化類
            st.Start();//開始計時

            Console.WriteLine("開始初始化長度為10000000的int陣列：");

            //// 定義一個陣列
            int[] nums = new int[10000000];
            for (int i = 0; i < 10000000; i++)
            {
                nums[i] = 1 + 1;
            }

            //需要統計時間的代碼段

            st.Stop();//終止計時
            Console.WriteLine(string.Format("初始化長度為10000的int陣列完畢！總耗時{0}毫秒", st.ElapsedMilliseconds.ToString()));
        }
    }

三、ArrayList集合簡介

ArrayList 是Array的升級版，能夠解決Array的一些缺點
ArrayList其內部實作也是Array，只是其長度是可以動態，在其內部用一個變數記錄控制長度，ArrayList有如下一些特點

1.長度不固定
2.可以存盤不同的資料型別(object)
3.同樣支持索引查詢（可以直接通過小標訪問）
4.靈活性更強，以犧牲性能為代價

優缺點：
優點：
1、長度不固定，在定義是不必擔長度溢位
2、可以存盤任意資料型別
3、可根據索引查詢，查詢效率快
缺點：
1、由于長度不固定，執行效率低下，因為超出默認長度（10）后，會自動擴容拷貝資料，犧牲性能
2、由于存盤型別是object,所以在存資料時會有裝箱操作，在取資料時會有拆箱操作，影響效率
3、執行緒不安全，因為其內部實作是用size、array來共同控制，在新增操作時是非原子操作，所以非安全執行緒

使用技巧：
在實際使用程序中，為了避免自動擴容，可以預估資料長度，初始化一個資料長度，從而提高效率

練習實體代碼：

    /// <summary>
    /// ArrayList陣列練習操作 
    /// </summary>
    public class ArrayListTest
    {
        /// ArrayList 是Array的升級版，能夠解決Array的一些缺點
        /// ArrayList其內部實作也是Array，只是其長度是可以動態，在其內部用一個變數記錄控制長度，ArrayList有如下一些特點
        /// 1.長度不固定
        /// 2.可以存盤不同的資料型別(object)
        /// 3.同樣支持索引查詢（可以直接通過小標訪問）
        /// 4.靈活性更強，以犧牲性能為代價

        /// 優缺點：
        /// 優點：
        ///     1、長度不固定，在定義是不必擔長度溢位
        ///     2、可以存盤任意資料型別
        ///     3、可根據索引查詢，查詢效率快
        /// 缺點：
        ///     1、由于長度不固定，執行效率低下，因為超出默認長度（10）后，會自動擴容拷貝資料，犧牲性能
        ///     2、由于存盤型別是object,所以在存資料時會有裝箱操作，在取資料時會有拆箱操作，影響效率
        ///     3、執行緒不安全，因為其內部實作是用size、array來共同控制，在新增操作時是非原子操作，所以非安全執行緒
        ///     
        /// 使用技巧：
        ///     在實際使用程序中，為了避免自動擴容，可以預估資料長度，初始化一個資料長度，從而提高效率

        /// ArrayList操作實體
        public static void ArrayListOpert()
        {

            //// 定義一個秒表，執行獲取執行時間
            Stopwatch st = new Stopwatch();//實體化類

            //// 需要統計時間的代碼段(統計初始化長度時的執行時間)
            st.Start();//開始計時
            Console.WriteLine("");
            Console.WriteLine("");
            Console.WriteLine("ArryList集合存盤資料量為10000000，初始化一個長度，執行開始：");

            ArrayList arrayList = new ArrayList(10000000);

            //// 定義一個陣列
            for (int i = 0; i < 10000000; i++)
            {
                arrayList.Add(1 + 1);
            }

            st.Stop();//終止計時
            Console.WriteLine(string.Format("ArryList集合存盤資料量為10000000，初始化一個長度，執行完畢：！總耗時{0}毫秒", st.ElapsedMilliseconds.ToString()));

            //// 需要統計時間的代碼段(統計初始化非指定長度時的執行時間)

            st.Restart();
            Console.WriteLine("");
            Console.WriteLine("ArryList集合存盤資料量為10000000，初始化不指定長度，執行開始：");

            arrayList = new ArrayList();

            //// 定義一個陣列
            for (int i = 0; i < 10000000; i++)
            {
                arrayList.Add(1 + 1);
            }

            st.Stop();//終止計時
            Console.WriteLine(string.Format("ArryList集合存盤資料量為10000000，初始化不指定長度，執行完畢：！總耗時{0}毫秒", st.ElapsedMilliseconds.ToString()));
        }
    }

四、List集合簡介

隨著c#泛型的推出，為了避免ArrayList一些缺點，微軟推出了List集合
List集合內部還是采用的Array實作，同時在定義時需要指定對應的資料型別
這樣級保留了Array集合的優點，同時也避免了ArrayList集合的資料型別不安全和裝箱帶來的性能犧牲
List特點：

1、資料長度不固定，自動增加
2、存盤相同的資料型別
3、可根據索引查詢，查詢效率快

優缺點：
優點：
1、長度不固定，在定義是不必擔長度溢位
2、存盤相同資料型別的資料，避免的資料的裝箱拆箱，提高了資料處理效率
3、支持索引查詢，查詢效率快
缺點：
1、由于長度不固定，執行效率低下，因為超出默認長度（10）后，會自動擴容拷貝資料，犧牲性能
2、執行緒不安全，因為其內部實作是用size、array來共同控制，在新增操作時是非原子操作，所以非安全執行緒

練習實體代碼：

   /// <summary>
    /// List練習操作
    /// </summary>
    public class ListTest
    {
        /// 隨著c#泛型的推出，為了避免ArrayList一些缺點，微軟推出了List集合
        /// List集合內部還是采用的Array實作，同時在定義時需要指定對應的資料型別
        /// 這樣級保留了Array集合的優點，同時也避免了ArrayList集合的資料型別不安全和裝箱帶來的性能犧牲
        /// List特點：
        /// 1、資料長度不固定，自動增加
        /// 2、存盤相同的資料型別
        /// 3、可根據索引查詢，查詢效率快
        /// 
        /// 優缺點：
        /// 優點：
        ///     1、長度不固定，在定義是不必擔長度溢位
        ///     2、存盤相同資料型別的資料，避免的資料的裝箱拆箱，提高了資料處理效率
        ///     3、支持索引查詢，查詢效率快
        /// 缺點：
        ///     1、由于長度不固定，執行效率低下，因為超出默認長度（10）后，會自動擴容拷貝資料，犧牲性能
        ///     2、執行緒不安全，因為其內部實作是用size、array來共同控制，在新增操作時是非原子操作，所以非安全執行緒

        /// ArrayList操作實體
        public static void ListOpert()
        {
            //// 定義一個秒表，執行獲取執行時間
            Stopwatch st = new Stopwatch();//實體化類
            st.Start();//開始計時
                       //// 需要統計時間的代碼段(統計初始化長度時的執行時間)
            Console.WriteLine("");
            Console.WriteLine("");
            Console.WriteLine("List集合存盤資料量為10000000，初始化一個長度，執行開始：");

            List<int> list = new List<int>(10000000);

            //// 定義一個陣列
            for (int i = 0; i < 10000000; i++)
            {
                list.Add(1 + 1);
            }

            //需要統計時間的代碼段

            st.Stop();//終止計時
            Console.WriteLine(string.Format("List集合存盤資料量為10000000，初始化一個長度，執行完畢：！總耗時{0}毫秒", st.ElapsedMilliseconds.ToString()));

            //// 需要統計時間的代碼段(統計初始化非指定長度時的執行時間)
            st.Restart();
            Console.WriteLine("");
            Console.WriteLine("List集合存盤資料量為10000000，初始化不指定長度，執行開始：");

            list = new List<int>();

            //// 定義一個陣列
            for (int i = 0; i < 10000000; i++)
            {
                list.Add(1 + 1);
            }

            st.Stop();//終止計時
            Console.WriteLine(string.Format("List集合存盤資料量為10000000，初始化不指定長度，執行完畢：！總耗時{0}毫秒", st.ElapsedMilliseconds.ToString()));
        }
    }

五、LinkedList集合簡介

LinkedList鏈表的底層是采用雙向鏈表的方式實作，
在鏈表（Linked List）中，每一個元素都指向下一個元素，以此來形成了一個鏈（chain）
可以從頭部和尾部插入資料，在存盤記憶體上采用非連續方式存盤，鏈表有如下一些特點

1、記憶體存盤上是非連續的
2、能夠支持從頭部和底部同時插入
3、長度是非固定的

優缺點：
優點：
1、由于非連續存盤，中部插入和洗掉元素效率高
2、長度非固定，在創建時不用考慮其長度
3、可以沖頭部和底部添加元素
4、資料型別是安全的，在創建時需要指定的資料型別
缺點：
1、由于非連續存盤，不能通過小標訪問，查詢效率低

練習實體代碼：

    /// <summary>
    /// LinkedList練習操作
    /// </summary>
    public class LinkedListTest {
        /// LinkedList鏈表的底層是采用雙向鏈表的方式實作，
        /// 在鏈表（Linked List）中，每一個元素都指向下一個元素，以此來形成了一個鏈（chain）
        /// 可以從頭部和尾部插入資料，在存盤記憶體上采用非連續方式存盤，鏈表有如下一些特點
        /// 1、記憶體存盤上是非連續的
        /// 2、能夠支持從頭部和底部同時插入
        /// 3、長度是非固定的
        /// 優缺點：
        /// 優點：
        ///     1、由于非連續存盤，中部插入和洗掉元素效率高
        ///     2、長度非固定，在創建時不用考慮其長度
        ///     3、可以沖頭部和底部添加元素
        ///     4、資料型別是安全的，在創建時需要指定的資料型別
        ///  缺點：
        ///     1、由于非連續存盤，不能通過小標訪問，查詢效率低

        /// LinkedList操作實體
        public static void LinkedListTestOpert() {
            //// 定義一個秒表，執行獲取執行時間
            Stopwatch st = new Stopwatch();//實體化類
            st.Start();//開始計時
                       //// 需要統計時間的代碼段(統計初始化長度時的執行時間)
            Console.WriteLine("");
            Console.WriteLine("");
            Console.WriteLine("Linked集合存盤資料量為10000000，執行開始：");

            LinkedList<int> list = new LinkedList<int>();

            //// 定義一個陣列
            for (int i = 0; i < 10000000; i++)
            {
                list.AddFirst(1 + 1);
            }

            //需要統計時間的代碼段

            st.Stop();//終止計時
            Console.WriteLine(string.Format("Linked集合存盤資料量為10000000，執行完畢：！總耗時{0}毫秒", st.ElapsedMilliseconds.ToString()));
        }
    }

六、每種集合資料執行結果對比分析

    class Program
    {
        static void Main(string[] args)
        {
            //// array陣列操作測驗
            ArrayTest.IntArrayTest();

            //// arrayList集合操測驗
            ArrayListTest.ArrayListOpert();

            //// List集合操作測驗
            ListTest.ListOpert();

            //// LinkedList集合操作測驗
            LinkedListTest.LinkedListTestOpert();

            ///// 通過測驗資料
            //通過測驗資料大概可以分析得出一些結論
            //1、整體效率上Array效率最高，ArrayList效率最低，List效率介于Array和ArrayList之間
            //2、ArrayList和List集合，在定義時如果知道資料長度，那么初始化時，指定長度的效率比不指定的長度效率高
            
            
            //總結：
            //在資料集合使用選擇上給出以下一些建議：
            //1、Array：當元素的數量是固定的，并且需要使用下標時
            //2、ArrayList：當存盤的元素型別不同時
            //3、List：當元素的數量是固定的，并且需要使用下標時
            //4、LinkedList：當元素需要能夠在串列的兩端添加時
            Console.ReadLine();
        }
    }

　　執行結果資料

通過測驗資料大概可以分析得出一些結論
1、整體效率上Array效率最高，ArrayList效率最低，List效率介于Array和ArrayList之間
2、ArrayList和List集合，在定義時如果知道資料長度，那么初始化時，指定長度的效率比不指定的長度效率高

七、總結：

在資料集合使用選擇上給出以下一些建議：
1、Array：當元素的數量是固定的，并且需要使用下標時
2、ArrayList：當存盤的元素型別不同時，初始化時給一個預估的長度
3、List：當元素的數量是固定的，并且需要使用下標時，初始化時給一個預估的長度
4、LinkedList：當元素需要能夠在串列的兩端添加時

附件：

關于這一些練習的代碼，上傳到github，有興趣的可以看一下：

https://github.com/xuyuanhong0902/dataStructureTest.git

轉載請註明出處，本文鏈接：https://www.uj5u.com/net/103488.html

標籤：C#

上一篇：C#泛型自己的理解和總結

下一篇：13. 羅馬數字轉整數(C#)