Repository: TheAlgorithms/Java
Pull request #3160 (2022-06-22 06:19:16)

Fix SkipList remove operation
### **Describe your change:**

- [ ] Add an algorithm?
- [X] Fix a bug or typo in an existing algorithm?
- [ ] Documentation change?

#### References

There was a failed build: https://github.com/TheAlgorithms/Java/runs/6992142297?check_suite_focus=true

After some debugging I have found the problem. After removing some node all links for previous and next node should be reassigned. But current algorithm did not mentioned that next node could be null. For example (on this structure tests had failed in linked build):
```
[ ] --- --- --- --- --- --- --- --- --- --- --- 
[ ] --- --- --- --- --- --- --- --- --- --- --- 
[ ] [ ] --- --- --- --- --- --- --- --- --- --- 
[ ] [ ] --- --- --- --- --- --- --- --- --- --- 
[ ] [ ] --- --- --- --- --- --- --- [ ] --- --- 
[ ] [ ] --- --- [ ] --- [ ] --- --- [ ] --- --- 
[ ] [ ] [ ] --- [ ] --- [ ] --- --- [ ] --- --- 
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] 
 H   0   1   2   3   4   5   6   7   8   9  10
```
When we try to delete node with index 0, it would have null next nodes on layers 4 and 5.

I had fixed an issue and add test case with removing last node. So removing elements with pointers to null is tested separately now.

### **Checklist:**

<!-- Remove items that do not apply. For completed items, change [ ] to [x]. -->

- [X] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [X] This pull request is all my own work -- I have not plagiarized.
- [X] I know that pull requests will not be merged if they fail the automated tests.
- [X] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
- [X] All functions and variable names follow Java naming conventions.
- [ ] If this pull request resolves one or more open issues then the commit message contains `Fixes: #{$ISSUE_NO}`.



Patch:
diff --git a/src/main/java/com/thealgorithms/datastructures/lists/SkipList.java b/src/main/java/com/thealgorithms/datastructures/lists/SkipList.java
index 5cd14f9d..259406e2 100644
--- a/src/main/java/com/thealgorithms/datastructures/lists/SkipList.java
+++ b/src/main/java/com/thealgorithms/datastructures/lists/SkipList.java
@@ -117,7 +117,9 @@ public class SkipList<E extends Comparable<E>> {
         }
         for (int i = 0; i <= layer; i++) {
             current.previous(i).setNext(i, current.next(i));
-            current.next(i).setPrevious(i, current.previous(i));
+            if (current.next(i) != null) {
+                current.next(i).setPrevious(i, current.previous(i));
+            }
         }
         size--;
     }


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/lists/SkipListTest.java b/src/test/java/com/thealgorithms/datastructures/lists/SkipListTest.java
index b26de0c5..1bbe1152 100644
--- a/src/test/java/com/thealgorithms/datastructures/lists/SkipListTest.java
+++ b/src/test/java/com/thealgorithms/datastructures/lists/SkipListTest.java
@@ -42,12 +42,26 @@ class SkipListTest {
     }
 
     @Test
-    void remove() {
+    void removeFromHead() {
         SkipList<String> skipList = createSkipList();
+        String mostLeftElement = skipList.get(0);
         int initialSize = skipList.size();
         print(skipList);
 
-        skipList.remove("a");
+        skipList.remove(mostLeftElement);
+
+        print(skipList);
+        assertEquals(initialSize - 1, skipList.size());
+    }
+
+    @Test
+    void removeFromTail() {
+        SkipList<String> skipList = createSkipList();
+        String mostRightValue = skipList.get(skipList.size() - 1);
+        int initialSize = skipList.size();
+        print(skipList);
+
+        skipList.remove(mostRightValue);
 
         print(skipList);
         assertEquals(initialSize - 1, skipList.size());