数组 Array

头部加入 O(1）可以做到！！
尾部加入 O(1)
随机访问 O(1)
插入 O(n)
删除 O(n)

java的 ArrayList部分源代码：

public boolean add(E e) 
    {
        ensureCapacityInternal(size + 1);  
        elementData[size++] = e;
        return true;
    }
    
    // 将element添加到ArrayList的指定位置   
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1); 
       
        //从指定源数组中复制一个数组，复制从指定的位置开始，到目标数组的指定位置结束。
        //arraycopy(被复制的数组, 从第几个元素开始复制, 要复制到的数组, 从第几个元素开始粘贴, 一共需要复制的元素个数)
        //即在数组elementData从index位置开始，复制到index+1位置,共复制size-index个元素
        System.arraycopy(elementData, index, elementData, index + 1,size - index);
        elementData[index] = element;
        size++;
    }

链表 List

头部加入 O(1）
尾部加入 O(1)
随机访问 O(n)
插入 O(1)
删除 O(1)

跳表 SkipList

为了优化、补足链表的缺点来实现的。
在Redis中使用的是SkipList
中心思想：升维思想、空间换时间思想。
添加一级索引、二级索引。。。
一级索引加速，乘以2，每次跨过2个元素。
。。。
增加log2(n)个索引。
时间复杂度降到了O(logn)
现实中，跳表经过增加和删除，跳表变得不规范。
跳表的维护成本高，增加和删除需要修改索引。
空间复杂度为O(n)

应用

链表的应用：
LRU缓存：用双端链表和unordered_map实现。
跳表的应用：Redis中使用。跳跃表在 Redis 的唯一作用， 就是实现有序集数据类型。

为什么Redis使用的是跳表，而不是红黑树？

1、跳表和红黑树的复杂度都一样，但是实现简单。
2、红黑树的插入删除会做rebalance操作，会涉及整棵树，而跳表的操作会更加局部些。在并发环境下，锁需要盯住的节点更少。