Repository: TheAlgorithms/Java
Pull request #5519 (2024-10-02 11:49:49)

Sorted Linked List Added
<!--
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/5519?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 `72.72727%` with `18 lines` in your changes missing coverage. Please review.
> Project coverage is 52.37%. Comparing base [(`0bd86b3`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/0bd86b3d7ed24029a799e7215893865b7eb42c35?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`3dce7f0`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/3dce7f0ff797dad43181b8b10f64dafbf6252914?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/5519?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/SortedLinkedList.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5519?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fdatastructures%2Flists%2FSortedLinkedList.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9kYXRhc3RydWN0dXJlcy9saXN0cy9Tb3J0ZWRMaW5rZWRMaXN0LmphdmE=) | 72.72% | [15 Missing and 3 partials :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5519?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    #5519      +/-   ##
============================================
+ Coverage     52.29%   52.37%   +0.08%     
- Complexity     3257     3275      +18     
============================================
  Files           525      526       +1     
  Lines         15185    15251      +66     
  Branches       2887     2900      +13     
============================================
+ Hits           7941     7988      +47     
- Misses         6920     6935      +15     
- Partials        324      328       +4     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5519?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).

alxkm: Now it looks good, thanks

Patch:
diff --git a/src/main/java/com/thealgorithms/datastructures/lists/SortedLinkedList.java b/src/main/java/com/thealgorithms/datastructures/lists/SortedLinkedList.java
new file mode 100644
index 00000000..4cf78267
--- /dev/null
+++ b/src/main/java/com/thealgorithms/datastructures/lists/SortedLinkedList.java
@@ -0,0 +1,141 @@
+package com.thealgorithms.datastructures.lists;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * A SortedLinkedList is a data structure that maintains a sorted list of elements.
+ * Elements are ordered based on their natural ordering or by a Comparator provided at the time of creation.
+ * This implementation uses a singly linked list to store the elements.
+ * Further details can be found on this link
+ * https://runestone.academy/ns/books/published/cppds/LinearLinked/ImplementinganOrderedList.html
+ */
+public class SortedLinkedList {
+    private Node head;
+    private Node tail;
+
+    public SortedLinkedList() {
+        this.head = null;
+        this.tail = null;
+    }
+
+    /**
+     * Inserts a new element into the sorted linked list.
+     * @param value the value to be inserted
+     */
+    public void insert(int value) {
+        Node newNode = new Node(value);
+        if (head == null) {
+            this.head = newNode;
+            this.tail = newNode;
+        } else if (value < head.value) {
+            newNode.next = this.head;
+            this.head = newNode;
+        } else if (value > tail.value) {
+            this.tail.next = newNode;
+            this.tail = newNode;
+        } else {
+            Node temp = head;
+            while (temp.next != null && temp.next.value < value) {
+                temp = temp.next;
+            }
+            newNode.next = temp.next;
+            temp.next = newNode;
+            if (newNode.next == null) {
+                this.tail = newNode;
+            }
+        }
+    }
+
+    /**
+     * Displays the elements of the sorted linked list.
+     */
+    public void display() {
+        System.out.println(this.toString());
+    }
+
+    /**
+     * Deletes the first occurrence of the specified element in the sorted linked list.
+     * @param value the value to be deleted
+     * @return true if the element is found and deleted, false otherwise
+     */
+    public boolean delete(int value) {
+        if (this.head == null) {
+            return false;
+        } else if (this.head.value == value) {
+            if (this.head.next == null) {
+                this.head = null;
+                this.tail = null;
+            } else {
+                this.head = this.head.next;
+            }
+            return true;
+        } else {
+            Node temp = this.head;
+            while (temp.next != null) {
+                if (temp.next.value == value) {
+                    if (temp.next == this.tail) {
+                        this.tail = temp;
+                    }
+                    temp.next = temp.next.next;
+                    return true;
+                }
+                temp = temp.next;
+            }
+            return false;
+        }
+    }
+
+    /**
+     * Searches for the specified element in the sorted linked list.
+     * @param value the value to be searched
+     * @return true if the element is found, false otherwise
+     */
+    public boolean search(int value) {
+        Node temp = this.head;
+        while (temp != null) {
+            if (temp.value == value) {
+                return true;
+            }
+            temp = temp.next;
+        }
+        return false;
+    }
+
+    /**
+     * Checks if the sorted linked list is empty.
+     * @return true if the list is empty, false otherwise
+     */
+    public boolean isEmpty() {
+        return head == null;
+    }
+    /**
+     * Returns a string representation of the sorted linked list.
+     * @return a string representation of the sorted linked list
+     */
+    @Override
+    public String toString() {
+        if (this.head != null) {
+            List<String> elements = new ArrayList<>();
+            Node temp = this.head;
+            while (temp != null) {
+                elements.add(String.valueOf(temp.value));
+                temp = temp.next;
+            }
+            return "[" + String.join(", ", elements) + "]";
+
+        } else {
+            return "[]";
+        }
+    }
+
+    public final class Node {
+        public final int value;
+        public Node next;
+
+        public Node(int value) {
+            this.value = value;
+            this.next = null;
+        }
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/lists/SortedLinkedListTest.java b/src/test/java/com/thealgorithms/datastructures/lists/SortedLinkedListTest.java
new file mode 100644
index 00000000..4877e6db
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/lists/SortedLinkedListTest.java
@@ -0,0 +1,67 @@
+package com.thealgorithms.datastructures.lists;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertFalse;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+import org.junit.jupiter.api.Test;
+
+public class SortedLinkedListTest {
+
+    @Test
+    public void testInsert() {
+        SortedLinkedList list = new SortedLinkedList();
+        list.insert(5);
+        list.insert(3);
+        list.insert(7);
+        assertEquals("[3, 5, 7]", list.toString());
+    }
+
+    @Test
+    public void testDelete() {
+        SortedLinkedList list = new SortedLinkedList();
+        list.insert(5);
+        list.insert(3);
+        list.insert(7);
+        assertTrue(list.delete(5));
+        assertEquals("[3, 7]", list.toString());
+        assertFalse(list.delete(10));
+    }
+
+    @Test
+    public void testSearch() {
+        SortedLinkedList list = new SortedLinkedList();
+        list.insert(5);
+        list.insert(3);
+        list.insert(7);
+        assertTrue(list.search(5));
+        assertFalse(list.search(10));
+    }
+    @Test
+    public void testEmptyList() {
+        SortedLinkedList list = new SortedLinkedList();
+        assertEquals("[]", list.toString());
+        assertFalse(list.delete(5));
+        assertFalse(list.search(5));
+    }
+    @Test
+    public void testIsEmptyOnEmptyList() {
+        SortedLinkedList list = new SortedLinkedList();
+        assertTrue(list.isEmpty());
+    }
+
+    @Test
+    public void testIsEmptyOnNonEmptyList() {
+        SortedLinkedList list = new SortedLinkedList();
+        list.insert(10);
+        assertFalse(list.isEmpty());
+    }
+
+    @Test
+    public void testIsEmptyAfterDeletion() {
+        SortedLinkedList list = new SortedLinkedList();
+        list.insert(10);
+        list.delete(10);
+        assertTrue(list.isEmpty());
+    }
+}