學習資源

https://labuladong.online/algo/data-structure-basic/skip-list-basic/

學習記錄

今天是學習的第 7 天，主要學習了跳表核心原理：

在單鏈表中，要找到對應索引的節點，只能從頭節點開始遍歷到目標節點，因此增刪查改指定索引的元素所需的時間複雜度是 O(n)。

有幾種方法可以優化讓鏈表支持快速的查找操作：

• 哈希鏈表（LinkedHashMap）：借助鍵值映射，在 O(1) 的時間拿到目標節點
• 跳表（Skip List）：利用空間換時間，用額外的空間記錄訊息，增刪查改的時間複雜度都能優化到 O(log n)

跳表核心原理

這是一條普通的單鏈表結構：

index  0  1  2  3  4  5  6  7  8  9
node   a->b->c->d->e->f->g->h->i->j

而這是跳表的結構：

indexLevel   0-----------------------8-----10
indexLevel   0-----------4-----------8-----10
indexLevel   0-----2-----4-----6-----8-----10
indexLevel   0--1--2--3--4--5--6--7--8--9--10
nodeLevel    a->b->c->d->e->f->g->h->i->j->k

跳表是在原先鏈表的基礎上，增加了多層索引，每向上一層，索引節點的數量減少一半，索引的間隔變成 2 倍，所以索引的高度是 log n，n 代表鏈表中元素的數量。

如果我們想要查詢索引為 7 的元素 h，可以從最高層索引開始，一層一層往下查找：

• 首先，第一層的第一個索引區間是 [0, 8]，可以確定索引 7 在這個區間內，所以從下一層的節點 0 開搜索

indexLevel   0-----------------------8 // 確定在這個區間

• 第二層節點從 0 開始，索引區間 [0, 4] 不包含索引 7，繼續往右移動到節點 4，索引區間 [4, 8] 包含索引 7，所以從下一層的節點 4 開始搜索

indexLevel   0-----------4 // 不在這個區間，往右移動到 4
indexLevel   4-----------8 // 確定在這個區間

• 第三層節點從 4 開始，索引區間 [4, 6] 不包含索引 7，繼續往右移動到節點 6，索引區間 [6, 8] 包含索引 7，所以從下一層的節點 6 開始搜索

indexLevel   4-----6 // 不在這個區間，往右移動到 6
indexLevel   6-----8 // 確定在這個區間

• 第四層節點從 6 開始，索引區間 [6, 7] 包含索引 7，最終找到目標節點 h。

indexLevel   6--7 // 找到索引 7

在這個搜索過程中，會經過 log n 層索引，因此跳表的查詢，時間複雜度為 O(log n)。

學習總結

• 跳表是典型的空間換取時間的設計思路
• 需要保證每一層的索引區間盡可能二分，確保索引層的高度為 log n