线性表链式存储结构定义：
链表是用一组任意的存储单元来存储线性表中的数据元素（这组存储单元可以是连续的，也可以是不连续的）。
关于链表大概还有几个定义要了解一下：
在存储数据元素时，除了存储数据元素本身的信息外，还要存储与它后继结点的数据元素的存储地址信息。这两部分信息组成该数据元素的存储映像，称为结点。
把存储据元素本身信息的域叫结点的数据域。
把存储与它相邻的数据元素的存储地址信息的域叫结点的引用域。
链表中第一个节点的存储位置叫做头指针，头指针是必须的。
单向链表中第一个节点前附设一个节点，称为头结点，头节点不是必须的。
观察上图我们可以清楚的发现，链表中的第一个节点，只有指针，没有数据，最后一个节点只有数据，没有指针。
链表大概有两种形式：单向链表及双向链表
一：单向链表：
结点的引用域只存储该结点直接后继结点的存储地址，则该链表叫单链表
首先，我们来定义一个节点类：
/// <summary> /// 单向链表结点类 /// </summary> /// <typeparam name="T">数据类型</typeparam> public class Node<T> { /// <summary> /// 链表中的数据域 /// </summary> public T data; /// <summary> /// 链表中的下一个节点的指针域 /// </summary> public Node<T> Next; // 每个结点有两部分组成，指针+数据，第一个节点没有数据，只有指针，最后一个节点只有数据，没有指针。 // 那么构造函数需要有三次重载。 /// <summary> /// 中间节点构造函数 /// </summary> /// <param name="val"></param> /// <param name="index"></param> public Node(T val, Node<T> index) { this.data = val; this.Next = index; } /// <summary> /// 最后一个节点构造函数 /// </summary> /// <param name="val"></param> public Node(T val) { this.data = val; this.Next = null; } /// <summary> /// 第一个节点构造函数 /// </summary> /// <param name="val"></param> /// <param name="index"></param> public Node(Node<T> index) { // 默认值 this.data = default(T); this.Next = index; } /// <summary> /// 定义一个空节点 /// </summary> /// <param name="val"></param> /// <param name="index"></param> public Node() { this.data = default(T); this.Next = null; } }
这其中大概有四个重载，每个节点具体的意义在函数的备注中都有写。
接下来，定义一个链表操作泛型接口
/// <summary> /// 链表操作泛型接口 /// </summary> /// <typeparam name="T"></typeparam> interface Ilinklist<T> { /// <summary> /// 清空链表 /// </summary> bool MakeEmpty(); /// <summary> /// 返回链表的长度 /// </summary> /// <returns></returns> int GetTableLength(); /// <summary> /// 在链表中查询数据item,找到则返回相应链表结点的位置，否则返回-1 /// </summary> /// <param name="item"></param> /// <returns></returns> int FindData(T item); /// <summary> /// 在位置n的结点前插入一个新结点，新结点的data值为item /// </summary> /// <param name="item"></param> /// <param name="n"></param> /// <returns></returns> bool Insert(T item, int n); /// <summary> /// 查询链表的第n个链表结点，返回链表结点的数据 /// </summary> /// <param name="pos"></param> /// <returns></returns> T GetIndexData(int pos); /// <summary> /// 删除第n个链表结点 /// </summary> /// <param name="n"></param> /// <returns></returns> T Remove(int n); /// <summary> /// 对链表的内容进行翻转 /// </summary> bool Rollback(Node<T> node1,Node<T> node2); /// <summary> /// 输出链表的内容 /// </summary> void Print(); /// <summary> /// 是否为空 /// </summary> bool IsEmpty(); /// <summary> /// 在链表末尾插入数据 /// </summary> /// <returns></returns> bool AppendData(T val); }
对于链表，我们大概要实现以上的操作。
在具体实现之前，我们先来简单的看一下链表的添加和删除大概是一个什么样子的情况。
如下图所示：
链表在元素插入/删除时，无需对后面的元素进行移动，只需要修改自身以及相邻节点的next指向即可，所以插入/删除元素的开销要比顺序表小得多。但是也应该注意到，其它操作比如：查找元素，反转倒置链表等，有可能需要遍历整个链表中的所有元素。
接下来，我们来实现上边接口定义的操作：
/// <summary> /// 单向链表类 /// </summary> public class linklist<T> : Ilinklist<T> { /// <summary> /// 头指针（只有指针，没有数据） /// </summary> public Node<T> head = null; /// <summary> /// 是否为空（查看头指针是否为空，为空，则链表为空） /// </summary> /// <returns></returns> public bool IsEmpty() { if (head == null) { return true; } else { return false; } } /// <summary> /// 在链表末尾插入数据 /// </summary> /// <returns></returns> public bool AppendData(T val) { // 两种可能性，一：正常在尾部添加。二：链表为空，添加的值等于引用头 Node<T> node = new Node<T>(val); // 判断链表是否为空(就是将引用头赋值) if (IsEmpty()) { head = node; return true; } else { // 实例化一个空点,让其等于引用头 Node<T> nodeTemp = new Node<T>(); nodeTemp = head; // 定义一个死循环，查找当前链表中的最后一个节点 while (true) { // 如果当前节点的下一个指针为空，说明当前节点是当前链表的最后一个节点 if (nodeTemp.Next != null) { nodeTemp = nodeTemp.Next; } else { break; } } // 经过上边循环判断，一定会找到当前单向链表中最后一个点（只有数据，没有下一个节点的指针） // 所以 nodeTemp就是当前链表的最后一个节点 nodeTemp.Next = node; return true; } } /// <summary> /// 在位置n的结点前插入一个新结点，新结点的data值为item /// </summary> /// <param name="item"></param> /// <param name="n"></param> /// <returns></returns> public bool Insert(T item, int n) { // 返回结果 bool result = false; // 首先判断链表是否为空，及插入位置是否小于1，只能在中间写入。 if (IsEmpty() || n < 1 ) { Console.WriteLine("链表为空或未知错误"); } // 当写入位置 大于等于当前链表长度时，调用末尾插入数据方法 if (n >= GetTableLength()) { result = AppendData(item); return result; } // 定义一个新节点 Node<T> temp = new Node<T>(item); // 写入位置为1时，直接就在引用头后写入。 if (n == 1) { // 新节点的下一位指针等于头结点的下一个指针 temp.Next = head.Next; // 头结点的下一个指针等于新定义的节点 head.Next = temp; return true; } // 当写入位置为其他位置时，需要循环找到要写入的前一个节点 int j = 1; Node<T> headTemp = head; Node<T> kong = new Node<T>(); while (headTemp.Next != null && j < n) { // 将当前节点赋值给空节点 kong = headTemp; // 当前节点等于下一个节点（为了下一次循环） headTemp = headTemp.Next; ++j; } if (j == n) { // 添加节点只影响其之前及之后的数据。 // 首先将当前节点之后的节点存储起来 Node<T> mes = kong.Next; // 将当前节点之后的节点改为添加的节点 kong.Next = temp; // 将添加的节点之后的节点改为刚刚存储的节点 temp.Next = mes; } return true; } /// <summary> /// 清空单向链表 /// </summary> public bool MakeEmpty() { head = null; return true; } /// <summary> /// 获取链表长度 /// </summary> /// <returns></returns> public int GetTableLength() { Node<T> nodeTemp = new Node<T>(); nodeTemp = head; int linklistNum = 0; while (true) { linklistNum++; nodeTemp = nodeTemp.Next; if (nodeTemp.Next == null) { linklistNum++; break; } } return linklistNum; } /// <summary> /// 在链表中查询数据item,找到则返回相应链表结点的位置，否则返回-1 /// </summary> /// <param name="item"></param> /// <returns></returns> public int FindData(T item) { if (IsEmpty()) { Console.WriteLine("链表为空"); return -1; } // 计数 int j = 1; // 实例化一个空节点 Node<T> temp = new Node<T>(); temp = head; while (!temp.data.Equals(item)) { temp = temp.Next; j++; if(j > GetTableLength()) { Console.WriteLine("您查找的值不存在，请稍后再试"); return -1; } } return j; } /// <summary> /// 查询链表的第n个链表结点，返回链表结点的数据 /// </summary> /// <param name="pos"></param> /// <returns></returns> public T GetIndexData(int pos) { // 判断长度是否超限 if (pos > GetTableLength()) { Console.WriteLine("您输入的值超出了链表长度"); return default(T); } int j = 1; // 定义一个临时节点，初始值为引用头 Node<T> tempHead = head; // 定义一个空节点，用来存储结果 T result = default(T); // 循环（） while (true) { if (j == pos) { result = tempHead.data; break; } else { tempHead = tempHead.Next; j++; } } return result; } /// <summary> /// 删除第n个链表结点 /// </summary> /// <param name="n"></param> /// <returns></returns> public T Remove(int n) { if (IsEmpty() || n < 1 || n > GetTableLength()) { Console.WriteLine("链表为空或您删除的节点存在"); } // 定义一个空节点来参数被删除的节点 Node<T> temp = head; // 删除头结点 if (n == 1) { head = head.Next; return temp.data; } // 如果删除的不是头结点，其余循环删除 int j = 1; // 定义一个空节点，存储当前节点 Node<T> tab = new Node<T>(); while (j < n) { tab = temp; temp = temp.Next; j++; } // temp 是要删除的节点，tab的下一个节点等于temp的下一个节点 tab.Next = temp.Next; return temp.data; } /// <summary> /// 对链表的内容进行翻转（返回值为引用头） /// </summary> public bool Rollback(Node<T> node1, Node<T> node2) { // 判断是否是头结点 bool isHead = false; if (node1 == head) { isHead = true; } // 定义一个临时节点存储要翻转的第二个参数的下一个节点 Node<T> temp = node2.Next; //使Node2节点指向Node1节点 node2.Next = node1; // 头节点反转后就是尾节点，它的Next为空 if (isHead) { node1.Next = null; } // 如果其下一个节点为空，则说明，翻转完毕，否则，递归 if (temp == null) { head = node2; return true; } else { return Rollback(node2, temp); } } /// <summary> /// 循环输出（打印）链表的内容 /// </summary> public void Print() { if (IsEmpty()) { Console.WriteLine("链表为空，无法打印"); return; } Node<T> nodeTemp = new Node<T>(); nodeTemp = head; while (true) { Console.WriteLine("data:" + nodeTemp.data + " | " + "Next:" + nodeTemp.Next); nodeTemp = nodeTemp.Next; if (nodeTemp.Next == null) { Console.WriteLine("data:" + nodeTemp.data + " | " + "Next:" + nodeTemp.Next); break; } } } }
以上是单向链表的类。
调用方式如下：
// 实例化一个链表List linklist<string> linkTable = new linklist<string>(); // 查看链表是否为空 bool IsEmptyRes = linkTable.IsEmpty(); Console.WriteLine("链表为空："+ IsEmptyRes); Console.WriteLine("======================================================================"); // 从末尾添加数据 bool AppendDataRes = linkTable.AppendData("11111"); linkTable.AppendData("22222"); linkTable.AppendData("33333"); linkTable.AppendData("44444"); linkTable.AppendData("55555"); Console.WriteLine("从末尾添加数据：" + AppendDataRes); Console.WriteLine("======================================================================"); // 打印链表数据 linkTable.Print(); Console.WriteLine("======================================================================"); // 获取链表元素个数 int linkListNum = linkTable.GetTableLength(); Console.WriteLine("链表元素个数：" + linkListNum); Console.WriteLine("======================================================================"); // 在链表中插入数据 bool res = linkTable.Insert("99999",3); Console.WriteLine("在链表中插入数据：" + res); Console.WriteLine("======================================================================"); // 打印链表数据 linkTable.Print(); Console.WriteLine("======================================================================"); // 访问链表第四个数据 string resultStr = linkTable.GetIndexData(4); Console.WriteLine("链表第四个数据为：" + resultStr); Console.WriteLine("======================================================================"); // 递归翻转链表 bool Rollback = linkTable.Rollback(linkTable.head, linkTable.head.Next); Console.WriteLine("递归翻转链表：" + Rollback); Console.WriteLine("======================================================================"); // 打印链表数据 linkTable.Print(); Console.WriteLine("======================================================================"); // 删除节点 string nodeData = linkTable.Remove(3); Console.WriteLine("删除节点：" + nodeData); Console.WriteLine("======================================================================"); // 打印链表数据 linkTable.Print(); Console.WriteLine("======================================================================"); // 根据数据获取指针 int index = linkTable.FindData("99999"); Console.WriteLine("根据数据获取指针：" + index); Console.WriteLine("======================================================================"); // 清空链表 linkTable.MakeEmpty(); Console.WriteLine("======================================================================"); // 打印链表数据 linkTable.Print(); Console.WriteLine("======================================================================");
二：双向链表：
双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。
大概图示基本上就是这样
具体代码不在这里展示包含在文末实例中。
三：循环链表
将单链表中终端结点的指针端有空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。
循环链表的基本操作与单链表大体相同，只是判断链表结束的条件并不是判断结点的引用域是否为空，而是判断结点的引用域是否为头引用，其它没有较大的变化。
四：静态链表
静态链表一般用于没有指针的早期的高级语言。一般情况下用不上，但是其设计思想很巧妙。用数组描述的链表叫做静态链表。
静态链表的设计思想：
（1）：我们对数组的第一个元素及最后一个元素进行处理。
（2）：第一个元素存储备用链下标，就是存储数组中第一个没有数据的元素下标。
（3）：最后一个元素存储数据链下标，就是存储数组中第一个有数据的元素的下标，相当于链表中的头结点。
这里不展示静态链表的源码，在文末实例中，可下载。
数组节点的定义：
/// <summary> /// 静态链表节点类 /// </summary> public class StaticNode<T> { /// <summary> /// 静态链表节点中的 游标 /// </summary> public int Next; /// <summary> /// 静态链表节点中的数据 /// </summary> public T data; }
1：静态链表中的添加：
静态链表中要解决的是：如何用静态模拟动态链表结构的存储空间的分配，需要的时候申请，不需要的时候释放。
为了明确数组中那些变量未被使用，解决的办法是将所有未被使用过的及已被删除的分量用游标连城一个备用的链表，每当进行插入式，边可以从备用链表上取得第一个节点作为待插入的新节点。
/// <summary> /// 在链表中插入数据 /// </summary> /// <param name="item">添加的数据</param> /// <param name="n">链表游标</param> /// <returns></returns> public bool Insert(T item, int n) { if (IsFull()) { Console.WriteLine("链表已满，无法添加！"); return false; } if(IsEmpty()) { // 尾部添加 AppendData(item); } // 添加节点 staticArray[staticArray[0].Next].data = item; for (int i = 1; i < maxSize - 1; i++) { if (staticArray[i].Next == n + 1 && staticArray[i].data != null) { staticArray[i].Next = staticArray[0].Next + 1; } } staticArray[staticArray[0].Next].Next = n + 1; int bakNext = GetBakNext(); staticArray[0].Next = bakNext; listLength++; return true; }
2：静态链表中的删除：
正常删除是与链表中大致相同，别忘了，静态链表中还需要内存回收。
将第一个元素Next值赋给要删除的元素Next。
把要删除的分量下标赋值给第一个元素的Next
/// <summary> /// 删除元素 /// </summary> /// <param name="n">元素个数</param> /// <returns></returns> public T Remove(int n) { // 首先判断要删除的元素是否在链表中 if (n >= staticArray[0].Next) { Console.WriteLine("数据不存在，无法删除！"); return default(T); } // 锁定要删除的元素的Next（数组中Next的排序是连续的，因此要删除的元素位置 n 的Next = n + 1） int k = staticArray[maxSize - 1].Next; for (int i = 1; i < n - 1; i++) { k = staticArray[k].Next; } //k=1 //假如我要删除第2个 //temp=2 int tmep = staticArray[k].Next;//得到第2个的下一个 staticArray[k].Next = staticArray[tmep].Next; T result = staticArray[tmep].data; staticArray[tmep].Next = staticArray[0].Next; staticArray[tmep].data = default(T); staticArray[0].Next = tmep; listLength--; return result; }
最后了解下静态链表的优缺点：
优点： 在插入和删除操作是，只需要更改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点。
缺点：没有解决连续存储分配带来的表长难以确定的问题，失去了顺序存储结构随机存储的特性。
以上大概就是线性表链式存储结构的基本内容。
