Skip List: Implementation
S0
S1
S2
S3
4512 23 34
34
23 34
Lecture No.41
Data Structure
Dr. Sohail Aslam
Implementation: TowerNode
TowerNode will have array of next pointers.
Actual number of next pointers will be
decided by the random procedure.
Define MAXLEVEL as an upper limit on
number of levels in a node.
40 50 60
head tail
20 3026 57
Tower Node
Implementation: QuadNode
A quad-node stores:
•item
•link to the node before
•link to the node after
•link to the node below
•link to the node above
This will require copying the
key (item) at different levels
x
quad-node
Skip Lists with Quad Nodes
56 64 78
31 34 44
12 23 26
31
64
31 34
23
S0
S1
S2
S3