数组

是一种线性表结构，用一组连续的内存空间，来存储一组具有相同类型的数据

线性表：数据排列的像是一条线一样的结构，每个线性表中的数据最多有前后两个方向 包括 数组，链表，队列，栈 非线性表： 数据之间并不是简单的前后关系，例如 二叉树，堆，图 Â 数组支持随机访问，根据下标随机访问的时间复杂度是O(1)

插入和删除

数组的插入和删除最好时间复杂度是O(1),最坏的时间复杂度是O(n)，平均情况的时间复杂度是(1+2+3…+n)/n =O(n) 看起来都很低效的，但是可以在特定场景下，可以优化的。

插入优化方案： 如果数组存储数据没有任何规律，只是被当做一个存储数据的集合，如果在第 K 位置插入一个数据，可以将 K 位置的数据移动到数组元素最后，把新的元素之间放入到第 K 个位置 例如 a b c d e 中将 x 插入到第三个位置，那么最后顺序就是 a b x d e c 这样在这种场景下，在第 K 位置插入一个元素的时间复杂度就会降低为O(1)

删除优化方案：在某些特殊场景下，不追求数组中数据连续性，可以将多次删除操作集中在一起执行，删除的效率会高很多， 例如 a b c d e f g h ,依次删除 a b c 三个元素，可以先记录要删除的元素，并不真正的搬移数据，当数组中没有更多空间存储数据时，再触发一次执行真正的删除操作，这样就大大减少删除操作导致的数据搬移了。 这就是 JVM 标记清除垃圾回收算法的核心思想。

警惕数组访问越界的问题

java 还好，会有java.lang.ArrayIndexOutOfBoundsException，但是 C 语言就是一种未决定行为，没有规定数组访问越界时候编译期如何处理。所以需要警惕。不然会出现一些莫名其妙的问题。

ArrayList

• 可以将很多数组操作的细节封装起来，比如前面提到的数组插入，删除数据时需要搬移其他数据等。
• 支持动态扩容，每次存储空间不够的时候，空间就会自动扩容为1.5倍大小
• 因为扩容操作设计内存申请和数据搬移，比较耗时，如果事先确定需要要存储数据大小，最好在创建 ArrayListd 的时候事先指定数据大小
• 无法存储基本类型，比如 int long ，需要 Autoboxing , Unboxing ，而有一定的性能消耗，如果特别关注性能，或者希望使用基本数据类型，可以选数组
• 如果数据大小事先知道，并且对数据操作简单，也可以使用数组
• 当表示多维数组时，数组更加直观。

总结： 对于业务：容器足够，省时省力，毕竟损耗一丢丢性能，完全不会影响系统整体性能 对于底层开发，网络架构，性能优化需要做到极致的，数组会优于容器，成为首选

链表 Linked list

不需要一块连续内存空间，通过指针将一组零散的内存卡串联起来使用，这个内存块叫结点，每个链表结点包括 存储的数据+后继指针 next ,也就是记录下一个结点的地址，

常见的链表结构：

单链表

第一个结点叫头结点，用来记录链表的基地址，有了它，我们就可以变量整条链表 最后一个结点叫尾结点，指针指向一个空地址 NULL ，表示这是链表最后一个结点
插入，删除操作，速度非常快，时间复杂度是O(1)
查找，只能根据指针一个结点一个结点依次遍历，时间复杂度是O(n)

循环链表

特殊的单链表，唯一区别就是尾结点，这个尾结点指向头结点，想一个环一样首尾相连， 优点就是从链尾到链头比较方便，当处理的数据具有唤醒结构特点的时候，特别适合采用循环链表。代码简洁很多

双向链表

每个结点不止有一个后继指针 next 指向后面结点，还有一个前驱指针 prev 指向前面结点 比单链表占用更多内存空间，但是支持双向遍历， 支持O(1)时间复杂度的情况下查找前驱结点

• 删除结点中 值等于给定值的节点，
  单链表和双向链表，尽管删除操作时间复杂度都是O(1),但是因为得先查找出来，查找操作的时间复杂度是O(n) ,根据加法法则，删除 值等于给定的值的节点对应的链表操作的总时间复杂度为O(n)
• 删除给定指针指向的节点 因为得知道前驱节点，所以单链表要遍历得到前驱节点，故时间复杂度还是O(n) 而双向链表，可以直接得到前驱节点，所以时间复杂度就是O(1) 同理，在某个至东京节点前插入一个节点，双向链表也比单向链表有优势， 对于有序链表，双向链表的安值查询效率也比单链表要高一些，可以记录上次查找的位置 P ，每次查询时候，根据要查找值与 P 的位置，决定是往前还是往后查找。所以平均只需要查找一版的数据 LinkedHashMap 内部使用的就是双向链表结构 也是用空间换时间的设计思想。 缓存就是利用了空间换时间的设计思想。

常见的缓存策略

• 先进先出策略 FIFO(Frist In,Frist Out)
• 最少使用策略 LFU(Least Frequently Used)
• 最近最少使用策略 LRU (Least Recentyl Used)

LRU 算法思路

1. 如果此数据之前已经存在链表中，遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表头部
2. 如果此数据没有在缓存链表中，可以分两种情况
   • 此时缓存未满，将此结点直接插入链表的头部
   • 此时缓存已满，则链表尾结点删除，将新的数据插入链表的头部

访问缓存的时间复杂度是O(n) 优化方案：

1. 使用散列表（Hash table ） 记录每个数据的位置，这样就将访问缓存的时间复杂度将到O(1)
2. 使用数组实现 LRU 缓存淘汰策略

使用数组，思路也是一样的，

1. 如果数据之前已经存在数组中，遍历得到这个数据对应的index (时间复杂度是O(n)) ，然后删除该数据(时间复杂度是O(1))，并把 index 之前的数据后移一位(时间复杂度是O(n))，然后把该数组插入到数组头部(时间复杂度是O(1)) ，所以根据加法法则，时间复杂度是 O(n)
2. 如果此数据没有在数组中，分两种情况
   • 如果此时数组已满，则删除数组最后一位对应的数据(时间复杂度是O(1))，然后把剩下的数据都后移一位(时间复杂度是O(n))，把该数据插入到数组头部(时间复杂度是O(1)),所以根据加法法则，时间复杂度是 O(n)
   • 如果此时数组未满，则把所有数据都后移一位(时间复杂度是O(n))，然后把该数据插入到数组头部(时间复杂度是O(1))。所以根据加法法则，时间复杂度是 O(n)

思考题

回文字符串判断

• 字符串是用数组存储

      String []array =new String[]{"f","d","s","a","s","d","f"};
       int length=array.length;
       for (int i = 0; i < length / 2; i++) {
           if(!array[i].equals(array[length-1-i])){
               return false;
           }
       }
       return true;
  

  时间复杂度是O(n)

• 字符串是链表存储