Design Skiplist LeetCode solution in Java

1
class Skiplist {
2

3
  public static final int MAX_LEVEL = 4;
4

5
  private final int levels;
6

7
  private SkipListEntry head;
8

9
  private SkipListEntry tail;
10

11
  public Skiplist() {
12
    this(MAX_LEVEL);
13
  }
14

15
  public Skiplist(int levels) {
16
    this.levels = levels;
17

18
    // init new SkipList with defined level
19
    // Firstly, create the root level (level = 0) entry for left (min) and right (max)
20
    // and linked it
21
    // LEFT <------------------------------------------------> RIGHT
22
    SkipListEntry left = new SkipListEntry(Integer.MIN_VALUE, Integer.MIN_VALUE);
23
    SkipListEntry right = new SkipListEntry(Integer.MAX_VALUE, Integer.MAX_VALUE);
24
    left.right = right;
25
    right.left = left;
26

27
    // After, we can define left and right as the head and tail nodes
28
    // HEAD = LEFT <------------------------------------------------> RIGHT = TAIL
29
    this.head = left;
30
    this.tail = right;
31

32
    // Next, we can define left and right nodes for other levels and linked it
33
    // 0 HEAD = LEFT <------------------------------------------------> RIGHT = TAIL
34
    // ^ ^
35
    // | |
36
    // v v
37
    // 1 HEAD = LEFT <------------------------------------------------> RIGHT = TAIL
38
    // ^ ^
39
    // | |
40
    // v v
41
    // 2 HEAD = LEFT <------------------------------------------------> RIGHT = TAIL
42
    // ^ ^
43
    // | |
44
    // v v
45
    // 3 HEAD = LEFT <------------------------------------------------> RIGHT = TAIL
46
    // ^ ^
47
    // | |
48
    // v v
49
    // N HEAD = LEFT <------------------------------------------------> RIGHT = TAIL
50
    for (int i = 1; i < this.levels; i++) {
51
      left.down = new SkipListEntry(Integer.MIN_VALUE, Integer.MIN_VALUE, null, null, left, null);
52
      left = left.down;
53

54
      right.down = new SkipListEntry(Integer.MAX_VALUE, Integer.MAX_VALUE, null, null, right, null);
55
      right = right.down;
56

57
      left.right = right;
58
      right.left = left;
59
    }
60
  }
61

62
  public boolean search(int target) {
63
    return this.find(target).key == target;
64
  }
65

66
  public void add(int num) {
67
    // We have to always start from head
68
    SkipListEntry current = this.head;
69

70
    // For the searching newNode we have to:
71
    // 1 - start from the head
72
    // 2 - go down the bottom level
73
    while (current.hasDown()) {
74
      current = current.down;
75
    }
76

77
    // 3 - try to find newNode
78
    while (current.hasRight() && num > current.right.key) {
79
      current = current.right;
80
    }
81

82
    // 4 - if we found newNode on the step 3, we have to do nothing (return;)
83
    if (num == current.key) {
84
      return;
85
    }
86

87
    // 5 - otherwise, we have to a put new newNode on the right
88
    SkipListEntry newNode = new SkipListEntry(num, num, current, current.right);
89
    current.right.left = newNode;
90
    current.right = newNode;
91

92
    // 6 - have to go up one level
93
    // 7 - flip the coin
94
    // 8 - if on the step 8 true - repeat step 5
95
    for (int level = this.levels - 2; level >= 0; level--) {
96
      if (!this.coinFlip(level)) {
97
        return;
98
      }
99

100
      // go up one level and find left node for new level
101
      while (!current.hasUp() && current.hasLeft()) {
102
        current = current.left;
103
      }
104
      current = current.up;
105

106
      newNode.up = new SkipListEntry(num, num, current, current.right, null, newNode);
107
      newNode = newNode.up;
108

109
      current.right.left = newNode;
110
      current.right = newNode;
111
    }
112
  }
113

114
  public boolean erase(int num) {
115
    SkipListEntry entry = this.find(num);
116
    if (entry.key != num) {
117
      return false;
118
    }
119

120
    entry.left.right = entry.right;
121
    entry.right.left = entry.left;
122

123
    while ((entry = entry.up) != null) {
124
      entry.left.right = entry.right;
125
      entry.right.left = entry.left;
126
    }
127

128
    return true;
129
  }
130

131
  private SkipListEntry find(int key) {
132
    // We have to always start from head
133
    SkipListEntry current = this.head;
134

135
    // while node has right or down we can go down a level or right
136
    // 1 - we have to go right and try to find element
137
    // 2 - if element is not presented at this level, we have to go down a level
138
    // and repeat step 1
139
    // 3 - if we found element we have to go down to the bottom
140
    // if we found element we have to return it, otherwise - return last visited
141
    while (current != null && current.hasRight()) {
142
      while (current.hasRight() && key > current.right.key) {
143
        current = current.right;
144
      }
145

146
      if (key == current.right.key) {
147
        current = current.right;
148
        while (current.hasDown()) {
149
          current = current.down;
150
        }
151

152
        return current;
153
      }
154

155
      current = current.down;
156
    }
157

158
    return this.head;
159
  }
160

161
  private boolean coinFlip(int level) {
162
    return ThreadLocalRandom.current().nextInt(this.levels - level) == 0;
163
  }
164

165
  public static class SkipListEntry {
166

167
    private final int key;
168

169
    private final int value;
170

171
    private SkipListEntry up;
172

173
    private SkipListEntry down;
174

175
    private SkipListEntry left;
176

177
    private SkipListEntry right;
178

179
    public SkipListEntry(int key, int value) {
180
      this(key, value, null, null, null, null);
181
    }
182

183
    public SkipListEntry(int key, int value, SkipListEntry left, SkipListEntry right) {
184
      this(key, value, left, right, null, null);
185
    }
186

187
    public SkipListEntry(
188
        int key,
189
        int value,
190
        SkipListEntry left,
191
        SkipListEntry right,
192
        SkipListEntry up,
193
        SkipListEntry down) {
194
      this.key = key;
195
      this.value = value;
196
      this.left = left;
197
      this.right = right;
198
      this.up = up;
199
      this.down = down;
200
    }
201

202
    public int getKey() {
203
      return this.key;
204
    }
205

206
    public int getValue() {
207
      return this.value;
208
    }
209

210
    public SkipListEntry left() {
211
      if (!this.hasLeft()) {
212
        return null;
213
      }
214

215
      return this.left;
216
    }
217

218
    public void setLeft(SkipListEntry entry) {
219
      this.left = Objects.requireNonNull(entry);
220
    }
221

222
    public SkipListEntry right() {
223
      if (!this.hasRight()) {
224
        return null;
225
      }
226

227
      return this.right;
228
    }
229

230
    public void setRight(SkipListEntry entry) {
231
      this.right = Objects.requireNonNull(entry);
232
    }
233

234
    public SkipListEntry up() {
235
      if (!this.hasUp()) {
236
        return null;
237
      }
238

239
      return this.up;
240
    }
241

242
    public void setUp(SkipListEntry entry) {
243
      this.up = Objects.requireNonNull(entry);
244
    }
245

246
    public SkipListEntry getDown() {
247
      return this.down;
248
    }
249

250
    public SkipListEntry down() {
251
      if (!this.hasDown()) {
252
        return null;
253
      }
254

255
      return this.down;
256
    }
257

258
    public void setDown(SkipListEntry entry) {
259
      this.down = Objects.requireNonNull(entry);
260
    }
261

262
    public boolean hasLeft() {
263
      return this.left != null;
264
    }
265

266
    public boolean hasRight() {
267
      return this.right != null;
268
    }
269

270
    public boolean hasUp() {
271
      return this.up != null;
272
    }
273

274
    public boolean hasDown() {
275
      return this.down != null;
276
    }
277
  }
278
}