數(shù)組 Array

頭部加入 O(1）可以做到?。?br> 尾部加入 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); 
       
        //從指定源數(shù)組中復(fù)制一個數(shù)組，復(fù)制從指定的位置開始，到目標數(shù)組的指定位置結(jié)束。
        //arraycopy(被復(fù)制的數(shù)組, 從第幾個元素開始復(fù)制, 要復(fù)制到的數(shù)組, 從第幾個元素開始粘貼, 一共需要復(fù)制的元素個數(shù))
        //即在數(shù)組elementData從index位置開始，復(fù)制到index+1位置,共復(fù)制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

為了優(yōu)化、補足鏈表的缺點來實現(xiàn)的。
在Redis中使用的是SkipList
中心思想：升維思想、空間換時間思想。
添加一級索引、二級索引。。。
一級索引加速，乘以2，每次跨過2個元素。
。。。
增加log2(n)個索引。
時間復(fù)雜度降到了O(logn)
現(xiàn)實中，跳表經(jīng)過增加和刪除，跳表變得不規(guī)范。
跳表的維護成本高，增加和刪除需要修改索引。
空間復(fù)雜度為O(n)

應(yīng)用

鏈表的應(yīng)用：
LRU緩存：用雙端鏈表和unordered_map實現(xiàn)。
跳表的應(yīng)用：Redis中使用。跳躍表在 Redis 的唯一作用， 就是實現(xiàn)有序集數(shù)據(jù)類型。

為什么Redis使用的是跳表，而不是紅黑樹？

1、跳表和紅黑樹的復(fù)雜度都一樣，但是實現(xiàn)簡單。
2、紅黑樹的插入刪除會做rebalance操作，會涉及整棵樹，而跳表的操作會更加局部些。在并發(fā)環(huán)境下，鎖需要盯住的節(jié)點更少。