數據結構之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，有興趣的可以看一下：

 

 

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

※評比前十大台北網頁設計、台北網站設計公司知名案例作品心得分享

※智慧手機時代的來臨，RWD網頁設計已成為網頁設計推薦首選

※評比南投搬家公司費用收費行情懶人包大公開