线性表

线性表

线性表（Linear List）。顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。

数组

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。正是因为这两个限制，它才有了一个堪称“杀手锏”的特性：“随机访问“，但有利就有弊，这两个限制也让数组的很多操作变得非常低效，比如要想在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作，所以经常我们说数组的删除元素和插入元素的时间复杂度O(n),实际是数据搬迁工作为O(n)。

链表

链表是通过指针将一组零散的内存块串联在一起，我们把内存块称为链表的“结点”，我们把这个记录下个结点地址的指针叫作后继指针 next，由于链表的内存空间不连续，我们进行删除，插入节点的时候无需搬迁数据，只需改变相邻节点的指针指向，所以是O(1) 的时间复杂度

链表插入&删除.png

和单链表相比，还有循环链表 和双向链表

链表&数组大比拼

它们插入、删除、随机访问操作的时间复杂度正好相反

数组&链表.png

数组和链表的对比，并不能局限于时间复杂度，数组简单易用，在实现上内存空间是连续的，可以借助缓存机制实现高速读取，比如从一组姓名中找出"张三"，链表和数组时间复杂度都是O(n),由于数组是连续的内存空间往往更快。
数组还有一个缺点是大小固定，因为空间连续，所以初始化的时候需要指定空间，一旦空间不足就需要进行扩容，扩容实际上是开一个更大的数组将原数据进行搬迁，这是一个很耗时的工作。
除此之外，因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，会导致频繁的GC
说到数组和链表，就不得不提ArrayList 和LinkedList , 这两个集合类正是使用数组和链表实现，因为数组的缺点，所以我们在进行更多的删除和随机插入数据时使用LinkedList会更优，更多读和末尾添加数据使用ArrayList，由于数据连续空间特性，ArrayList申明前最好自定义大小，减少数据搬迁的可能性。

栈和队列

栈就是一摞叠在一起的盘子，从下往上一个一个放，取的时候，我们也是从上往下一个一个地依次取。栈是一种“操作受限”的线性表 ，既然操作受限似乎存在的意义不大，从功能上来说，数组或链表确实可以替代栈，但是数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。所以当我们的业务模型满足后进先出、先进后出的特性，首选当然是栈。举个栗子，验证一组括号是否合法，我们用栈来保存未匹配的左括号，当扫描到左括号入栈，扫描到右括号，出栈与之对比是否匹配，当所有扫描完成，栈为空，则是合法的括号格式。队列的使用场景在实际应用中则更常见，比如消息队列，ArrayBlockingQueue实现公平锁等等。

队列和栈.png