定义：
n个数据元素的有序列
对于其中的数据元素，必须满足：
一、数据元素具有相同特性
二、相邻数据具有序偶关系：
1、有唯一的第一和最后元素
2、除第一元素外，每个元素有且只有唯一一个前序元素
3、除最后一个元素外，每个元素有且只有唯一一个后序元素
存储结构：
一、顺序存储结构：用一组地址连续的存储单元依次存储数据表的线性元素
1、顺序表的基本操作：
1）、初始化
2）、插入
3）、删除
代码实现：
private T[] _list; public void Init(int maxCapacity = 100) { if (maxCapacity <= 0) throw new ArgumentException("maxCapcity无效"); _maxCapcity = maxCapacity; _list = new T[maxCapacity]; } private int _length; public int Lenght { get { return _length; } } private int _maxCapacity; public int MaxCapacity { get { return _maxCapacity; } } public T this[int index] { get { if (index >= Lenght) throw new IndexOutOfRangeException("index"); return _list[index]; } set { if (index >= MaxCapacity) throw new IndexOutOfRangeException("index"); _list[index] = value; } } public void Insert(int location, T data) { if (_length >= MaxCapacity) throw new Exception("列表已满..."); if (location < 1 && location > MaxCapacity) throw new ArgumentOutOfRangeException("location"); var index = location - 1; // 将后面的元素往后移一位 for (int i = MaxCapacity - 1; i > index; i--) { _list[i] = _list[i - 1]; } _list[index] = data; _length++; } public void Delete(int location) { if (location < 1 && location > MaxCapacity) throw new ArgumentOutOfRangeException("location"); var index = location - 1; // 将后面的元素往前移一位 for (int i = index; i < Lenght - 1; i++) { _list[i] = _list[i + 1]; } _list[Lenght - 1] = default(T); _length--; } public string OutputList() { var sb = new StringBuilder(); for (int i = 0; i < MaxCapacity; i++) { sb.Append(string.Format("[{0}] ", _list[i])); } return sb.ToString(); }
二、链式存储结构：用一组任意的存储单元存储，存储单元不要求是连续的，物理结构反应不出逻辑结构；不可以随机读取，但是插入和删除方便。
这样需要两个域来存储这些元素，一个存储数据元素本身，另一个需要存储元素之间的关联。那么这两个域就组成了一个节点，一个线性链表的存储结构就是一组节点。
1、单链表
代码实现：
////// 单链表 /// ///public class SingleLinkedList { private class Node { public TData Data { get; set; } public Node NextNode { get; set; } } private Node _head; public void Init(int maxCapacity = 100) { if (maxCapacity <= 0) throw new ArgumentException("maxCapacity无效"); MaxCapacity = maxCapacity; _head = new Node (); } private Node GetNodeByLocation(int location) { var next = _head.NextNode; int i = 1; while (next != null && i <= Length) { if (i == location) { return next; } else { next = next.NextNode; } i++; } return null; } /// /// 在 /// /// public void Insert(int location, T data) { if (Length >= MaxCapacity) throw new Exception("队列已满"); if (location < 1 || (Length != 0 && location > Length)) throw new ArgumentException("位置无效"); if (location == 1) { _head.NextNode = new Node位置插入数据 /// { Data = data, NextNode = _head.NextNode }; } else { var index = location - 1; // 取此节点的前一个节点的索引 var node = GetNodeByLocation(index); node.NextNode = new Node { Data = data, NextNode = node.NextNode }; } Length++; } public void Delete(int location) { var preNode = GetNodeByLocation(location - 1); if (preNode != null && preNode.NextNode != null) { // 把当前节点的前节点和当前节点的后节点关联起来 preNode.NextNode = preNode.NextNode.NextNode; } Length--; } /// /// 通过位置取数据 /// /// ///public T GetElementByLocation(int location) { if (location < 1 || location > Length) throw new ArgumentException("location"); var node = GetNodeByLocation(location - 1); if (node != null) return node.Data; return default(T); } /// /// 包含 /// /// ///public bool Contains(T obj) { if (obj == null) throw new ArgumentNullException("obj"); var next = _head.NextNode; int location = 1; while (next != null && location <= Length) { if (next.Data != null && next.Data.Equals(obj)) return true; next = next.NextNode; location++; } return false; } /// /// 定位 /// /// /// ///public int LocationOf(T obj, int startLocation = 1) { if (obj == null) throw new ArgumentNullException("obj"); var next = _head.NextNode; int location = startLocation; while (next != null && location <= Length) { if (next.Data != null && next.Data.Equals(obj)) return location; next = next.NextNode; location++; } return -1; } public string OutputList() { var sb = new StringBuilder(); int index = 1; var next = _head.NextNode; while (next != null && index <= Length) { sb.Append(string.Format("[{0}] ",next.Data)); next = next.NextNode; index++; } return sb.ToString(); } public int Length { get; private set; } public int MaxCapacity { get; private set; }