上一篇代码不复杂、复杂的是人心中已经学习了代码中的基本操作增删改查的知识，我们可以通过选择合适的数据结构来解决实际遇到的问题。那么从今天起，我们开始系统的学习数据结构相关的知识。
数据结构-线性表线性表是「最基本、最简单、也是最常用的」一种数据结构。线性表（linearlist）是数据结构的一种，它也成为线性链表或者链表。一个线性表是n个具有相同特性的数据元素的有限序列。每一个元素也叫作节点，一个节点存储一个数据，而每个节点包含两个部分：
具体的数据下一节点的指针首先需要一个头指针指向第一个数据表明链表的开头，然后第一个指向第二个...知道最后一个数据，「最后一个数据没有指针」，因为它后面没有东西了。这个小孩子手拉手的场景非常像，第一个孩子拉着第二个的三、第三个、第四个...直到最后一个。
假设你用链表这个数据结构保存全班同学的考试成绩，那么得到的数据结构是这样，如图
单向链表你可以在计算机任意地方任意存储块中存储某个同学的数据，它们之间就是「靠每个数据额外的指针数据串联起来成一条链」。所以你若是仔细思考就会发现，链表必须从上一个节点的指针才能获取到下一个节点的数据。所以这样的链表也被称作单向链表。如前面学生成绩链表所示。
双向链表既然有单向链表，那么也就有双向链表。单项链表只能从头走到尾，因为它只有一个指向下一个节点的指针。那么在这基础上再「加上一个指向上一个节点的指针」，这个链表就可以双向访问了。即可以从头访问到尾，也可以从尾往头访问。
循环链表单向链表只能一个方向访问，而且最后一个数据「没有指针」。那么我们如果把「最后一个数据的指针指向第一个数据」。那么整个链表就能循环起来，这就叫作循环链表。
这些改造都是以单向链表为基础，根据实际情况需要进行的改造。所以我们只要清楚单向链表的基本原理，这些其他的改造链表也就都懂了。
线性链表的基本操作我们还是来通过它基本的增删改查操作，来学习这个数据结构。
新增假设有10个同学的考试得分被存放在链表中。这时你漏掉了一个同学。他要怎样插到这个链表中呢？
其实链表的新增操作非常容易，就是「找到你要插入的位置」，获取它的指针，把它指向这个新增的数据节点，然后把这个新数据的指针，指向刚才获取到的指针指向。
s.next=p.nextp.next=s删除
假设有位同学是别班级的被误放进来了，那要怎么删除呢
其实非常简单。假设要删除的节点为b，前面为a，后面为c。那么删除操作就是，把a.next指向b.next(就是c)。
查找最后我们来看查找操作。正如前几篇所说，查找分为两种，一种是按照位置索引查找，另一种是按值来查找。
链表这个数据结构的查找功能是相对弱的，对于查找只能通过一个一个遍历去查找。假设你要找到学号为5的同学，你得先找到学号为1的，经过它的指针找到学号为2的，...直到你找到学号为5的，才能得到它的成绩。如图所示：
假设你要找到全班考试成绩有没有人超过95，怎么找呢？除了「从头到尾遍历，别无它法」。所以正常的流程就是先找第一个，看看他成绩是否超过95，如果是就返回真，即有人成绩超过95，否则就要一直判断下一个，直到所有节点都访问完
如果你仔细，你会发现虽然看起来新增和删除操作很简单，能够在O(1)的时间复杂度内完成。不用像数组那样，新增或删除一个，后面的数据全都受到影响。但是呢？在新增或删除操作时都会伴随着一个查找的动作。比如上面的新同学的成绩忘记插入，你必须通过查找，找到第5位同学的位置，然后才执行插入动作，删除也一样。所以这个优势也就被查找效率低所影响。
线性表真正的价值在于，「它不需要完整的存储连续的空间」，如果你的场景数据元素不一定，且需要「频繁地新增和删除操作」，那么你就选择线性表数据结构吧。如果元素确定，删除插入操作不多，那数组比较适合你。
实例关于线性表的问题都是围绕数据顺序来讨论。这里我们看一个例子，来更好理解线性表这个数据结构。
假设给你一个链表，要你输出翻转后的链表。输入1-2-3-4-5,输出5-4-3-2-1。
这题我们前面也做过，使用数组可以快速地实现翻转交换，因为它的长度是确定的而且数组可以通过索引O(1)的时间复杂度来查找元素。
那对于链表呢？该如何翻转呢？具体看图，我们需要三个临时指针来指向当前节点、及它的前后节点，然后通过遍历一次完成翻转的操作。
//伪代码while(curr){next=curr.next;curr.next=prev；prev=curr;curr=next;}
例子2，假设给你一个奇数个元素的链表，要你查找出这个链表的中间位置节点的值。一个暴力的方法就是先遍历一遍计算链表的长度，算出中间值，然后再遍历一次找到这个中间值的元素值。还有一个巧妙的方法，就是利用快慢指针进行处理。「快指针每次走两步，慢指针每次走一步」，那么当快指针走完时，慢指针的位置就是中间的位置。
例子3，给你一个链表，判断其中是否有环。
对于这个问题，我们同样用快慢指针可以解决。就像一个跑道一样，经过多次循环，快的一定会在某个时刻「超过」慢的。如果链表中有环，快慢指针都会进到环中，而且必定会在环内相遇。如果链表没有环，那么他们就都会走完全程并且不会相遇。
总而言之关于链表要掌握的就是这些内容。单向链表的基本操作掌握了，那些双向、循环、双向循环链表等变形的链表也就掌握了。线性表的增删查操作就是这样，增删时间复杂度为O(1),查找操作都需要遍历链表，时间复杂度为O(n)。它应用的场景就是当你需要频繁增删数据时，选择它！
另外关于快慢指针的思想，你也必须掌握。不知道你看到上面两题用快慢指针来解决问题时，是否眼前一亮，居然可以这样！其实我们人生活在世上也一样，需要快慢指针，来给你试错的机会，亦或是事半功倍的乐趣，这便是我体会到的编程的魅力。
预览时标签不可点收录于话题#个上一篇下一篇