【线性表】链表

本来要先讲数组的，介于之前已经总结过可变数组vector了，故不再开一个专题去介绍用法和原理。但是要提一嘴：

数组作为数据结构可以高效地存储和查询给定索引（下标）的数据，其时间复杂度均为O（1），因为这个性质，数组可以用来模拟其他很多数据结构，但是如果要将整个数组进行移位操作，例如在中间插入和删除数据，或者在没排序的情况下搜索指定元素，那么时间复杂度可达到O（n），效率很低的。

那么，我们就从链表开始学习数据结构吧！

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。但是我们这里先介绍静态链表（由数组模拟链表）以先了解链表的各项操作。简单来说：链表能知道每个元素之前/之后是谁，这样能恢复整个表的排列顺序。利用这种方式，来存储元素排列顺序的表，称为链表。

链表由三个重要部分组成，next指针，value，idx指针，head指针分别用来记录后续节点的下标，当前节点的值，标明使用节点的指针，头指针。

struct ListNode {
       int next;
       int val;
       ListNode(int _val=0,int _next=0) //初始化
       {next=_next;val=_val;}
};

ListNode Node[MAXSIZE];	
int idx;      //当前用的元素的指针
int head=-1; //初始化头指针