数据结构复习（一）

数组

数组是个线性表，它用一组连续的内存空间，来存储一组具有相同类型的数据。
寻址公式：

a[i]_address = base_address + i * data_type_size

数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。
数组是适合查找操作，用二分查找，时间复杂度也是 O(logn)。
数组的删除操作：可以先不进行删除，单标记数据，待内存空间不够，在进行删除。

Tips: JVM垃圾回收
JVM垃圾回收算法: 1.复制算法. 2.标记清除算法. 3.标记整理算法.
简单思想: 数组中删除数据时,并不真正的删除,而是标记一下,先不进行数据的搬移工作,等数组空间不够用时,我们再执行删除操作.进行数据的搬移工作,这样可以减少因为删除操作导致的数据搬移。
这种思想在JVM垃圾回收算法的 标记清除算法中 也有体现. 第一遍扫描先标记垃圾对象,第二遍扫描再清除垃圾对象.
这种垃圾回收算法 容易产生内存碎片,导致出现虽然内存空间充足,但是无法放置大对象的诡异现象.

ArrayList支持动态扩容，每次存储空间不够的时候，它都会将空间自动扩容为 1.5 倍大小，jdk8 arraylist默认10个初始化。
事先指定数据大小可以省掉很多次内存申请和数据搬移操作。

---

链表

数组需要一块连续的内存空间来存储，对内存的要求比较高。
链表不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用。
删除操作时间复杂度是 O(1)，但遍历查找的时间是主要的耗时点，对应的时间复杂度为 O(n)。

先进先出策略 FIFO（First In，First Out）
最少使用策略 LFU（Least Frequently Used）
最近最少使用策略 LRU（Least Recently Used）

基于链表实现 LRU 缓存淘汰算法，思路如下:

1. 越靠近链表尾部的结点是越早之前访问的
2. 当有一个新的数据被访问时，我们从链表头开始顺序遍历链表
3. 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部
4. 如果此数据没有在缓存链表中，缓存未满则将此结点直接插入到链表的头部、缓存已满则链表尾结点删除，将新的数据结点插入链表的头部
5. 引入散列表（Hash table）来记录每个数据的位置，将缓存访问的时间复杂度降到 O(1)

Java中LinkedList底层就是用双向链表实现的。
小知识点：CPU缓存存在的意义为了弥补内存访问速度过慢与CPU执行速度快之间的差异而引入。

---

栈

用数组实现的栈，叫作顺序栈，用链表实现的栈，叫作链式栈。
Java实现栈：

// 基于数组实现的顺序栈
public class ArrayStack {
  private String[] items;  // 数组
  private int count;       // 栈中元素个数
  private int n;           //栈的大小

  // 初始化数组，申请一个大小为n的数组空间
  public ArrayStack(int n) {
    this.items = new String[n];
    this.n = n;
    this.count = 0;
  }

  // 入栈操作
  public boolean push(String item) {
    // 数组空间不够了，直接返回false，入栈失败。
    if (count == n) return false;
    // 将item放到下标为count的位置，并且count加一
    items[count] = item;
    ++count;
    return true;
  }
  
  // 出栈操作
  public String pop() {
    // 栈为空，则直接返回null
    if (count == 0) return null;
    // 返回下标为count-1的数组元素，并且栈中元素个数count减一
    String tmp = items[count-1];
    --count;
    return tmp;
  }
}

动态扩容的栈类似ArrayList，需要重新申请内存控件，将数据复制出去。

Tips: 函数调用栈：操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构, 用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。

---

先到这吧，后面会写一个2，毕竟学这个还是挺无聊的。