數(shù)組在內(nèi)存中的存儲(chǔ)解析 - 全文

一、數(shù)組

數(shù)組在內(nèi)存中是連續(xù)存儲(chǔ)的，所以它的索引速度非?？?，而且賦值與修改元素也很簡(jiǎn)單。

1、一維數(shù)組

聲明一個(gè)數(shù)組：

int［］ array = new int［5］;

初始化一個(gè)數(shù)組：

int［］ array1 = new int［5］ { 1， 3， 5， 7， 9 }; //定長(zhǎng)

聲明并初始化：

int［］ array2 = { 1， 3， 5， 7， 9 }; //不定長(zhǎng)

2、多維數(shù)組

int［，］ numbers = new int［3， 2］ { {1， 2}， {3， 4}， {5， 6} };

但是數(shù)組存在一些不足的地方。在數(shù)組的兩個(gè)數(shù)據(jù)間插入數(shù)據(jù)是很麻煩的，而且在聲明數(shù)組的時(shí)候必須指定數(shù)組的長(zhǎng)度，數(shù)組的長(zhǎng)度過(guò)長(zhǎng)，會(huì)造成內(nèi)存浪費(fèi)，過(guò)短會(huì)造成數(shù)據(jù)溢出的錯(cuò)誤。如果在聲明數(shù)組時(shí)我們不清楚數(shù)組的長(zhǎng)度，就會(huì)變得很麻煩。

針對(duì)數(shù)組的這些缺點(diǎn)，.net中最先提供了ArrayList對(duì)象來(lái)克服這些缺點(diǎn)。

二、ArrayList

ArrayList是命名空間System.Collections下的一部分，在使用該類時(shí)必須進(jìn)行引用，同時(shí)繼承了IList接口，提供了數(shù)據(jù)存儲(chǔ)和檢索。ArrayList對(duì)象的大小是按照其中存儲(chǔ)的數(shù)據(jù)來(lái)動(dòng)態(tài)擴(kuò)充與收縮的。所以，在聲明ArrayList對(duì)象時(shí)并不需要指定它的長(zhǎng)度。

ArrayList list1 = new ArrayList（）; //新增數(shù)據(jù) list1.Add（“cde”）; list1.Add（5678）; //修改數(shù)據(jù) list［2］ = 34; //移除數(shù)據(jù) list.RemoveAt（0）; //插入數(shù)據(jù) list.Insert（0， “qwe”）;

我們從上面的例子看，在List中，我們不僅插入了字符串cde，而且插入了數(shù)字5678。這樣在ArrayList中插入不同類型的數(shù)據(jù)是允許的。因?yàn)锳rrayList會(huì)把所有插入其中的數(shù)據(jù)當(dāng)作為object類型來(lái)處理，在我們使用ArrayList處理數(shù)據(jù)時(shí)，很可能會(huì)報(bào)類型不匹配的錯(cuò)誤，也就是ArrayList不是類型安全的。在存儲(chǔ)或檢索值類型時(shí)通常發(fā)生裝箱和取消裝箱操作，帶來(lái)很大的性能耗損。

補(bǔ)充：數(shù)組擴(kuò)容 這是對(duì)ArrayList效率影響比較大的一個(gè)因素。 每當(dāng)執(zhí)行Add、AddRange、Insert、InsertRange等添加元素的方法，都會(huì)檢查內(nèi)部數(shù)組的容量是否不夠了，如果是，它就會(huì)以當(dāng)前容量的兩倍來(lái)重新構(gòu)建一個(gè)數(shù)組，將舊元素Copy到新數(shù)組中，然后丟棄舊數(shù)組，在這個(gè)臨界點(diǎn)的擴(kuò)容操作，應(yīng)該來(lái)說(shuō)是比較影響效率的。 例1：比如，一個(gè)可能有200個(gè)元素的數(shù)據(jù)動(dòng)態(tài)添加到一個(gè)以默認(rèn)16個(gè)元素大小創(chuàng)建的ArrayList中，將會(huì)經(jīng)過(guò)： 16*2*2*2*2 = 256 四次的擴(kuò)容才會(huì)滿足最終的要求，那么如果一開(kāi)始就以： ArrayList List = new ArrayList（ 210 ）; 的方式創(chuàng)建ArrayList，不僅會(huì)減少4次數(shù)組創(chuàng)建和Copy的操作，還會(huì)減少內(nèi)存使用。 例2：預(yù)計(jì)有30個(gè)元素而創(chuàng)建了一個(gè)ArrayList： ArrayList List = new ArrayList（30）; 在過(guò)程中，加入了31個(gè)元素，那么數(shù)組會(huì)擴(kuò)充到60個(gè)元素的大小，而這時(shí)候不會(huì)有新的元素再增加進(jìn)來(lái)，而且有沒(méi)有調(diào)用TrimSize方法，那么就有1次擴(kuò)容的操作，并且浪費(fèi)了29個(gè)元素大小的空間。如果這時(shí)候，用： ArrayList List = new ArrayList（40）; 那么一切都解決了。 所以說(shuō)，正確的預(yù)估可能的元素，并且在適當(dāng)?shù)臅r(shí)候調(diào)用TrimSize方法是提高ArrayList使用效率的重要途徑。

