diff options
Diffstat (limited to 'graphs/java/linkedList')
4 files changed, 206 insertions, 0 deletions
diff --git a/graphs/java/linkedList/.gitignore b/graphs/java/linkedList/.gitignore new file mode 100644 index 0000000..5ff6309 --- /dev/null +++ b/graphs/java/linkedList/.gitignore @@ -0,0 +1,38 @@ +target/ +!.mvn/wrapper/maven-wrapper.jar +!**/src/main/**/target/ +!**/src/test/**/target/ + +### IntelliJ IDEA ### +.idea/modules.xml +.idea/jarRepositories.xml +.idea/compiler.xml +.idea/libraries/ +*.iws +*.iml +*.ipr + +### Eclipse ### +.apt_generated +.classpath +.factorypath +.project +.settings +.springBeans +.sts4-cache + +### NetBeans ### +/nbproject/private/ +/nbbuild/ +/dist/ +/nbdist/ +/.nb-gradle/ +build/ +!**/src/main/**/build/ +!**/src/test/**/build/ + +### VS Code ### +.vscode/ + +### Mac OS ### +.DS_Store
\ No newline at end of file diff --git a/graphs/java/linkedList/pom.xml b/graphs/java/linkedList/pom.xml new file mode 100644 index 0000000..e1a9950 --- /dev/null +++ b/graphs/java/linkedList/pom.xml @@ -0,0 +1,31 @@ +<?xml version="1.0" encoding="UTF-8"?> +<project xmlns="http://maven.apache.org/POM/4.0.0" + xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" + xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd"> + <modelVersion>4.0.0</modelVersion> + + <groupId>fr.epita.assistants</groupId> + <artifactId>linkedList</artifactId> + <version>1.0-SNAPSHOT</version> + + <properties> + <maven.compiler.source>21</maven.compiler.source> + <maven.compiler.target>21</maven.compiler.target> + <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding> + </properties> + <dependencies> + <dependency> + <groupId>junit</groupId> + <artifactId>junit</artifactId> + <version>4.12</version> + <scope>test</scope> + </dependency> + <dependency> + <groupId>org.junit.jupiter</groupId> + <artifactId>junit-jupiter</artifactId> + <version>RELEASE</version> + <scope>test</scope> + </dependency> + </dependencies> + +</project>
\ No newline at end of file diff --git a/graphs/java/linkedList/src/main/java/fr/epita/assistants/linkedlist/LinkedList.java b/graphs/java/linkedList/src/main/java/fr/epita/assistants/linkedlist/LinkedList.java new file mode 100644 index 0000000..c54f0f4 --- /dev/null +++ b/graphs/java/linkedList/src/main/java/fr/epita/assistants/linkedlist/LinkedList.java @@ -0,0 +1,99 @@ +package fr.epita.assistants.linkedlist; + +public class LinkedList<T extends Comparable<T>> { + static public class ListElement<T> { + T value; + ListElement<T> next; + + public ListElement(T value) { + this.value = value; + this.next = null; + } + } + + /** + * Initializes the list + **/ + public ListElement<T> head; + public int size; + public LinkedList() { + this.head = new ListElement<T>(null); + this.size = 0; + } + + /** + * Inserts the specified element into the list. + * The elements must be sorted in ascending order. + * null elements should be at the end of the list. + * + * @param e Element to be inserted + **/ + public void insert(T e) { + ListElement<T> h = this.head; + while ((h.next != null) && (h.next.value.compareTo(e) < 0)) + h = h.next; + + if (h.next == null) + h.next = new ListElement<T>(e); + else + { + ListElement<T> tmp = h.next; + h.next = new ListElement<>(e); + h.next.next = tmp; + } + this.size++; + } + + /** + * Returns the n-th element in the list. + * + * @param i Index + * @return The element at the given index + * @throws IndexOutOfBoundsException if there is no element at this + * index. + **/ + public T get(int i) { + if (i >= this.size || i < 0) + throw new IndexOutOfBoundsException(); + ListElement<T> h = this.head; + while(i-- != 0) + h = h.next; + return h.next.value; + } + + /** + * Removes the first occurrence of the specified element in the list. + * + * @param e Element to remove + * @return returns the element that has been removed or null + **/ + public T remove(T e) { + ListElement<T> h = this.head; + while ((h.next != null) && (h.next.value.compareTo(e) != 0)) + h = h.next; + if (h.next == null) + return null; + ListElement<T> res = h.next; + h.next = h.next.next; + res.next = null; + this.size--; + return res.value; + } + + /** + * Returns the size of the list. + * + * @return Number of elements in the list + **/ + public int size() { + return this.size; + } + + /** + * Removes all elements from the list. + **/ + public void clear() { + this.head.next = null; + this.size = 0; + } +}
\ No newline at end of file diff --git a/graphs/java/linkedList/src/test/java/fr/epita/assistants/linkedlist/LinkedListTests.java b/graphs/java/linkedList/src/test/java/fr/epita/assistants/linkedlist/LinkedListTests.java new file mode 100644 index 0000000..58ee1b1 --- /dev/null +++ b/graphs/java/linkedList/src/test/java/fr/epita/assistants/linkedlist/LinkedListTests.java @@ -0,0 +1,38 @@ +package fr.epita.assistants.linkedlist; + +import org.junit.jupiter.api.Test; +import org.junit.jupiter.api.Timeout; + +import static org.junit.jupiter.api.Assertions.*; + +public class LinkedListTests { + @Test + @Timeout(value = 10, threadMode = Timeout.ThreadMode.SEPARATE_THREAD) + public void testInsertOne() { + LinkedList<Integer> list = new LinkedList<>(); + list.insert(12); + assertEquals(Integer.valueOf(12), list.get(0), "Invalid element"); + } + + @Test + @Timeout(value = 10, threadMode = Timeout.ThreadMode.SEPARATE_THREAD) + public void testGetFail() { + LinkedList<Integer> list = new LinkedList<>(); + list.insert(3); + list.insert(5); + list.insert(2); + assertThrows(IndexOutOfBoundsException.class, () -> list.get(4)); + } + + @Test + @Timeout(value = 10, threadMode = Timeout.ThreadMode.SEPARATE_THREAD) + public void testRemoveNotPresent() { + LinkedList<Integer> list = new LinkedList<>(); + list.insert(1); + list.insert(2); + list.insert(3); + list.insert(4); + assertNull(list.remove(12), "Invalid return value of remove()"); + } + // add your own tests here +} |