Repository: TheAlgorithms/Java
Pull request #5994 (2024-10-25 12:23:45)

refactor: Enhance docs, add tests in `CursorLinkedList`
<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- 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 it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5994?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `95.00000%` with `1 line` in your changes missing coverage. Please review.
> Project coverage is 68.38%. Comparing base [(`5246f63`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/5246f635797194f5f0d7ac93af61099a5764fa4f?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`a363e58`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/a363e58bfdfd4387993edbeb0c10f9d20972eb6b?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5994?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...orithms/datastructures/lists/CursorLinkedList.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5994?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fdatastructures%2Flists%2FCursorLinkedList.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9kYXRhc3RydWN0dXJlcy9saXN0cy9DdXJzb3JMaW5rZWRMaXN0LmphdmE=) | 95.00% | [0 Missing and 1 partial :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5994?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #5994      +/-   ##
============================================
+ Coverage     67.98%   68.38%   +0.40%     
- Complexity     4586     4605      +19     
============================================
  Files           620      620              
  Lines         17116    17121       +5     
  Branches       3305     3305              
============================================
+ Hits          11636    11709      +73     
+ Misses         5035     4962      -73     
- Partials        445      450       +5     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5994?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).


Patch:
diff --git a/DIRECTORY.md b/DIRECTORY.md
index 820b80cd..6a733019 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -830,6 +830,7 @@
             * lists
               * [CircleLinkedListTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/lists/CircleLinkedListTest.java)
               * [CreateAndDetectLoopTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/lists/CreateAndDetectLoopTest.java)
+              * [CursorLinkedListTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/lists/CursorLinkedListTest.java)
               * [MergeKSortedLinkedListTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/lists/MergeKSortedLinkedListTest.java)
               * [MergeSortedArrayListTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/lists/MergeSortedArrayListTest.java)
               * [MergeSortedSinglyLinkedListTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/lists/MergeSortedSinglyLinkedListTest.java)
diff --git a/src/main/java/com/thealgorithms/datastructures/lists/CursorLinkedList.java b/src/main/java/com/thealgorithms/datastructures/lists/CursorLinkedList.java
index b4fa9c51..ff3d3911 100644
--- a/src/main/java/com/thealgorithms/datastructures/lists/CursorLinkedList.java
+++ b/src/main/java/com/thealgorithms/datastructures/lists/CursorLinkedList.java
@@ -3,18 +3,20 @@ package com.thealgorithms.datastructures.lists;
 import java.util.Objects;
 
 /**
- * This class implements a Cursor Linked List.
- *
- * A CursorLinkedList is an array version of a Linked List. Essentially you have
- * an array of list nodes but instead of each node containing a pointer to the
- * next item in the linked list, each node element in the array contains the
- * index for the next node element.
+ * CursorLinkedList is an array-based implementation of a singly linked list.
+ * Each node in the array simulates a linked list node, storing an element and
+ * the index of the next node. This structure allows for efficient list operations
+ * without relying on traditional pointers.
  *
+ * @param <T> the type of elements in this list
  */
 public class CursorLinkedList<T> {
 
+    /**
+     * Node represents an individual element in the list, containing the element
+     * itself and a pointer (index) to the next node.
+     */
     private static class Node<T> {
-
         T element;
         int next;
 
@@ -31,7 +33,7 @@ public class CursorLinkedList<T> {
     private static final int CURSOR_SPACE_SIZE = 100;
 
     {
-        // init at loading time
+        // Initialize cursor space array and free list pointers
         cursorSpace = new Node[CURSOR_SPACE_SIZE];
         for (int i = 0; i < CURSOR_SPACE_SIZE; i++) {
             cursorSpace[i] = new Node<>(null, i + 1);
@@ -39,12 +41,18 @@ public class CursorLinkedList<T> {
         cursorSpace[CURSOR_SPACE_SIZE - 1].next = 0;
     }
 
+    /**
+     * Constructs an empty CursorLinkedList with the default capacity.
+     */
     public CursorLinkedList() {
         os = 0;
         count = 0;
         head = -1;
     }
 
+    /**
+     * Prints all elements in the list in their current order.
+     */
     public void printList() {
         if (head != -1) {
             int start = head;
@@ -57,27 +65,36 @@ public class CursorLinkedList<T> {
     }
 
     /**
-     * @return the logical index of the element within the list , not the actual
-     * index of the [cursorSpace] array
+     * Finds the logical index of a specified element in the list.
+     *
+     * @param element the element to search for in the list
+     * @return the logical index of the element, or -1 if not found
+     * @throws NullPointerException if element is null
      */
     public int indexOf(T element) {
-        Objects.requireNonNull(element);
-        Node<T> iterator = cursorSpace[head];
-        for (int i = 0; i < count; i++) {
-            if (iterator.element.equals(element)) {
-                return i;
+        if (element == null) {
+            throw new NullPointerException("Element cannot be null");
+        }
+        try {
+            Objects.requireNonNull(element);
+            Node<T> iterator = cursorSpace[head];
+            for (int i = 0; i < count; i++) {
+                if (iterator.element.equals(element)) {
+                    return i;
+                }
+                iterator = cursorSpace[iterator.next];
             }
-            iterator = cursorSpace[iterator.next];
+        } catch (Exception e) {
+            return -1;
         }
-
         return -1;
     }
 
     /**
-     * @param position , the logical index of the element , not the actual one
-     * within the [cursorSpace] array . this method should be used to get the
-     * index give by indexOf() method.
-     * @return
+     * Retrieves an element at a specified logical index in the list.
+     *
+     * @param position the logical index of the element
+     * @return the element at the specified position, or null if index is out of bounds
      */
     public T get(int position) {
         if (position >= 0 && position < count) {
@@ -88,15 +105,18 @@ public class CursorLinkedList<T> {
                 if (counter == position) {
                     return element;
                 }
-
                 start = cursorSpace[start].next;
                 counter++;
             }
         }
-
         return null;
     }
 
+    /**
+     * Removes the element at a specified logical index from the list.
+     *
+     * @param index the logical index of the element to remove
+     */
     public void removeByIndex(int index) {
         if (index >= 0 && index < count) {
             T element = get(index);
@@ -104,19 +124,22 @@ public class CursorLinkedList<T> {
         }
     }
 
+    /**
+     * Removes a specified element from the list.
+     *
+     * @param element the element to be removed
+     * @throws NullPointerException if element is null
+     */
     public void remove(T element) {
         Objects.requireNonNull(element);
-
-        // case element is in the head
         T tempElement = cursorSpace[head].element;
         int tempNext = cursorSpace[head].next;
         if (tempElement.equals(element)) {
             free(head);
             head = tempNext;
-        } else { // otherwise cases
+        } else {
             int prevIndex = head;
             int currentIndex = cursorSpace[prevIndex].next;
-
             while (currentIndex != -1) {
                 T currentElement = cursorSpace[currentIndex].element;
                 if (currentElement.equals(element)) {
@@ -124,15 +147,34 @@ public class CursorLinkedList<T> {
                     free(currentIndex);
                     break;
                 }
-
                 prevIndex = currentIndex;
                 currentIndex = cursorSpace[prevIndex].next;
             }
         }
-
         count--;
     }
 
+    /**
+     * Allocates a new node index for storing an element.
+     *
+     * @return the index of the newly allocated node
+     * @throws OutOfMemoryError if no space is available in cursor space
+     */
+    private int alloc() {
+        int availableNodeIndex = cursorSpace[os].next;
+        if (availableNodeIndex == 0) {
+            throw new OutOfMemoryError();
+        }
+        cursorSpace[os].next = cursorSpace[availableNodeIndex].next;
+        cursorSpace[availableNodeIndex].next = -1;
+        return availableNodeIndex;
+    }
+
+    /**
+     * Releases a node back to the free list.
+     *
+     * @param index the index of the node to release
+     */
     private void free(int index) {
         Node<T> osNode = cursorSpace[os];
         int osNext = osNode.next;
@@ -141,44 +183,26 @@ public class CursorLinkedList<T> {
         cursorSpace[index].next = osNext;
     }
 
+    /**
+     * Appends an element to the end of the list.
+     *
+     * @param element the element to append
+     * @throws NullPointerException if element is null
+     */
     public void append(T element) {
         Objects.requireNonNull(element);
         int availableIndex = alloc();
         cursorSpace[availableIndex].element = element;
-
         if (head == -1) {
             head = availableIndex;
+        } else {
+            int iterator = head;
+            while (cursorSpace[iterator].next != -1) {
+                iterator = cursorSpace[iterator].next;
+            }
+            cursorSpace[iterator].next = availableIndex;
         }
-
-        int iterator = head;
-        while (cursorSpace[iterator].next != -1) {
-            iterator = cursorSpace[iterator].next;
-        }
-
-        cursorSpace[iterator].next = availableIndex;
         cursorSpace[availableIndex].next = -1;
-
         count++;
     }
-
-    /**
-     * @return the index of the next available node
-     */
-    private int alloc() {
-        // 1- get the index at which the os is pointing
-        int availableNodeIndex = cursorSpace[os].next;
-
-        if (availableNodeIndex == 0) {
-            throw new OutOfMemoryError();
-        }
-
-        // 2- make the os point to the next of the  @var{availableNodeIndex}
-        cursorSpace[os].next = cursorSpace[availableNodeIndex].next;
-
-        // this to indicate an end of the list , helpful at testing since any err
-        // would throw an outOfBoundException
-        cursorSpace[availableNodeIndex].next = -1;
-
-        return availableNodeIndex;
-    }
 }


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/lists/CursorLinkedListTest.java b/src/test/java/com/thealgorithms/datastructures/lists/CursorLinkedListTest.java
new file mode 100644
index 00000000..bf550182
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/lists/CursorLinkedListTest.java
@@ -0,0 +1,112 @@
+package com.thealgorithms.datastructures.lists;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertNull;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
+
+class CursorLinkedListTest {
+    private CursorLinkedList<String> list;
+
+    @BeforeEach
+    void setUp() {
+        list = new CursorLinkedList<>();
+    }
+
+    @Test
+    void testAppendAndGet() {
+        list.append("First");
+        list.append("Second");
+        list.append("Third");
+
+        assertEquals("First", list.get(0));
+        assertEquals("Second", list.get(1));
+        assertEquals("Third", list.get(2));
+        assertNull(list.get(3));
+        assertNull(list.get(-1));
+    }
+
+    @Test
+    void testIndexOf() {
+        list.append("First");
+        list.append("Second");
+        list.append("Third");
+
+        assertEquals(0, list.indexOf("First"));
+        assertEquals(1, list.indexOf("Second"));
+        assertEquals(2, list.indexOf("Third"));
+        assertEquals(-1, list.indexOf("NonExistent"));
+    }
+
+    @Test
+    void testRemove() {
+        list.append("First");
+        list.append("Second");
+        list.append("Third");
+
+        list.remove("Second");
+        assertEquals("First", list.get(0));
+        assertEquals("Third", list.get(1));
+        assertNull(list.get(2));
+        assertEquals(-1, list.indexOf("Second"));
+    }
+
+    @Test
+    void testRemoveByIndex() {
+        list.append("First");
+        list.append("Second");
+        list.append("Third");
+
+        list.removeByIndex(1);
+        assertEquals("First", list.get(0));
+        assertEquals("Third", list.get(1));
+        assertNull(list.get(2));
+    }
+
+    @Test
+    void testRemoveFirstElement() {
+        list.append("First");
+        list.append("Second");
+
+        list.remove("First");
+        assertEquals("Second", list.get(0));
+        assertNull(list.get(1));
+        assertEquals(-1, list.indexOf("First"));
+    }
+
+    @Test
+    void testRemoveLastElement() {
+        list.append("First");
+        list.append("Second");
+
+        list.remove("Second");
+        assertEquals("First", list.get(0));
+        assertNull(list.get(1));
+        assertEquals(-1, list.indexOf("Second"));
+    }
+
+    @Test
+    void testNullHandling() {
+        assertThrows(NullPointerException.class, () -> list.append(null));
+        assertThrows(NullPointerException.class, () -> list.remove(null));
+        assertThrows(NullPointerException.class, () -> list.indexOf(null));
+    }
+
+    @Test
+    void testEmptyList() {
+        assertNull(list.get(0));
+        assertEquals(-1, list.indexOf("Any"));
+    }
+
+    @Test
+    void testMemoryLimitExceeded() {
+        // Test adding more elements than CURSOR_SPACE_SIZE
+        assertThrows(OutOfMemoryError.class, () -> {
+            for (int i = 0; i < 101; i++) { // CURSOR_SPACE_SIZE is 100
+                list.append("Element" + i);
+            }
+        });
+    }
+}