Merge pull request TheAlgorithms#1477 from shellhub/dev

realDuYuanChao · web-flow · commit d0962bc959e8 · 2020-09-22T16:05:39.000+08:00
Updated SinglyLinkedList
diff --git a/DIRECTORY.md b/DIRECTORY.md
@@ -60,12 +60,14 @@
     * [MinPriorityQueue](https://github.com/TheAlgorithms/Java/blob/master/DataStructures/Heaps/MinPriorityQueue.java)
   * Lists
     * [CircleLinkedList](https://github.com/TheAlgorithms/Java/blob/master/DataStructures/Lists/CircleLinkedList.java)
+    * [CountSinglyLinkedListRecursion](https://github.com/TheAlgorithms/Java/blob/master/DataStructures/Lists/CountSinglyLinkedListRecursion.java)
     * [CursorLinkedList](https://github.com/TheAlgorithms/Java/blob/master/DataStructures/Lists/CursorLinkedList.java)
     * [DoublyLinkedList](https://github.com/TheAlgorithms/Java/blob/master/DataStructures/Lists/DoublyLinkedList.java)
     * [ListAddnFun](https://github.com/TheAlgorithms/Java/blob/master/DataStructures/Lists/ListAddnFun.java)
     * [Merge K SortedLinkedlist](https://github.com/TheAlgorithms/Java/blob/master/DataStructures/Lists/Merge_K_SortedLinkedlist.java)
     * [MergeSortedArrayList](https://github.com/TheAlgorithms/Java/blob/master/DataStructures/Lists/MergeSortedArrayList.java)
     * [MergeSortedSinglyLinkedList](https://github.com/TheAlgorithms/Java/blob/master/DataStructures/Lists/MergeSortedSinglyLinkedList.java)
+    * [SearchSinglyLinkedListRecursion](https://github.com/TheAlgorithms/Java/blob/master/DataStructures/Lists/SearchSinglyLinkedListRecursion.java)
     * [SinglyLinkedList](https://github.com/TheAlgorithms/Java/blob/master/DataStructures/Lists/SinglyLinkedList.java)
   * Queues
     * [GenericArrayListQueue](https://github.com/TheAlgorithms/Java/blob/master/DataStructures/Queues/GenericArrayListQueue.java)
diff --git a/DataStructures/Lists/CountSinglyLinkedListRecursion.java b/DataStructures/Lists/CountSinglyLinkedListRecursion.java
@@ -0,0 +1,26 @@
+package DataStructures.Lists;
+
+public class CountSinglyLinkedListRecursion extends SinglyLinkedList {
+    public static void main(String[] args) {
+        CountSinglyLinkedListRecursion list = new CountSinglyLinkedListRecursion();
+        for (int i = 1; i <= 5; ++i) {
+            list.insert(i);
+        }
+        assert list.count() == 5;
+    }
+
+    /**
+     * Calculate the count of the list manually using recursion.
+     *
+     * @param head head of the list.
+     * @return count of the list.
+     */
+    private int countRecursion(Node head) {
+        return head == null ? 0 : 1 + countRecursion(head.next);
+    }
+
+    @Override
+    public int count() {
+        return countRecursion(getHead());
+    }
+}
diff --git a/DataStructures/Lists/SearchSinglyLinkedListRecursion.java b/DataStructures/Lists/SearchSinglyLinkedListRecursion.java
@@ -0,0 +1,32 @@
+package DataStructures.Lists;
+
+public class SearchSinglyLinkedListRecursion extends SinglyLinkedList {
+    public static void main(String[] args) {
+        SearchSinglyLinkedListRecursion list = new SearchSinglyLinkedListRecursion();
+        for (int i = 1; i <= 10; ++i) {
+            list.insert(i);
+        }
+
+        for (int i = 1; i <= 10; ++i) {
+            assert list.search(i);
+        }
+        assert !list.search(-1)
+                && !list.search(100);
+    }
+
+    /**
+     * Test if the value key is present in the list using recursion.
+     *
+     * @param node the head node.
+     * @param key  the value to be searched.
+     * @return {@code true} if key is present in the list, otherwise {@code false}.
+     */
+    private boolean searchRecursion(Node node, int key) {
+        return node != null && (node.value == key || searchRecursion(node.next, key));
+    }
+
+    @Override
+    public boolean search(int key) {
+        return searchRecursion(getHead(), key);
+    }
+}
diff --git a/DataStructures/Lists/SinglyLinkedList.java b/DataStructures/Lists/SinglyLinkedList.java
@@ -194,6 +194,39 @@ public int count() {
         return count;
     }
 
+    /**
+     * Test if the value key is present in the list.
+     *
+     * @param key the value to be searched.
+     * @return {@code true} if key is present in the list, otherwise {@code false}.
+     */
+    public boolean search(int key) {
+        Node cur = head;
+        while (cur != null) {
+            if (cur.value == key) {
+                return true;
+            }
+            cur = cur.next;
+        }
+        return false;
+    }
+
+    /**
+     * Return element at special index.
+     *
+     * @param index given index of element
+     * @return element at special index.
+     */
+    public int getNth(int index) {
+        checkBounds(index, 0, size - 1);
+        Node cur = head;
+        for (int i = 0; i < index; ++i) {
+            cur = cur.next;
+        }
+        return cur.value;
+    }
+
+
     @Override
     public String toString() {
         if (size == 0) {
@@ -227,6 +260,17 @@ public static void main(String[] arg) {
         list.insertNth(1, 4);
         assert list.toString().equals("10->7->5->3->1");
 
+        /* Test search function */
+        assert list.search(10)
+                && list.search(5)
+                && list.search(1)
+                && !list.search(100);
+
+        /* Test get function */
+        assert list.getNth(0) == 10
+                && list.getNth(2) == 5
+                && list.getNth(4) == 1;
+
         /* Test delete function */
         list.deleteHead();
         list.deleteNth(1);
