對于正常的鏈表來說选泻,如果需要查找某個數據時冲粤,需要從頭到尾遍歷鏈表,效率比較低页眯。
而跳表就同時維護了多個鏈表梯捕,并且這些鏈表是分層的,用來快速查找數據窝撵。
最底層的鏈表維護了跳表內所有的元素傀顾,每上面一層鏈表都是下面一層鏈表的子集,
鏈表越往上數據越少碌奉。
跳表內所有元素都是排序的短曾,這樣在查找時,可以先從頂層鏈表查找道批,
一旦發(fā)現被查找的元素大于當前鏈表的取值错英,就會轉入下一層鏈表繼續(xù)查找。
也就是說在查找過程中隆豹,是跳躍式搜索椭岩。
因為持有多個鏈表,也就是說使用了空間換取時間的算法。
附上一張圖片判哥,來源于網絡
查找18這個元素時的查找路徑
跳表.jpeg