引言：資料結構的基本概念
我們先來回顧下資料結構的幾個概念。
何謂資料結構？專門研究資料之間的邏輯關系、存儲方式及操作的學問就是所謂的資料結構。
資料的邏輯結構
資料元素之間存在的關聯關系(與它們在計算機中的存儲位置無關)，被稱為資料的邏輯結構。
從資料的邏輯結構劃分大緻有如下4中邏輯結構：
集合：資料元素之間隻有"同屬于一個集合"的關系
線性結構：資料元素之間存在"一對一"的關系
樹形結構：資料元素之間存在"一對多"的關系
圖狀結構或網狀結構：
資料的存儲結構
對于資料不同的邏輯結構，在底層通常通常有兩種實體存儲結構（資料元素在計算機存儲空間的存放形式）：
順序存儲結構（線性表）
鍊式存儲結構（連結清單）
對上面的内容用思維導圖小結下：
線性表
對于常用的資料結構可以分為線性結構和非線性結構。線性結構主要是線性表，非線性結構主要是樹和圖。
從上面對資料結構的邏輯結構介紹中得知， 資料元素之間存在"一對一"的關系， 即除了第一個和最後一個資料元素之外，其它資料元素都是首尾相接的（注意循環l連結清單也是線性結構，但是它首尾是相接的）。
線性表的每個元素必須有相同的結構（元素可以是簡單的資料，也可以是複雜的資料，但複雜的資料内部結構要相同）。
線性表的基本操作
線性表初始化
插入元素
向指定位置插入元素
删除元素
删除指定位置的元素
取指定位置的元素
查找元素的位置
傳回線性表的長度
判斷線性表是否為空
清空線性表
線性表主要有兩種存儲結構：順序存儲（線性表）、鍊式存儲（連結清單）。本篇文章主要介紹順序存儲，鍊式存儲放在下一個篇文章。
順序結構存儲是指用一組位址連續的存儲單元一次存放線性表中的元素。也就是說，順序結構線性表中的資料元素的實體關系和邏輯關系是一緻的。是以如果線性表采用順序存儲，往線性表中間的某個位置插入或者删除元素需要對該位置及其之後的元素進行移動。
順序存儲結構的線性表中間位置插入新元素
首先要把該位置及其之後的元素往後移一位，為新元素騰出空間。
往索引 index=2 的位置插入元素：
删除順序存儲結構的線性表中間位置元素
删除順序存儲結構的線性表中間位置的元素，操作類似。
删除索引index=2的元素：
順序存儲的線性表，采用數組存儲，插入元素如果容量不夠，需要進行擴容。擴容主要是建立一個新的數組，然後把資料從老數組拷貝到新的數組中。
一：數組
數組主要有Array，ArrayList，List
Array
數組在C#中最早出現的。在記憶體中是連續存儲的，是以它的索引速度非常快，而且指派與修改元素也很簡單。
<span style="font-family:SimSun;font-size:18px;">//數組
string[] s=new string[2];
//指派
s[0]="a";
s[1]="b";
//修改
s[1]="a1";
</span> 優點：數組在記憶體中是連續存儲的、是以它的索引速度是非常快的、時間複雜度為O(1)、而且它的指派/修改/擷取元素也是非常簡單的。
缺點：1、定義數組的時候需要指定數組的長度（過長會造成記憶體浪費、過短會導緻程式異常System.IndexOutOfRangeException:“索引超出數組界限”）
2、插入和删除元素效率低、也比較麻煩。
在不清楚數組長度的時候、就很尴尬了。 是以C#提供了ArrayList了來處理這些問題…
ArrayList
使用大小會根據需要動态增加的數組。
//初始化
ArrayList list = new ArrayList();
//添加元素
list.Add(1);
list.Add("A");
list.Add(0.1);
//修改元素
list[2] = "B";
//指定索引插入元素
list.Insert(1, "ABC");
//移除元素
list.RemoveAt(1); 優點：1、ArrayList大小會根據需要動态增加的數組。
2、實作了IList接口、可以友善的對資料進行添加、插入和删除。
缺點：1、ArrayList會把插入的資料都當做object類型來存儲、在操作資料的時候可能會因為類型不比對而出現異常、它是非類型安全的對象。
2、由于存儲的是object類型、在使用的時候進行類型轉換、會造成裝箱拆箱、進而損耗性能。
裝箱：把值類型轉換成引用類型；
拆箱：把引用類型轉換成值類型。
//裝箱
int i = 1;
object obj = (object)i;
//拆箱
int j = (int)obj; 優點：由于泛型List是強類型、編譯器會驗證類型安全。這樣就避免了類型的不安全、以及資料強制轉換導緻裝箱拆箱損耗性能。
備注:哈希表(散列),就是數組的更新版通過hash運算快速查找到值，數組下标就是哈希值。（前512是int，後才是哈希）