比較:Array與List

  • 1016
  • 0
  • C#
  • 2020-06-04

接續上篇《初識資料結構 - 最常被使用的物件容器?!》,此篇會針對Array與List做詳盡的解釋。

其實不論使用Array或List,它們在存儲元素資料之前,都會以Node節點(index)來包裝,所以每一元素都被一個Node所包裝。
以下將以圖解來介紹兩者區別,方便讓大家理解。
 

這裡宣告了一個變數為c的陣列,陣列的大小為9,index 0~8:
讓我們來一探Array的特點吧!


Array支援直接存取(Random access)?!而List無法做到?!

我們可以透過解決以下問題來釐清,為什麼Array支援直接存取。
例如:輸出集合中第5個元素;以及我想將集合中第9個元素修改為cyan,請問要怎麼做?

            Color[] c = new Color[9];//宣告陣列:c[]用來存儲Color物件

            for (int i = 0; i < c.Length; i++)
            {
                c[i] = new Color();//宣告Color物件:使用new運算符
                switch (i)
                {
                    case 0:
                        c[i].ConsoleColor = ConsoleColor.Red;
                        c[i].Name = "red";
                        break;
                    case 1:
                        c[i].ConsoleColor = ConsoleColor.Yellow;
                        break;
                    case 2:
                        c[i].ConsoleColor = ConsoleColor.Blue;
                        break;
                    case 3:
                        c[i].ConsoleColor = ConsoleColor.Black;
                        break;
                    case 4:
                        c[i].ConsoleColor = ConsoleColor.White;
                        break;
                    case 5:
                        c[i].ConsoleColor = ConsoleColor.Gray;
                        c[i].Name = "gray";
                        break;
                    case 6:
                        c[i].ConsoleColor = ConsoleColor.Green;
                        break;
                    case 7:
                        c[i].ConsoleColor = ConsoleColor.Magenta;
                        break;
                    case 8:
                        c[i].ConsoleColor = ConsoleColor.DarkYellow;
                        break;
                    default:
                        break;
                }
            }


            Console.WriteLine(c[4].ConsoleColor);

輸出結果:White
 //輸出集合中第5個元素,index=4
   

c[8].ConsoleColor = ConsoleColor.Cyan;
Console.WriteLine(c[8].ConsoleColor);

輸出結果:Cyan
 //修改集合中第9個元素為cyan,index=8 

其實Array尋訪集合中的元素其原理很簡單,就是尋訪Node,但因為Node彼此緊鄰
因此電腦很容易就計算出每個Node其所在的記憶體位置,我們也可以說每個Node就指向一個固定大小的記憶體空間。
以此例,c陣列中每個元素所占的空間都是4個byte,因此如果我想要得到c陣列中某個元素的記憶體位置,是不是很容易就能推敲出來了呢?
假設說我們已知c[0]的記憶體位置為0x100218200,那麼我們也能很直觀的知道c[4]的記憶體位置為0x100218216、c[8]的記憶體位置為0x100218232。
這就是為什麼Array的Node並不需要存儲(紀錄)下一個Node的記憶體位置的原因。


Array的直接存取就好像使用GPS導航,假設說我想去合歡山,我可以直接使用map定位當前所在位置、目的地位置,就可以順利地抵達目的地。

Array的優點:

Array的元素在記憶體中是連續地存放,因此可以通過索引直接定位到某一個元素,這就是直接存取(Random access)。
如果我們可以直觀地知道某元素的記憶體位置來達到快速存取,這就是直接存取的核心概念。

Array的缺點:
新增或移除元素時,非常耗費時間;

新增時,假設我想插入某元素到第二個元素這個位置,但我必須將原先佔據第二個元素位置的值以及其後面所有元素的值,
往後搬移一個、到(原索引值+1)的位置,以空出一個位置為了存放新的值;另外,還必須考慮插入新值後,會不會有索引超出範圍的問題,可使用Array.Resize() 的方法,重設陣列大小。

