# 4.如何完成线性表结构下的增删查

通过之前的学习，我们了解了，数据在代码中处理和加工的最小单位动作是增、删、查

数据结构就是数据的组织方式，在数据结构适用的场合中，需要一定量的数据
但计算机要处理大量数据时，同样需要考虑如何去组织这些数据，这就是数据结构(如小朋友站队方式：横排，列，圈)

线性表是n个数据元素的有限序列，最常用的是链式表达，通常也叫做线性链表或者链表
在链表中存储的数据元素也叫做结点，一个结点存储的就是一条数据记录，每个结点的结构包括两个部分

在链表的最前面，通常会有一个头指针来指向第一个结点
对于链表的最后一个结点，由于在它之后没有下一个结点，因此它是空指针
链表结构，和小朋友手拉手站成一排的场景很相似

上图可以看出，链表只能通过上一个结点的指针找到下一个结点，反过来行不通，这种就是单向链表

有时候我们为了弥补这种不足，可以对结点的结构进行改造：

这些种类的链表，都是单向链表为基础进行的变种。在某些场景下能提高线性表的效率

例子：有一个链表，存储了10个同学的考试成绩，现在有一个同学被忘记存储了，要怎么进行？
做法：只需要把待插入的结点的指针指向原指针的目标，把原来的指针指向插入的结点

代码如下：

 s.next = p.next;
 p.next = s

删除操作：链表的删除和新增一样，如果待删除的结点为b，只需要把b的指针(p.next),指向b的指针指向的结点（p.next.next）

代码如下：

 p.next = p.next.next;

这种和数组中的index非常类似，查出学号为5的同学，考试成绩是多少？
链表的查找功能很弱，所以只能一个一个遍历查找

查找出是否有同学成绩为95？
链表的价值在于用指针按照顺序连接了数据结点，但对每个结点的数值没有做任何整合，所以只能按照先后顺序遍历
所以解决办法：

  1、如果是，则返回有人得分为95
  2、如果不是，则需要通过指针去判断下一个结点的值是否为95，以此类推，直到所有结点被访问完

虽然链表在新增删除数据上有优势，但仔细就发现，这个优势不实用
主要是因为，在新增数据时，通常会伴随查找动作；例如：在第五个结点之后新增一个数据结点，就需要执行两个步骤：

 第一步：查找第五个结点
 第二步：新增结点，所以整体的复杂度为O(n) + O(1) = O(n)

如果数据元素个数不确定，删除插入的操作并不多，那么数组可能更适合

给定一个链表，输出翻转后的链表，例如输入1->2->3->4->5,输出5->4->3->2->1

如果是数组翻转，会比较容易；数组在连续空间进行存储，可以直接求解出数组的长度；而且数组可以通过索引值去查找元素，然后对相应的数据进行交换操作而完成翻转
但对于单个单向链表，它的指针是有去无回的，一旦修改了某元素的指针，后面的元素就会造成失联状态，为解决这个问题，需要构造三个指针prev,curr,next,对当前结点、以及它之前和之后的结点进行缓存，再完成翻转，具体代码如下

 while(curr){
   next = curr.next;
   curr.next = prev;
   prev = curr;
   curr = next
 }

这个例子，也是利用了链表的长度无法或缺的不足做的文章，解决办法如下：

 while(fast && fast.next && fast.next.next){
   fast = fast.next.next;
   slow = fast.next;
 }

链表的快慢指针的方法，在很多链表操作的场景下都非常适用
假如链表有环，这个环就像一个跑步赛道，多次循环，快指针和慢指针都会进入到赛道中，相对而言，快指针每循环会多走一步
这就意味着