常用的數(shù)據(jù)結(jié)構(gòu)總結(jié)與分析！一文給你解決！
1.幾種常見的數(shù)據(jù)結(jié)構(gòu)
這里主要總結(jié)下在工作中常碰到的幾種數(shù)據(jù)結(jié)構(gòu)：Array，ArrayList，List<T>，LinkedList<T>，Queue<T>，Stack<T>，Dictionary<K,T>
數(shù)組Array：
數(shù)組是最簡單的數(shù)據(jù)結(jié)構(gòu)。其具有如下特點：
數(shù)組存儲在連續(xù)的內(nèi)存上。
數(shù)組的內(nèi)容都是相同類型。
數(shù)組可以直接通過下標(biāo)訪問。
數(shù)組Array的創(chuàng)建：
創(chuàng)建一個新的數(shù)組時將在 CLR 托管堆中分配一塊連續(xù)的內(nèi)存空間，來盛放數(shù)量為size，類型為所聲明類型的數(shù)組元素。如果類型為值類型，則將會有size個未裝箱的該類型的值被創(chuàng)建。如果類型為引用類型，則將會有size個相應(yīng)類型的引用被創(chuàng)建。
由于是在連續(xù)內(nèi)存上存儲的，所以它的索引速度非?？?，訪問一個元素的時間是恒定的也就是說與數(shù)組的元素數(shù)量無關(guān)，而且賦值與修改元素也很簡單。
但是有優(yōu)點，那么就一定會伴隨著缺點。由于是連續(xù)存儲，所以在兩個元素之間插入新的元素就變得不方便。而且就像上面的代碼所顯示的那樣，聲明一個新的數(shù)組時，必須指定其長度，這就會存在一個潛在的問題，那就是當(dāng)我們聲明的長度過長時，顯然會浪費內(nèi)存，當(dāng)我們聲明長度過短的時候，則面臨這溢出的風(fēng)險。這就使得寫代碼像是投機，很厭惡這樣的行為！針對這種缺點，下面隆重推出ArrayList。
ArrayList：
為了解決數(shù)組創(chuàng)建時必須指定長度以及只能存放相同類型的缺點而推出的數(shù)據(jù)結(jié)構(gòu)。ArrayList是System.Collections命名空間下的一部分，所以若要使用則必須引入System.Collections。正如上文所說，ArrayList解決了數(shù)組的一些缺點。
不必在聲明ArrayList時指定它的長度，這是由于ArrayList對象的長度是按照其中存儲的數(shù)據(jù)來動態(tài)增長與縮減的。
ArrayList可以存儲不同類型的元素。這是由于ArrayList會把它的元素都當(dāng)做Object來處理。因而，加入不同類型的元素是允許的。
ArrayList的操作：
說了那么一堆”優(yōu)點“，也該說說缺點了吧。為什么要給”優(yōu)點”打上引號呢？那是因為ArrayList可以存儲不同類型數(shù)據(jù)的原因是由于把所有的類型都當(dāng)做Object來做處理，也就是說ArrayList的元素其實都是Object類型的，辣么問題就來了。
ArrayList不是類型安全的。因為把不同的類型都當(dāng)做Object來做處理，很有可能會在使用ArrayList時發(fā)生類型不匹配的情況。
如上文所訴，數(shù)組存儲值類型時并未發(fā)生裝箱，但是ArrayList由于把所有類型都當(dāng)做了Object，所以不可避免的當(dāng)插入值類型時會發(fā)生裝箱操作，在索引取值時會發(fā)生拆箱操作。這能忍嗎？
注：為何說頻繁的沒有必要的裝箱和拆箱不能忍呢？所謂裝箱 (boxing)：就是值類型實例到對象的轉(zhuǎn)換(百度百科)。那么拆箱：就是將引用類型轉(zhuǎn)換為值類型咯（還是來自百度百科）。下面舉個栗子~
那么結(jié)論呢？顯然，從原理上可以看出，裝箱時，生成的是全新的引用對象，這會有時間損耗，也就是造成效率降低。
List<T>泛型List
為了解決ArrayList不安全類型與裝箱拆箱的缺點，所以出現(xiàn)了泛型的概念，作為一種新的數(shù)組類型引入。也是工作中經(jīng)常用到的數(shù)組類型。和ArrayList很相似，長度都可以靈活的改變，最大的不同在于在聲明List集合時，我們同時需要為其聲明List集合內(nèi)數(shù)據(jù)的對象類型，這點又和Array很相似，其實List<T>內(nèi)部使用了Array來實現(xiàn)。
這么做最大的好處就是
即確保了類型安全。
也取消了裝箱和拆箱的操作。
它融合了Array可以快速訪問的優(yōu)點以及ArrayList長度可以靈活變化的優(yōu)點。
LinkedList<T>
也就是鏈表了。和上述的數(shù)組最大的不同之處就是在于鏈表在內(nèi)存存儲的排序上可能是不連續(xù)的。這是由于鏈表是通過上一個元素指向下一個元素來排列的，所以可能不能通過下標(biāo)來訪問。如圖
既然鏈表最大的特點就是存儲在內(nèi)存的空間不一定連續(xù)，那么鏈表相對于數(shù)組最大優(yōu)勢和劣勢就顯而易見了。
向鏈表中插入或刪除節(jié)點無需調(diào)整結(jié)構(gòu)的容量。因為本身不是連續(xù)存儲而是靠各對象的指針?biāo)鶝Q定，所以添加元素和刪除元素都要比數(shù)組要有優(yōu)勢。
鏈表適合在需要有序的排序的情境下增加新的元素，這里還拿數(shù)組做對比，例如要在數(shù)組中間某個位置增加新的元素，則可能需要移動移動很多元素，而對于鏈表而言可能只是若干元素的指向發(fā)生變化而已。
有優(yōu)點就有缺點，由于其在內(nèi)存空間中不一定是連續(xù)排列，所以訪問時候無法利用下標(biāo)，而是必須從頭結(jié)點開始，逐次遍歷下一個節(jié)點直到尋找到目標(biāo)。所以當(dāng)需要快速訪問對象時，數(shù)組無疑更有優(yōu)勢。
綜上，鏈表適合元素數(shù)量不固定，需要經(jīng)常增減節(jié)點的情況。
示例：
下面的代碼示例演示了類的許多功能LinkedList<T>。
Queue<T>
在Queue<T>這種數(shù)據(jù)結(jié)構(gòu)中，最先插入在元素將是最先被刪除；反之最后插入的元素將最后被刪除，因此隊列又稱為“先進(jìn)先出”（FIFO—first in first out）的線性表。通過使用Enqueue和Dequeue這兩個方法來實現(xiàn)對 Queue<T> 的存取。
一些需要注意的地方：
先進(jìn)先出的情景。
默認(rèn)情況下，Queue<T>的初始容量為32， 增長因子為2.0。
當(dāng)使用Enqueue時，會判斷隊列的長度是否足夠，若不足，則依據(jù)增長因子來增加容量，例如當(dāng)為初始的2.0時，則隊列容量增長2倍。
乏善可陳。
示例：
下面的代碼示例演示了泛型類的幾個方法 Queue<T> 。 此代碼示例創(chuàng)建具有默認(rèn)容量的字符串隊列，并使用 Enqueue 方法將五個字符串進(jìn)行排隊。 枚舉隊列的元素，而不會更改隊列的狀態(tài)。 Dequeue方法用于取消對第一個字符串的排隊。 Peek方法用于查看隊列中的下一項，然后 Dequeue 使用方法將其取消排隊。
ToArray方法用于創(chuàng)建數(shù)組，并將隊列元素復(fù)制到該數(shù)組，然后將數(shù)組傳遞給 Queue<T> 采用的構(gòu)造函數(shù) IEnumerable<T> ，創(chuàng)建隊列的副本。 將顯示副本的元素。
創(chuàng)建隊列大小兩倍的數(shù)組，并 CopyTo 使用方法從數(shù)組中間開始復(fù)制數(shù)組元素。 在 Queue<T> 開始時，將再次使用構(gòu)造函數(shù)來創(chuàng)建包含三個 null 元素的隊列的第二個副本。
Contains方法用于顯示字符串 "四" 位于隊列的第一個副本中，在此之后， Clear 方法會清除副本， Count 屬性顯示該隊列為空。
Stack<T>
與Queue<T>相對，當(dāng)需要使用后進(jìn)先出順序（LIFO）的數(shù)據(jù)結(jié)構(gòu)時，我們就需要用到Stack<T>了。
一些需要注意的地方：
后進(jìn)先出的情景。
默認(rèn)容量為10。
使用pop和push來操作。
乏善可陳。
示例:
下面的代碼示例演示了泛型類的幾個方法 Stack<T> 。 此代碼示例創(chuàng)建一個具有默認(rèn)容量的字符串堆棧，并使用 Push 方法將五個字符串推送到堆棧上。 枚舉堆棧的元素，這不會更改堆棧的狀態(tài)。 Pop方法用于彈出堆棧中的第一個字符串。 Peek方法用于查看堆棧上的下一項，然后 Pop 使用方法將它彈出。
ToArray方法用于創(chuàng)建數(shù)組，并將堆棧元素復(fù)制到該數(shù)組，然后將該數(shù)組傳遞給 Stack<T> 采用的構(gòu)造函數(shù)，并 IEnumerable<T> 使用反轉(zhuǎn)元素的順序創(chuàng)建堆棧副本。 將顯示副本的元素。
創(chuàng)建堆棧大小兩倍的數(shù)組，并 CopyTo 使用方法從數(shù)組中間開始復(fù)制數(shù)組元素。 Stack<T>再次使用構(gòu)造函數(shù)來創(chuàng)建具有反轉(zhuǎn)的元素順序的堆棧副本; 因此，這三個 null 元素位于末尾。
Contains方法用于顯示字符串 "四" 位于堆棧的第一個副本中，在此之后， Clear 方法會清除副本， Count 屬性會顯示堆棧為空。
Dictionary<K,T>
提到字典就不得不說Hashtable哈希表以及Hashing（哈希，也有叫散列的），因為字典的實現(xiàn)方式就是哈希表的實現(xiàn)方式，只不過字典是類型安全的，也就是說當(dāng)創(chuàng)建字典時，必須聲明key和item的類型，這是第一條字典與哈希表的區(qū)別。關(guān)于哈希，簡單的說就是一種將任意長度的消息壓縮到某一固定長度，比如某學(xué)校的學(xué)生學(xué)號范圍從00000~99999，總共5位數(shù)字，若每個數(shù)字都對應(yīng)一個索引的話，那么就是100000個索引，但是如果我們使用后3位作為索引，那么索引的范圍就變成了000~999了，當(dāng)然會沖突的情況，這種情況就是哈希沖突(Hash Collisions)了。
回到Dictionary<K,T>，我們在對字典的操作中各種時間上的優(yōu)勢都享受到了，那么它的劣勢到底在哪呢？對嘞，就是空間。以空間換時間，通過更多的內(nèi)存開銷來滿足我們對速度的追求。在創(chuàng)建字典時，我們可以傳入一個容量值，但實際使用的容量并非該值。而是使用“不小于該值的最小質(zhì)數(shù)來作為它使用的實際容量，最小是3?！保ɡ馅w），當(dāng)有了實際容量之后，并非直接實現(xiàn)索引，而是通過創(chuàng)建額外的2個數(shù)組來實現(xiàn)間接的索引，即int[] buckets和Entry[] entries兩個數(shù)組（即buckets中保存的其實是entries數(shù)組的下標(biāo)），這里就是第二條字典與哈希表的區(qū)別，還記得哈希沖突嗎？對，第二個區(qū)別就是處理哈希沖突的策略是不同的！字典會采用額外的數(shù)據(jù)結(jié)構(gòu)來處理哈希沖突，這就是剛才提到的數(shù)組之一buckets桶了，buckets的長度就是字典的真實長度，因為buckets就是字典每個位置的映射，然后buckets中的每個元素都是一個鏈表，用來存儲相同哈希的元素，然后再分配存儲空間。
因此，我們面臨的情況就是，即便我們新建了一個空的字典，那么伴隨而來的是2個長度為3的數(shù)組。所以當(dāng)處理的數(shù)據(jù)不多時，還是慎重使用字典為好，很多情況下使用數(shù)組也是可以接受的。
幾種常見數(shù)據(jù)結(jié)構(gòu)的使用情景
