• Array数组
      数组支持随机访问，根据下标随机访问的时间复杂度为O(1)
      计算元素的内存地址：a[i]_address = base_address + I * data_type_size

    查询方便、增加删除麻烦 超过容量时重新生成*2容量对象 原数据复制过去
    Java源码
    ArrayList
    https://developer.classpath.org/doc/java/util/ArrayList-source.html

    练习题：
    三数之和：https://leetcode-cn.com/problems/3sum/
    求众数：https://leetcode-cn.com/problems/majority-element/
    求缺失的第一个正数：https://leetcode-cn.com/problems/first-missing-positive/

    • LinkedList链表

    单链表
    元素用class来定义 https://www.geeksforgeeks.org/implementing-a-linked-list-in-java-using-class/

    1. class LinkedList {
    2.   Node head; // head of list
    4.   /* Linked list Node*/
    5.   class Node {
    7.       int data;
    9.       Node next;
    12.       // Constructor to create a new node
    13.       // Next is by default initialized
    14.       // as null
    15.       Node(int d) { data = d; }
    17.   }
    18. }

    练习题
    环形链表：https://leetcode-cn.com/problems/linked-list-cycle/
    合并K个排序链表：https://leetcode-cn.com/problems/merge-k-sorted-lists/
    LeetCode对应编号：206，141，21，19，876

    LinkedList LRU Cache
    https://www.jianshu.com/p/b1ab4a170c3c
    https://leetcode-cn.com/problems/lru-cache/

    • 跳表 理解不手写
      SkipList 解决链表的缺陷，查询O(n)的问题
      给链表加速：
      中心思想 升维，空间换时间
      简单优化：添加头尾指针
      升维 增加多级索引 log2N级索引
      n/2、n/4、n/8、第k级索引结点的个数就是n/(2^k)
      假设索引有h级，最高级的索引有2个结点 n/(2^h) = 2 得到h = log2(n) - 1

    SkipList Redis
    https://redisbook.readthedocs.io/en/latest/internal-datastruct/skiplist.html
    https://www.zhihu.com/question/20202931