一、誕生原因

解決鏈表查詢時耗時過長的問題。

二、基本信息

英文全稱：Skip List 。

鏈表 + 多級索引（鏈表） = 跳表

三、原理說明

顧名思義，跳表的查詢是在多個鏈表之間跳躍查詢的，其路線類似于走臺階，如下圖所示：

?舉個栗子：

某一時刻，想查詢代號為 8 的節點的數據，按照常規鏈表查詢，需要從最左側挨個查詢至最右側，遍歷次數為 8 ，時間復雜度為 O(n) 。

若添加一級索引，遍歷次數為 5；若再添加二級索引，遍歷次數為 4，遍歷路線猶如下臺階一跳一跳的，故該結構名為跳表。

?跳表實際上是典型的空間換時間的思想。

時間復雜度：跳表可以說是利用多級鏈表實現的二分查找，如圖所示，故?時間復雜度為 O(logn) 。

?

參考：極客時間《數據結構與算法之美》王爭

這門課真心推薦，內容很經典、栗子很形象，里面還包含了很多面試題目。真是居家旅行必備良藥。

?

（SAW：Game Over！）

?

總結

以上是生活随笔為你收集整理的数据结构与算法 / 跳表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。