Skip to content

Commit 94e1041

Browse files
arindam89arindam89
authored
Merge branch 'master' into master
2 parents 56825a5 + e59568b commit 94e1041

File tree

2 files changed

+409
-0
lines changed

2 files changed

+409
-0
lines changed

‎src/main/java/com/thealgorithms/datastructures/lists/SkipList.java

Lines changed: 324 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,324 @@
1+
package com.thealgorithms.datastructures.lists;
2+
3+
import java.util.*;
4+
import java.util.stream.Collectors;
5+
import java.util.stream.IntStream;
6+
7+
/**
8+
* Skip list is a data structure that allows {@code O(log n)} search complexity
9+
* as well as {@code O(log n)} insertion complexity within an ordered sequence
10+
* of {@code n} elements. Thus it can get the best features of a sorted array
11+
* (for searching) while maintaining a linked list-like structure that allows
12+
* insertion, which is not possible with a static array.
13+
* <p>
14+
* A skip list is built in layers. The bottom layer is an ordinary ordered
15+
* linked list. Each higher layer acts as an "express lane" for the lists
16+
* below.
17+
* <pre>
18+
* [ ] ------> [ ] --> [ ]
19+
* [ ] --> [ ] [ ] --> [ ]
20+
* [ ] [ ] [ ] [ ] [ ] [ ]
21+
* H 0 1 2 3 4
22+
* </pre>
23+
*
24+
* @param <E> type of elements
25+
* @see <a href="https://en.wikipedia.org/wiki/Skip_list">Wiki. Skip list</a>
26+
*/
27+
public class SkipList<E extends Comparable<E>> {
28+
29+
/**
30+
* Node before first node.
31+
*/
32+
private final Node<E> head;
33+
34+
/**
35+
* Maximum layers count.
36+
* Calculated by {@link #heightStrategy}.
37+
*/
38+
private final int height;
39+
40+
/**
41+
* Function for determining height of new nodes.
42+
* @see HeightStrategy
43+
*/
44+
private final HeightStrategy heightStrategy;
45+
46+
/**
47+
* Current count of elements in list.
48+
*/
49+
private int size;
50+
51+
private static final int DEFAULT_CAPACITY = 100;
52+
53+
public SkipList() {
54+
this(DEFAULT_CAPACITY, new BernoulliHeightStrategy());
55+
}
56+
57+
public SkipList(int expectedCapacity, HeightStrategy heightStrategy) {
58+
this.heightStrategy = heightStrategy;
59+
this.height = heightStrategy.height(expectedCapacity);
60+
this.head = new Node<>(null, this.height);
61+
this.size = 0;
62+
}
63+
64+
public void add(E e) {
65+
Objects.requireNonNull(e);
66+
Node<E> current = head;
67+
int layer = height;
68+
Node<E>[] toFix = new Node[height + 1];
69+
70+
while (layer >= 0) {
71+
Node<E> next = current.next(layer);
72+
if (next == null || next.getValue().compareTo(e) > 0) {
73+
toFix[layer] = current;
74+
layer--;
75+
} else {
76+
current = next;
77+
}
78+
}
79+
int nodeHeight = heightStrategy.nodeHeight(height);
80+
Node<E> node = new Node<>(e, nodeHeight);
81+
for (int i = 0; i <= nodeHeight; i++) {
82+
if (toFix[i].next(i) != null) {
83+
node.setNext(i, toFix[i].next(i));
84+
toFix[i].next(i).setPrevious(i, node);
85+
}
86+
87+
toFix[i].setNext(i, node);
88+
node.setPrevious(i, toFix[i]);
89+
}
90+
size++;
91+
}
92+
93+
public E get(int index) {
94+
int counter = -1; // head index
95+
Node<E> current = head;
96+
while (counter != index) {
97+
current = current.next(0);
98+
counter++;
99+
}
100+
return current.value;
101+
}
102+
103+
public void remove(E e) {
104+
Objects.requireNonNull(e);
105+
Node<E> current = head;
106+
int layer = height;
107+
108+
while (layer >= 0) {
109+
Node<E> next = current.next(layer);
110+
if (e.equals(current.getValue())) {
111+
break;
112+
} else if (next == null || next.getValue().compareTo(e) > 0) {
113+
layer--;
114+
} else {
115+
current = next;
116+
}
117+
}
118+
for (int i = 0; i <= layer; i++) {
119+
current.previous(i).setNext(i, current.next(i));
120+
current.next(i).setPrevious(i, current.previous(i));
121+
}
122+
size--;
123+
}
124+
125+
/**
126+
* A search for a target element begins at the head element in the top
127+
* list, and proceeds horizontally until the current element is greater
128+
* than or equal to the target. If the current element is equal to the
129+
* target, it has been found. If the current element is greater than the
130+
* target, or the search reaches the end of the linked list, the procedure
131+
* is repeated after returning to the previous element and dropping down
132+
* vertically to the next lower list.
133+
*
134+
* @param e element whose presence in this list is to be tested
135+
* @return true if this list contains the specified element
136+
*/
137+
public boolean contains(E e) {
138+
Objects.requireNonNull(e);
139+
Node<E> current = head;
140+
int layer = height;
141+
142+
while (layer >= 0) {
143+
Node<E> next = current.next(layer);
144+
if (e.equals(current.getValue())) {
145+
return true;
146+
} else if (next == null || next.getValue().compareTo(e) > 0) {
147+
layer--;
148+
} else {
149+
current = next;
150+
}
151+
}
152+
return false;
153+
}
154+
155+
public int size() {
156+
return size;
157+
}
158+
159+
/**
160+
* Print height distribution of the nodes in a manner:
161+
* <pre>
162+
* [ ] --- --- [ ] --- [ ]
163+
* [ ] --- [ ] [ ] --- [ ]
164+
* [ ] [ ] [ ] [ ] [ ] [ ]
165+
* H 0 1 2 3 4
166+
* </pre>
167+
* Values of nodes is not presented.
168+
*
169+
* @return string representation
170+
*/
171+
@Override
172+
public String toString() {
173+
List<boolean[]> layers = new ArrayList<>();
174+
int sizeWithHeader = size + 1;
175+
for (int i = 0; i <= height; i++) {
176+
layers.add(new boolean[sizeWithHeader]);
177+
}
178+
179+
Node<E> current = head;
180+
int position = 0;
181+
while (current != null) {
182+
for (int i = 0; i <= current.height; i++) {
183+
layers.get(i)[position] = true;
184+
}
185+
current = current.next(0);
186+
position++;
187+
}
188+
189+
Collections.reverse(layers);
190+
String result = layers.stream()
191+
.map(layer -> {
192+
StringBuilder acc = new StringBuilder();
193+
for (boolean b : layer) {
194+
if (b) {
195+
acc.append("[ ]");
196+
} else {
197+
acc.append("---");
198+
}
199+
acc.append(" ");
200+
}
201+
return acc.toString();
202+
})
203+
.collect(Collectors.joining("\n"));
204+
String positions = IntStream.range(0, sizeWithHeader - 1)
205+
.mapToObj(i -> String.format("%3d", i))
206+
.collect(Collectors.joining(" "));
207+
208+
return result + String.format("%n H %s%n", positions);
209+
}
210+
211+
/**
212+
* Value container.
213+
* Each node have pointers to the closest nodes left and right from current
214+
* on each layer of nodes height.
215+
* @param <E> type of elements
216+
*/
217+
private static class Node<E> {
218+
219+
private final E value;
220+
private final int height;
221+
private final List<Node<E>> forward;
222+
private final List<Node<E>> backward;
223+
224+
@SuppressWarnings("unchecked")
225+
public Node(E value, int height) {
226+
this.value = value;
227+
this.height = height;
228+
229+
// predefined size lists with null values in every cell
230+
this.forward = Arrays.asList(new Node[height + 1]);
231+
this.backward = Arrays.asList(new Node[height + 1]);
232+
}
233+
234+
public Node<E> next(int layer) {
235+
checkLayer(layer);
236+
return forward.get(layer);
237+
}
238+
239+
public void setNext(int layer, Node<E> node) {
240+
forward.set(layer, node);
241+
}
242+
243+
public void setPrevious(int layer, Node<E> node) {
244+
backward.set(layer, node);
245+
}
246+
247+
public Node<E> previous(int layer) {
248+
checkLayer(layer);
249+
return backward.get(layer);
250+
}
251+
252+
public E getValue() {
253+
return value;
254+
}
255+
256+
private void checkLayer(int layer) {
257+
if (layer < 0 || layer > height) {
258+
throw new IllegalArgumentException();
259+
}
260+
}
261+
}
262+
263+
/**
264+
* Height strategy is a way of calculating maximum height for skip list
265+
* and height for each node.
266+
* @see BernoulliHeightStrategy
267+
*/
268+
public interface HeightStrategy {
269+
int height(int expectedSize);
270+
int nodeHeight(int heightCap);
271+
}
272+
273+
/**
274+
* In most common skip list realisation element in layer {@code i} appears
275+
* in layer {@code i+1} with some fixed probability {@code p}.
276+
* Two commonly used values for {@code p} are 1/2 and 1/4.
277+
* Probability of appearing element in layer {@code i} could be calculated
278+
* with <code>P = p<sup>i</sup>(1 - p)</code>
279+
* <p>
280+
* Maximum height that would give the best search complexity
281+
* calculated by <code>log<sub>1/p</sub>n</code>
282+
* where {@code n} is an expected count of elements in list.
283+
*/
284+
public static class BernoulliHeightStrategy implements HeightStrategy {
285+
286+
private final double probability;
287+
288+
private static final double DEFAULT_PROBABILITY = 0.5;
289+
private static final Random RANDOM = new Random();
290+
291+
public BernoulliHeightStrategy() {
292+
this.probability = DEFAULT_PROBABILITY;
293+
}
294+
295+
public BernoulliHeightStrategy(double probability) {
296+
if (probability <= 0 || probability >= 1) {
297+
throw new IllegalArgumentException("Probability should be from 0 to 1. But was: " + probability);
298+
}
299+
this.probability = probability;
300+
}
301+
302+
@Override
303+
public int height(int expectedSize) {
304+
long height = Math.round(Math.log10(expectedSize) / Math.log10(1 / probability));
305+
if (height > Integer.MAX_VALUE) {
306+
throw new IllegalArgumentException();
307+
}
308+
return (int) height;
309+
}
310+
311+
@Override
312+
public int nodeHeight(int heightCap) {
313+
int level = 0;
314+
double border = 100 * (1 - probability);
315+
while (((RANDOM.nextInt(Integer.MAX_VALUE) % 100) + 1) > border) {
316+
if (level + 1 >= heightCap) {
317+
return level;
318+
}
319+
level++;
320+
}
321+
return level;
322+
}
323+
}
324+
}

0 commit comments

Comments
 (0)