线性表表示一种线性结构的数据结构，顾名思义就是数据排成像一条线一样的结构，每个线性表上的数据只有前和后两个方向。比如：数组、链表、栈和队列都是线性表，今天我们分别来看看这些线性数据结构。
数组是一种线性表数据结构，用一组连续的内存空间来存储一组具有相同类型的数据。
内存分布：
连续内存空间存储相同类型的数据，这个特性支持了数组的随机访问特性，相同类型的数据占用的空间是固定的假设为data_size，第n个元素的地址可以根据公式计算出来：
&a[n] = $a[0] + n * data_size
其中：
&a[n]：第n个元素的地址
a[0]：第0个元素的地址（数组的地址）
data_size：数组存储的元素的类型大小
所以访问数组里指定下标的任何一个元素，都可以直接访问对应的地址，不需要遍历数组，时间复杂度为O(1)。
插入/删除低效为了保证内存的连续性，插入或删除数据时如果不是在数组末尾操作，就需要做数据的搬移工作，数据搬移会使得数组插入和删除时候效率低下。
向数组里插入一个元素有三种情况：
1、向末尾插入一个元素，此时的时间复杂度为O(1)，对应最好时间复杂度。
2、向数组开头插入一个元素，需要将所有元素依次向后挪一个位置，然后将元素插入开头位置，此时时间复杂度为O(n)，对应最坏时间复杂度。
3、向数组中间位置插入一个元素，此时每个位置插入元素的概率都是一样的为1/n，平均复杂度为（1+2+3+…+n）/n = O(n)
如果数组元素是没有顺序的（或不需要保证元素顺序），向数组中间位置插入一个元素x，只需要将插入位置的元素放到数组的末尾，然后将x插入，这时候不需要搬移元素，时间复杂度仍为O(1)，如：
同样地，删除数据的时候，从开头删除，需要将后面n-1个元素往前搬移，对应的时间复杂度为O(n)；从末尾删除时间复杂度为O(1)；平均时间复杂度也是O(n)。
如果不需要保证数据的连续性，有两种方法：
1、可以将末尾的数据搬移到删除点插入，删除末尾那个元素
2、删除的时候做标记，并不正真删除，等数组空间不够的时候，再进行批量删除搬移操作
Java的ArrayList很多编程语言都针对数组进行了封装，比如Java的ArrayList，可以将数组的很多操作细节封装起来（插入删除的搬移数据或动态扩容），可以参考ArrayList的扩容数据搬移方法，ArrayList默认size是10，如果空间不够了会先按1.5倍扩容（如果还不够就可能会用到最大容量）。所以在使用的时候如果事先知道数组的大小，可以一次性申请，这样可以免去自动扩容的性能损耗。
什么时候选择使用编程语言帮我们封装的数组，什么时候直接使用数组呢？
1、Java ArrayList不支持基本数据类型，需要封装为Integer、Long类才能使用。Autoboxing、Unboxing有一定的性能消耗。如果比较关注性能可以直接使用数组
2、使用前已经能确认数据大小，并且操作比较简单可以使用数组
链表比起数组，链表不需要连续内存空间，它通过指针将一组分别独立的内存空间串起来形成一条“链条”。链表有很多种，如：单链表、双向链表、循环链表和双向循环链表。
链表内存分布：
如下图所示，链表的每一项我们称为结点（node），为了将所有结点连接起来形成链表，结点除了需要记录数据之外，还需要记录下一个结点的地址，记录下一个结点地址的指针我们叫做后继指针（next），第一个结点和最后一个结点比较特殊，第一个结点没有next指针指向它，称为头结点，最后一个结点next指针没有指向任何元素，称为尾结点。头结点用来记录链表的基地址，有了它就可以顺着链子往下搜索每一个元素，如果遇到next指向null表示到达了链表的末尾。