移除時,假設我想移除第二個元素這個位置的值,所以移除後,第二個元素這個位置就空出來了,然而其後面所有元素的值,
我們必須往前搬移一個、到(原索引值-1)的位置,以遞補移除值後的空位。
簡單來說,我們必須確保元素的排列,在陣列中有連續位置的特性,這就是為什麼Array在插入與移除元素特別不靈活的原因。

Array使用時機:

  • 已知需要處理資料的數量,以便設定陣列大小。
  • 希望能夠快速存取資料。
  • 處理重複性的資料、資料量較大時。
  • 要求記憶體空間使用愈少愈好。
     

首先要了解List的內部運作方式,才能進一步分辨List的使用時機。

List由於實作LinkedList所以它只支援循序存取(Sequential access)。

List尋訪集合中的元素時,也是透過尋訪Node,但因為Node彼此分散在不連續記憶體位置,所以尋訪的困難度就增加了!

這裡宣告了一個變數為intList的串列,沒有設定串列大小:
讓我們來一探List的特點吧!

List的特點是,不論是宣告串列時就將元素初始化,還是透過方法Add新增元素,
我們都要知道每一個Node包裝的元素與下一個Node之間,彼此的記憶體不是連續的。

            List<int> intList = new List<int>();
            intList.Add(2);
            intList.Add(14);
            intList.Add(33);
            intList.Add(106);
            intList.Add(96);
            foreach (var item in intList)
            {
                Console.WriteLine(item);
            }

輸出結果:
2
14
33
106
96

List的缺點:

這段程式碼背後的意義是,每個包含在Node裡的元素,除了知道自己的值與下一個Node的記憶體位址,其他都不知道
所以就形成了一個Node串接下一個Node、下一個Node串接下下一個Node…....,因此當我們想要得到集合中的某個元素時,
也只能透過一一尋訪Node來找到值,這就是為什麼使用List來讀取較大量的資訊時,效能會特別差。

List的元素在記憶體中沒有連續地存放,而是通過指針連在一起,為了訪問某一元素,必須從串列頭開始順著指針才能找到某一個元素,這就是循序存取(Sequential access)。也就是說,元素實體沒有連續地排列,而只是「邏輯上」的順序排列而已。

List的循序存取(Sequential access)就好像活在沒有GPS導航的年代,想到達目的地是透過"問路人",每次開車開到覺得迷路的時候,就問一下路人,這個過程就跟List一個Node、一個Node的尋訪很相像,不是嗎?

List能夠支援動態插入、動態移除?!而Array做不到?!

我們可以透過解決以下問題來釐清,為什麼List支援動態插入、動態移除。
例如:接續上面那段程式碼,從Node2與Node3之間插入Node6;以及我想將Node4移除,請問要怎麼做?

            intList.Insert(2, 87);
            intList.RemoveAt(4);
            foreach (var item in intList)
            {
                Console.WriteLine(item);
            }

輸出結果:
2
14
87
33
96

這段程式碼背後的意義是,不論插入或移除Node,其實最終只是對Node中Next記憶體位址作改變

  1. 從Node2與Node3之間插入Node6,它的運作是Node6會先通知Node2你的下一個是我喔,然後請Node2將原來的Next交給自己,所以Node6也就知道它的下一個是Node3了。
  2. 將Node4移除,它的運作是Node4會先通知Node3我要被移除了,並且把自己的Next交給Node3,那麼Node3也就知道它的下一個是Node5了。

List的優點:

彈性靈活,能動態跟記憶體要空間、或釋放空間。

List的使用時機:

  • 需要頻繁地插入或移除資料時。
  • 無法預期資料數量時。
  • 不需要快速查詢資料時,適合處理資料量較少時。

   [注意]使用物件容器時,必須留意變數的索引值index,不可超出宣告的範圍大小。
           

 // 例如
            List<int> intList = new List<int>(){13,43,75,25};
          
            Console.WriteLine(intList[4]);

輸出結果:
ArgumentOutOfRangeException: 索引超出範圍

結論:
有關Array與List的全面性介紹就到這裡,下篇要為大家介紹另一種物件容器Dictionary,
它有著Array與List沒有的特點。《認識Dictionary<TKey,TValue>》

那麼,下篇見!

如有敘述錯誤,還請不吝嗇留言指教,thanks!