本节，我们先学习链表的基础知识，再看一个链表的经典应用场景。而且，本节只涉及链表的基础知识和实现，链表相关的高级讲解和面试题目等，请关注公众号 攻城狮客栈 查看，可通过关键字 链表 来获取。
首先，我们来说一下链表和数组的区别，上节我们知道，数组和链表都是线性表，且数组是用连续的内存空间来存储数据的，但链表，在内存上并不是连续的，这既是数组和链表的最大区别。
链表分为单链表、双链表、循环链表、循环双向链表等多种类型。下面我们依次来看一下。
单链表
链表节点，除了存储数据外，还有一个存储下一节点地址的指针，链表的第一个节点称为头结点，记录的是链表的基地址，最后一个节点称为尾节点，指向null.
单链表支持O(1)的时间复杂度内完成链表的插入和删除操作。因为在插入和删除时，只需要确定要删除节点与要插入节点的位置，只操作相邻的节点即可完成。
虽然单链表单独执行插入和删除的时间复杂度是O(1)，但是在这之前，我们需要知道插入或删除位置的前一个节点，查找这个节点的过程时间复杂度是O(n)而非O(1)，因此要强调的是，单链表支持在O(1)的时间复杂度内完成删除和插入操作，并非整个过程。
双向链表
双向链表和单向链表的区别是，除了存储了指向下一个节点的指针外，还存储了指向上一个节点的指针，也就是说，双向链表支持在O(1)的时间复杂度内找到节点的上一个节点。这是单链表不支持的。这也是为什么双向链表虽然占用更多的空间，却在实际开发中更常用的原因。
双向链表适合的场景：
- 双向链表某些情况下，插入、删除要比单链表高效，因为，单链表删除结点时，需要先通过遍历获得结点的前驱结点。
- 对于一个有序链表，双向链表的按值查询效率比单链表高。因为，可以记录上次查找的位置p，每次查询时，根据要查找的值与p的关系，决定是向前还是向后查找，平均只需查找一半数据
循环链表
循环链表的尾节点不是指向null，而是指向链表的头结点。首尾相连，即为循环链表。循环链表的优点是从链表尾到链表头方便，当要处理的问题具有环形结构时，可以考虑用循环链表来处理，比如经典的约瑟夫问题。
双向循环链表
双向循环链表则兼具双向链表和循环链表的优点，如图所示。
和数组相比，链表更适合用于插入、删除操作频繁的场景，查找的时间复杂度较高。
好了到这里，基础知识就讲完了，我们下面来模拟实现以下链表的一些基础操作。
这里，我们用单链表来模拟链表的实现。
那么首先，我们先给出节点定义和链表的构造函数
/// <summary> /// 单链表节点 /// </summary> public class SNode<T>where T:IComparable<T> { public T Value { get; set; } public SNode<T> Next { get; set; } public SNode(T val) { Value = val; } } public class SLinkedList<T>where T:IComparable<T> { public int Length { get; set; } public SLinkedList(params T[] tlist) { var Head = new SNode<T>(default(T)); if (tlist == null) return; var p = Head; int count = 0; foreach (var item in tlist) { SNode<T> node = new SNode<T>(item); p.Next = node; p = node; count++; if (count==tlist.Count()) { node.Next = null; } } Length = tlist.Length; } }
我们这里实现在特定位置插入值、删除特定值节点以及打印链表全部值三个方法，其他方法就不一一实现了，若有需要，可以关注公众号，获取完整代码。
首先，我们先来看，如何打印链表的全部节点值，我们知道，链表是一个线性表结构，只要我们知道链表的头节点，那么我们就可以同个next指针逐个遍历，直接遍历完全部节点。现在我们来实现一下:
/// <summary> /// 打印全部节点 /// </summary> /// <param name="list">链表头节点</param> public void PrintAll(SNode<T> list) { while (list!=null) { Console.WriteLine(list.Value); list = list.Next; } }
是不是觉得很简单，没错，链表的操作就是这么简洁，但是，一定要注意指针的位置，在复杂的链表操作中，很容易将指针指来指去，将指针丢失，要杜绝这种情况，就需要深刻理解指针的含义并多写多练。
下面，直接给出单链表的删除和插入的代码，因为前面已经分析过其过程，因此这里就不再赘述了
public int Insert(int index, T val) { if (index<0||index>Length) { return -1; } var p = Head; int count = 0; while (p!=null&&count<index) { p = p.Next; count++; } SNode<T> node = new SNode<T>(val); node.Next = p.Next; p.Next = node; Length++; return 0; } //返回值-1：删除失败；0：删除成功。 public int Delete(T val) { var p = Head; while (p!=null) { if (p.Next.Value.Equals(val)) { p.Next = p.Next.Next; Length--; return 0; } else { p = p.Next; } } return -1; }
链表的基础操作，到此就结束了。关于链表的更多内容，可以通过公众号 攻城狮客栈获取。欢迎提问或提建议，另外，公众号寻找合作伙伴，有意向的同学可以联系我咯，多谢。(๑•ᴗ•๑)
