Skip List
A skip list is a probabilistic data structure that provides logarithmic time operations for sequential access and search. It consists of successive “layers” of linked lists that connect increasingly sparse subsequences of elements.
Java example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Node {
int value;
Node next, down;
}
public class SkipList {
private Node head;
private int maxLevel;
public boolean search(int value) {
Node current = head;
for (int i = maxLevel; i >= 0; i--) {
while (current.next != null && current.next.value < value) {
current = current.next;
}
if (current.value == value) {
return true;
}
current = current.down;
}
return false;
}
public void insert(int value) {
int level = randomLevel();
Node newNode = new Node(value, level);
Node current = head;
// Insert node at each level
}
}
|
C++ example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| struct Node {
int value;
Node *next, *down;
};
class SkipList {
private:
Node* head;
int maxLevel;
public:
bool search(int value) {
Node *curr = head;
for (int i = maxLevel; i >= 0; i--) {
while (curr->next && curr->next->value < value)
curr = curr->next;
if (curr->value == value) return true;
curr = curr->down;
}
return false;
}
void insert(int value) {
int level = randomLevel();
Node* newNode = new Node(value, level);
Node* curr = head;
// Insert logic
}
};
|
Python example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| import random
class Node:
def __init__(self, value, max_level):
self.value = value
self.next = [None] * (max_level + 1)
self.down = None
class SkipList:
def __init__(self):
self.max_level = 0
self.head = Node(-1, self.max_level)
def insert(self, value):
level = random.randint(0, self.max_level+1)
newNode = Node(value, level)
current = self.head
# Insert logic
def search(self, value):
current = self.head
for i in range(self.max_level, -1, -1):
while current.next[i] and current.next[i].value < value:
current = current.next[i]
if current.value == value:
return True
return False
|
Skip lists provide probabilistic balancing for fast search, insert, delete in O(log n) time.
A Skip List is a data structure that allows fast search within an ordered sequence of elements. It does this by maintaining multiple layers of linked lists, where each layer skips over a fixed number of elements. This hierarchical design allows Skip Lists to achieve the same logarithmic time complexity for search, insert, and delete operations as balanced trees like AVL or Red-Black trees. However, Skip Lists are easier to implement and can be more efficient in practice.
Java Code for Skip List
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| import java.util.Random;
class Node {
int value;
Node[] next;
public Node(int value, int level) {
this.value = value;
this.next = new Node[level];
}
}
public class SkipList {
private Node head;
private int maxLevel;
private Random rand = new Random();
public SkipList() {
head = new Node(0, 16); // Max 16 levels
maxLevel = 1;
}
public void insert(int value) {
Node[] update = new Node[maxLevel];
Node x = head;
// Search in the list
for (int i = maxLevel - 1; i >= 0; i--) {
while (x.next[i] != null && x.next[i].value < value) {
x = x.next[i];
}
update[i] = x;
}
int level = rand.nextInt(16) + 1;
if (level > maxLevel) {
for (int i = maxLevel; i < level; i++) {
update[i] = head;
}
maxLevel = level;
}
x = new Node(value, level);
for (int i = 0; i < level; i++) {
x.next[i] = update[i].next[i];
update[i].next[i] = x;
}
}
}
|
C++ Code for Skip List
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #include <cstdlib>
#include <ctime>
struct Node {
int value;
Node** next;
Node(int value, int level) {
this->value = value;
this->next = new Node*[level];
}
};
class SkipList {
private:
Node* head;
int maxLevel;
public:
SkipList() : maxLevel(1) {
head = new Node(0, 16);
}
void insert(int value) {
Node* update[16];
Node* x = head;
for (int i = maxLevel - 1; i >= 0; i--) {
while (x->next[i] != nullptr && x->next[i]->value < value) {
x = x->next[i];
}
update[i] = x;
}
int level = rand() % 16 + 1;
if (level > maxLevel) {
for (int i = maxLevel; i < level; i++) {
update[i] = head;
}
maxLevel = level;
}
x = new Node(value, level);
for (int i = 0; i < level; i++) {
x->next[i] = update[i]->next[i];
update[i]->next[i] = x;
}
}
};
|
Python Code for Skip List
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| import random
class Node:
def __init__(self, value, level):
self.value = value
self.next = [None] * level
class SkipList:
def __init__(self):
self.head = Node(0, 16)
self.max_level = 1
def insert(self, value):
update = [None] * self.max_level
x = self.head
for i in reversed(range(self.max_level)):
while x.next[i] and x.next[i].value < value:
x = x.next[i]
update[i] = x
level = random.randint(1, 16)
if level > self.max_level:
for i in range(self.max_level, level):
update.append(self.head)
self.max_level = level
x = Node(value, level)
for i in range(level):
x.next[i] = update[i].next[i]
update[i].next[i] = x
|
In all three implementations, the logic is the same:
- Each node contains an array called
next to hold the next pointers for each level. - A new node is inserted at appropriate locations at all levels where it appears.
- Random levels are generated for each new node to decide how high the node will appear in the Skip List.
Skip Lists are useful because they provide a balance between efficiency and simplicity. They are particularly effective when you need a data structure that supports fast insert, delete, and search operations but you want to avoid the complexity of balanced tree structures.