Fix SkipList remove operation

Boiarshinov · Boiarshinov · commit 768dc4b57227 · 2022-06-22T09:09:42.000+03:00
diff --git a/src/main/java/com/thealgorithms/datastructures/lists/SkipList.java b/src/main/java/com/thealgorithms/datastructures/lists/SkipList.java
@@ -100,6 +100,12 @@ public E get(int index) {
         return current.value;
     }
 
+    /*
+    java.lang.NullPointerException: Cannot invoke
+    "com.thealgorithms.datastructures.lists.SkipList$Node.setPrevious(int, com.thealgorithms.datastructures.lists.SkipList$Node)"
+    because the return value of "com.thealgorithms.datastructures.lists.SkipList$Node.next(int)" is null
+	at com.thealgorithms.datastructures.lists.SkipListTest.remove(SkipListTest.java:50)
+     */
     public void remove(E e) {
         Objects.requireNonNull(e);
         Node<E> current = head;
@@ -117,7 +123,9 @@ public void remove(E 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--;
     }
diff --git a/src/test/java/com/thealgorithms/datastructures/lists/SkipListTest.java b/src/test/java/com/thealgorithms/datastructures/lists/SkipListTest.java
@@ -42,12 +42,26 @@ void contains() {
     }
 
     @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());

Original file line number	Diff line number	Diff line change
`@@ -100,6 +100,12 @@ public E get(int index) {`
`100`	`100`	`return current.value;`
`101`	`101`	`}`
`102`	`102`
	`103`	`+ /*`
	`104`	`+ java.lang.NullPointerException: Cannot invoke`
	`105`	`+ "com.thealgorithms.datastructures.lists.SkipList$Node.setPrevious(int, com.thealgorithms.datastructures.lists.SkipList$Node)"`
	`106`	`+ because the return value of "com.thealgorithms.datastructures.lists.SkipList$Node.next(int)" is null`
	`107`	`+ at com.thealgorithms.datastructures.lists.SkipListTest.remove(SkipListTest.java:50)`
	`108`	`+ */`
`103`	`109`	`public void remove(E e) {`
`104`	`110`	`Objects.requireNonNull(e);`
`105`	`111`	`Node<E> current = head;`
`@@ -117,7 +123,9 @@ public void remove(E e) {`
`117`	`123`	`}`
`118`	`124`	`for (int i = 0; i <= layer; i++) {`
`119`	`125`	`current.previous(i).setNext(i, current.next(i));`
`120`		`- current.next(i).setPrevious(i, current.previous(i));`
	`126`	`+ if (current.next(i) != null) {`
	`127`	`+ current.next(i).setPrevious(i, current.previous(i));`
	`128`	`+ }`
`121`	`129`	`}`
`122`	`130`	`size--;`
`123`	`131`	`}`