[Skip List] 跨越串列

跨越串列，中國那邊稱之為跳表，是由 William Pugh 發明的一種利用隨機性質維護有序性的資料結構，也就是說他能做到普通 binary search tree 能做到的所有操作。

skip list 由多層 (levels) 的 linked-list 組成。每一個插入 skip list 的元素要隨機決定一個高度 (height)，這個高度是幾何分布，也就是高度是 $1$ 的機率是 $1/2$；高度是 $2$ 的機率是 $1/4$；高度是 $3$ 的機率是 $1/8 $；...；高度是 $k$ 的機率是 $1/2^{k}$ 以此類推。高度為 $h$ 的元素會再 $1\sim h$ 層中存在 linked-list 節點，並且每一層的 linked-list 都是排序好的。

這樣的設計可以讓插入、刪除和搜尋變成多層的 linked-list 操作，且平均時間複雜度是 $\ord{\log n}$。

經我個人實測它的效率並沒有比 STL 的紅黑樹還要來高，另一個缺點是若要支援重複元素也較難處理。但他的優勢在於能夠輕鬆改為 concurrent 的版本，這點對需要平衡的二元搜尋樹來說極為困難， TBB 中的 concurrent set 和 concurrent map 都是使用 skip list  實作的。

這裡附上程式碼：

[Concurrent Queue] 並發隊列

在這個 AI 的時代，大多數的資料結構或演算法可以很容易透過 AI 生成。但我發現 lock-free 演算法/資料結構是個例外，AI 的生成結果經常會有 deadlock 產生，所以我打算自己試著把常見的資料結構改成 Concurrent 的形式。

我自己沒有寫註解的習慣，程式碼中所有註解是 AI 加上去的。測試我也只讓 AI 隨意生成測試程式而已，但邏輯上應該沒問題，如果有人能幫我測過我會很感激的。