線性表
線性表是最簡單、最基本、最常用的數據結構。數據元素 1 對 1的關系，這種關系是位置關系。
特點
（1）第一個元素和最後一個元素前後是沒有數據元素，線性表中剩下的元素是近鄰的，前後都有元素。
（2）線性表中的元素是有限的（List），線性表中的數據類型一致。
（3）線性表表示方法 L={a1,a2,a3,a4…….an},L=(D,R)
（4）每一個元素都有前驅和後繼，第一個元素只有後繼，最後一個元素只有前驅。
實例
例如：1～100的整數是一個線性表
{“zhangsan”, “lisi”, “wangwu”}
……
A.順序表
所有的操作都是根據建立在線性結構的基礎之上進行的,線性表接口表示如下：
public interface IListDS<T>
{
int GetLength(); //求長度
void Clear();//清空線性表
bool IsEmpty();//判斷是否為空
void Append(T item);//追加元素
void Insert(T item,int i);//插入元素
T Delete(int i);//刪除元素
T GetElem(int i);//獲取元素
int Locate(T value);//查找元素
void Reverse();//倒置
}
操作
1.插入操作：
30在插入之前數據表沒有什麼變化，當30數據出入到第i個位置後，後面的數據需要向後移動，那麼插入的
數據越靠前，所需要移動的次數越多，如果i=0 那麼需要向後移動 n 個位置，如果插入到最後一個，那麼
順序表就不需要移動，如果插入的數據的位置i的概率為Pi，那麼需要移動的位置次數為n/2,在順序表中移動
其中一半的數據，那麼插入操作的時間復雜度為0(n)。
2.刪除操作：順序表刪除操作和插入操作一致，時間都是浪費在移動數據上，時間復雜度也為0（n）
3.讀取操作：直接讀取到順序表中的數值 比如 IListDS[i]元素,那麼時間復雜度為 0(1) 只需要取一次即可。
4.查找操作：查找需要找到數據位置i，然後判斷數值是否一致，這個類似於插入和刪除，時間復雜度：0（n）
5.倒置操作：倒置操作只需要把前後對比 把第i個元素和第n-i個元素交換即可，時間復雜度也為:0(n)
B.單鏈表
對比順序表，邏輯相同的數據在物理地址上也相同，在順序表上查找一個位置上的數據非常方便，這是順序表的
優勢所在，那麼問題來了，在順序表插入或者刪除一個數據時候往往需要移動剩下的數據，那麼這樣會影響效率
，接下來學習一下線性表的另外一個存儲結構----鏈式存儲（Linked Strorage）,這樣的線性表叫做（Linked
List），對單鏈表的操作也不需要移動其他數據元素，但也失去順序表可隨機存儲的優點。
從兩張圖我們可以看到單鏈表的結構和順序表的一個差異
單鏈表實現的方法：
pulic class LinkedList<T>:IListDS<T>
{
Pulic Node<T> Head;//屬性
pulic LinkedList();//構造器
pulic GetLength();//獲取長度
pulic Clear();//清空
pulic bool IsEmpty();//判斷是否為空
pulic void Append(T item);//追加
pulic void Insert(T item,int i);//i位置插入
pulic void Delete(T item);//刪除元素
pulic T GetElem(int i);//獲取單鏈表第i個元素
pulic int i Location(T item);//查找位置
pulic void Reserver();//倒置
}
操作
1.獲取長度
單鏈表和順序表的長度過去方法不一致，因為單鏈表是連續的順序空間，而單鏈表
從頭引用頭開始，一個節點一個節點的便利，直到表的末尾。那麼問題來了：剛剛介紹單鏈表物理空間不也是
連續的嗎？這個筆者個人理解，初始化數據是物理連續，而新插入的數據不會按照物理地址排列，所以所單鏈
表還是要便利整個內容來計算長度,時間復雜度為 0(n)。
2.清空操作
清空操作是指將單鏈表所有的節點使得單鏈表為空，此時頭引用head為null.清空單鏈表的算法實現如下：
pulic void Clear()
{
head=null;
}
需要注意的是，單鏈表清空後，原來節點所占用的空間不會一直保留，而由垃圾回收器進行回收和順序表不一樣
的是，順序表是連續的空間，數組分配的空間仍然保留。
3.附加操作
附加操作，是要便利單鏈表中所有的元素，然後在鏈表的尾部添加元素，時間復雜度為：0(n);
線性表的順序存儲和鏈式存儲各有優缺點，線性表如何存儲取決於使 用的場合。如果不需要經常在線性表中進行
插入和刪除，只是進行查找，那麼， 線性表應該順序存儲；如果線性表需要經常插入和刪除，而不經常進行查找
，則 線性表應該鏈式存儲。
C 結合單向鏈表，肯定也有有雙向鏈表，雙向鏈表也是有上面的基本操作，然後思考相關的問題：時間復雜度問題。
D 循環列表：循環鏈表是在單鏈表和雙向鏈表的基礎上頭尾相連Last.Next=>Header.Head
C#中的線性表
說道C# 線性表那就是List，在1.1中提供了非泛型接口 IList,接口中的項是object，非泛型IList是從ICollection
接口繼承而來,是所有線性表的接口，用了這麼長時間的List才發現IList是線性結構，IList分為三類：只讀的，大
小不可變，大小可變的。
只讀的IList：不能被修改，插入或者刪除。
大小不變的IList：不能在表中插入或刪除，但是可以修改表中的項。
大小可變的ILIST: 可以操作，可以插入或者刪除
非泛型的IList接口聲明如下：
interface IList:ICollenciton,IEnumberable
{
//共有屬性
bool IsFiexedSize{get;} //只讀，如果IList有固定大小
bool IsReadOnly{get;} //只讀 ，如果ILIST是只讀的
object this[T index] {get;set;} //索引器 得到某個類型
int add(object value);
void clear();
int indexof(object value);
bool contains(ojbject value);
void insert(index,object value);
void remove();
void removeat();
}
.NET 框架中一些集合實現了IList接口，如ArrayList，ListDictionary,StringCollection,String Dictionary.
.NET 線性表中順序存儲采用的是數組，而鏈式的存儲方式則是：IList接口。
未完待續…….
