數(shù)據(jù)結構的擴展步驟：（在真正設計的時候归敬，下面的步驟的順序可以置換）
1.選擇一種基礎數(shù)據(jù)結構
2.確定基礎數(shù)據(jù)結構中需要維護的附加信息
3.檢驗基礎數(shù)據(jù)結構上的基本修改操作能否維護附加信息
4.設計需要的新操作
如果要插入數(shù)值3切诀，首先要知道3應該插入的位置。使用二分查找可以最快定位棺榔，這一步時間復雜度是O（logN）。
插入過程中往毡，原數(shù)組中所有大于3的數(shù)都要右移溶推，這一步時間復雜度是O（N）。所以總體時間復雜度是O（N）帅霜。
如果使用鏈表匆背，插入新數(shù)的方式如下：
如果要插入3，首先要知道3應該插入的位置身冀。鏈表無法使用二分查找钝尸，只能和原鏈表中的節(jié)點逐一比較大小來確定位置。這一步的時間復雜度是O（N）搂根。
插入的過程倒是很容易珍促，直接改變節(jié)點指針的目標，時間復雜度O（1）剩愧。因此總體的時間復雜度也是O（N）猪叙。
對于比較龐大的數(shù)據(jù)操作來說，這兩種方法顯然都太慢了仁卷。
——————————————
跳躍表（Skip Lists）是一種基于有序鏈表的擴展穴翩。
插入
新節(jié)點和各層索引節(jié)點逐一比較，確定原鏈表的插入位置锦积。O（logN）
把索引插入到原鏈表芒帕。O（1）
利用拋硬幣的隨機方式，決定新節(jié)點是否提升為上一級索引丰介。結果為“正”則提升并繼續(xù)拋硬幣背蟆，結果為“負”則停止鉴分。O（logN）
總體上，跳躍表插入操作的時間復雜度是O（logN）带膀，而這種數(shù)據(jù)結構所占空間是2N志珍，既空間復雜度是 O（N）。
刪除
自上而下垛叨，查找第一次出現(xiàn)節(jié)點的索引伦糯，并逐層找到每一層對應的節(jié)點。O（logN）
刪除每一層查找到的節(jié)點点额，如果該層只剩下1個節(jié)點舔株，刪除整個一層（原鏈表除外）。O（logN）
總體上还棱，跳躍表刪除操作的時間復雜度是O（logN）载慈。
進步是留給時間最美的禮物
