跨越串列，中國那邊稱之為跳表，是由 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}$。
這裡附上程式碼：
reference_pointer<int> a;//建立一個int的引用指標a a = new_reference(5);//a指向新增int動態變數，其值為5 a = new_reference<int>(5);//同上，只是定義較為嚴謹 a = new_reference((int)5);//同上，只是定義較為嚴謹 reference_pointer<int> b = a;//將b指向a所指向之物 struct P{ int a,b; P(int _a,int _b):a(_a),b(_b){} }p(2,3); reference_pointer<P> a;//建立一個P的引用指標a c = new_reference(P(1,2));//指向新增P動態變數，其值為1,2 c = new_reference<P>(P(1,2));//同上，只是定義較為嚴謹 c = new_reference(p);//指向新增P動態變數，其值為p