三、List 因?yàn)锳rrayList存在不安全類型與裝箱拆箱的缺點(diǎn)，所以出現(xiàn)了泛型的概念。List類是ArrayList類的泛型等效類，它的大部分用法都與ArrayList相似，因?yàn)長(zhǎng)ist類也繼承了IList接口。最關(guān)鍵的區(qū)別在于，在聲明List集合時(shí)，我們同時(shí)需要為其聲明List集合內(nèi)數(shù)據(jù)的對(duì)象類型。

List《string》 list = new List《string》（）; //新增數(shù)據(jù) list.Add（“abc”）; //修改數(shù)據(jù) list［0］ = “def”; //移除數(shù)據(jù) list.RemoveAt（0）;

四、LinkedList

然而數(shù)組和數(shù)組列表都有一個(gè)重大的缺陷，這就是從數(shù)組的中間位置刪除一個(gè)元素需要付出很大的代價(jià)，其原因是數(shù)組中處于被刪除元素之后的所有元素都要向數(shù)組的前端移動(dòng)。在數(shù)組的中間的位置插入一個(gè)元素也是如此。如下圖：

這個(gè)問(wèn)題就靠LinkedList（鏈表）來(lái)解決。鏈表將每個(gè)對(duì)象存放在獨(dú)立的節(jié)點(diǎn)中，每個(gè)節(jié)點(diǎn)還存放著序列中上一個(gè)節(jié)點(diǎn)的引用和下一個(gè)節(jié)點(diǎn)的引用，如下圖：

這樣，從鏈表中間刪除一個(gè)元素是很輕松的操作，即需要對(duì)唄刪除元素附近的節(jié)點(diǎn)更新一下即可，如下圖：

List names=new LinkedList《》（）; names.add（“Amy”）; names.add（“Bob”）;

總結(jié)：

數(shù)組的容量是固定的，只能一次獲取或設(shè)置一個(gè)元素的值，而ArrayList或List的容量可根據(jù)需要自動(dòng)擴(kuò)充、修改、刪除或插入數(shù)據(jù)。

數(shù)組可以具有多個(gè)維度，而 ArrayList或 List《 T》 始終只具有一個(gè)維度。但是，可以輕松創(chuàng)建數(shù)組列表或列表的列表。特定類型（Object 除外）的數(shù)組 的性能優(yōu)于 ArrayList的性能。 這是因?yàn)?ArrayList的元素屬于 Object 類型；所以在存儲(chǔ)或檢索值類型時(shí)通常發(fā)生裝箱和取消裝箱操作。不過(guò)，在不需要重新分配時(shí)（即最初的容量十分接近列表的最大容量），List《 T》 的性能與同類型的數(shù)組十分相近。

在決定使用 List 還是使用ArrayList 類（兩者具有類似的功能）時(shí)，記住List 類在大多數(shù)情況下執(zhí)行得更好并且是類型安全的。如果對(duì)List《 T》 類的類型T 使用引用類型，則兩個(gè)類的行為是完全相同的。但是，如果對(duì)類型T使用值類型，則需要考慮實(shí)現(xiàn)和裝箱問(wèn)題。

ArrayList是實(shí)現(xiàn)了基于動(dòng)態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)，LinkedList基于鏈表的數(shù)據(jù)結(jié)構(gòu)。

對(duì)于隨機(jī)訪問(wèn)get和set，ArrayList覺(jué)得優(yōu)于LinkedList，因?yàn)長(zhǎng)inkedList要移動(dòng)指針。

對(duì)于新增和刪除操作add和remove，LinedList比較占優(yōu)勢(shì)，因?yàn)锳rrayList要移動(dòng)數(shù)據(jù)。