[TOC]
线性表：顺序表/链表/栈/队列
非线性表：二叉树/图
线性表和非线性表的划分，是根据其逻辑来划分的，而不是根据其存储结构来划分的。每个线性表上的数据最多只有前后两个方向。
最本质的区别：顺序表在内存是连续存储的，而链表在内存中是离散存储的。
其他所有的区别，都源于这个最本质的区别，由于顺序表是连续存储的，所以可以根据索引快速的进行查找，但是如果想要插入和删除，为了保持顺序表的连续性，部分元素就需要移位，而这正是链表所擅长的，链表的离散存储特性决定了其无法快速的查找，但是可以快速的进行插入/删除操作。
链表由于其需要另外开辟空间存储下一个节点的指针，所以其比顺序表要耗费更多的内存。并且由于链表的空间是离散分配的，在内存回收后，会产生更多的内存碎片，不方便利用。
线性表的使用场景更多一些，其相较于链表，更节省内存，而且可以借助 CPU 的缓存机制，加速线性表的访问速度。但是其缺点也很明显，其需要占用连续的存储空间，一旦申请的空间很大，就会导致申请失败；另外，如果申请的空间不够用，那么就得向操作系统申请一个更大的连续空间，然后将顺序表中的内容 copy 过去，而 copy 的操作是非常耗时的。
- 解法一：将链表的数据 copy 到数组中解决
- 解法二：头插法(逆序)新建一个链表，然后等值匹配
两者的时间复杂度相同，都是 O(n)，但是空间复杂度，差距特别大，采用新建链表的方式，其耗费了 12.6M 的内存，比解法一多用 1MB 的内存，这说明，链表的指针，是比较耗费内存的，同样的需求，还是优先考虑用顺序表实现。
该题的最佳空间复杂度是 O(1)，以上的两个解法，实际上是在拿空间复杂度换取时间复杂度。