aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--LinkedList.java205
-rw-r--r--Sequence.java12
-rw-r--r--SortingAlgos.java46
3 files changed, 260 insertions, 3 deletions
diff --git a/LinkedList.java b/LinkedList.java
new file mode 100644
index 0000000..8721224
--- /dev/null
+++ b/LinkedList.java
@@ -0,0 +1,205 @@
+import java.util.Iterator;
+
+public class LinkedList<T> implements Sequence<T> {
+
+ private class ListNode<T> {
+ T element;
+ ListNode<T> next;
+
+ ListNode(T o) {
+ element = o;
+ next = null;
+ }
+
+ void connect(ListNode<T> n) {
+ next = n;
+ }
+
+ @Override
+ public String toString() {
+ return "Value =" + element;
+ }
+ }
+
+ private class LinkedListIterator implements Iterator<T> {
+ private int count;
+ private ListNode<T> node;
+
+ LinkedListIterator() {
+ count = 0;
+ node = firstNode;
+ }
+
+ public boolean hasNext() {
+ return count < size();
+ }
+
+ public T next() {
+ T retVal = node.element;
+ count++;
+ node = node.next;
+ return retVal;
+ }
+ }
+
+ protected ListNode<T> firstNode;
+ protected int size;
+
+ public LinkedList() {
+ firstNode = null;
+ size = 0;
+ }
+
+ public Iterator<T> iterator() {
+ return new LinkedListIterator();
+ }
+
+ public T get(int index) {
+ // get head of list, traverse to index using currentNode.next index number of times, return the element at position index
+ ListNode<T> node = firstNode;
+ for (int i = 0; i <= index; i++) {
+ if (i == index) {
+ return node.element;
+ } else {
+ node = node.next;
+ }
+ }
+ return null;
+ }
+
+ public void set(int index, T value) {
+ ListNode<T> node = firstNode;
+ for (int i = 0; i <= size; i++) {
+ if (i == index) {
+ node.element = value;
+ break;
+ } else {
+ node = node.next;
+ }
+ }
+ }
+
+ public void add(int index, T value) {
+ ListNode<T> newNode = new ListNode<>(value);
+ if (index == 0) {
+ if (size == 0) {
+ firstNode = newNode;
+ } else {
+ newNode.connect(firstNode);
+ firstNode = newNode;
+ }
+ } else {
+ ListNode<T> node = firstNode;
+ for (int i = 0; i <= index; i++) {
+ if (i == index - 1) {
+ newNode.connect(node.next);
+ node.connect(newNode);
+ break;
+ } else {
+ node = node.next;
+ }
+ }
+ }
+ size += 1;
+ }
+
+ public T remove(int index) {
+ ListNode<T> node = firstNode;
+ T toReturn = firstNode.element;
+ for (int i = 0; i <= index; i++) {
+ if (i == index - 1) {
+ toReturn = node.next.element;
+ if (i != size() - 2) { // if its the last value, we don't need to link
+ node.connect(node.next.next);
+ }
+ break;
+ } else {
+ node = node.next;
+ }
+ }
+ size--;
+ return toReturn;
+ }
+
+ public void add(T value) {
+ if (size == 0) {
+ firstNode = new ListNode<T>(value);
+ } else {
+ ListNode<T> node = firstNode;
+ for (int i = 0; i <= size; i++) {
+ if (i == size - 1) {
+ node.connect(new ListNode<T>(value));
+ break;
+ } else {
+ node = node.next;
+ }
+ }
+ }
+ size += 1;
+ }
+
+ public T remove() {
+ return remove(size() - 1);
+ }
+
+ public int size() {
+ return size;
+ }
+
+ public boolean isEmpty() {
+ return size() == 0;
+ }
+
+ public String toString() {
+
+ String s = "["; // better to use a StringBuilder etc.
+ ListNode<T> currentNode = firstNode;
+ for (int i = 0; i < size; i++) {
+ s += currentNode.element.toString() + ", ";
+ currentNode = currentNode.next;
+ }
+
+ //traverse list, add each eleemnt to s
+ return s + "]";
+ }
+
+
+ public LinkedList<T> reverse() {
+ throw new UnsupportedOperationException("Not supported yet.");
+ }
+
+ // Some basic test methods
+ public static void main(String[] args) {
+ LinkedList<String> m = new LinkedList<>();
+
+ m.add("First");
+ m.add("Second");
+ m.add("Third");
+ m.add("Fourth");
+ m.add(0, "Zeroth");
+
+ System.out.println(" List is now =\n" + m);
+
+ System.out.println(m.remove(4));
+ System.out.println(" List is now =\n" + m);
+
+ // for (String e : m) {
+ // System.out.println(e);
+ // }
+
+// //Test Set
+// m.set(0, "XXXXX");
+
+// System.out.println("List is now =\n" + m);
+// m.set(2, "YYYYY");
+
+// //Test remove
+// m.remove(2);
+// System.out.println("List is now =\n" + m);
+
+// m.remove(0);
+// System.out.println("List is now =\n" + m);
+
+ }
+
+}
diff --git a/Sequence.java b/Sequence.java
new file mode 100644
index 0000000..a53c1bf
--- /dev/null
+++ b/Sequence.java
@@ -0,0 +1,12 @@
+public interface Sequence<T> extends Iterable<T> {
+
+ T get(int index); // Get value at index
+ void set(int index, T value); // Replace value at index
+ void add(int index, T value); // Add item at index (increase size)
+ T remove(int index); // Remove item at index
+ void add(T value); // Append item
+ T remove(); // Pop item
+ int size(); // get size
+ boolean isEmpty(); // size is zero
+}
+ \ No newline at end of file
diff --git a/SortingAlgos.java b/SortingAlgos.java
index eecb3fa..980bc48 100644
--- a/SortingAlgos.java
+++ b/SortingAlgos.java
@@ -1,3 +1,5 @@
+import java.lang.reflect.Array;
+import java.lang.Class;
public class SortingAlgos {
@@ -109,6 +111,43 @@ public class SortingAlgos {
return A;
}
+ /* ************************************************************* */
+ // Name: Merge Sort
+ // Basis: Comparison
+ // Complexity: - O(nlogn) in all cases
+ // Space: O(n) memory usage (cannot sort in place)
+ // Stability: Stable
+ // Informal Description:
+ // Merge sort is a recursive algorithm. It works under
+ // the principal that an array with 1 item in it is sorted.
+ // In the divide stage, the array is split up into many
+ // arrays with single items using recursion. Then in the
+ // conquer stage, elements are recursively merged together
+ // linearlly.
+ // Base Case:
+ // A single element, return it
+ // Divide Stage:
+ // Split the array into two halves, left and right
+ // Recursively call mergeSort on these halves
+ // Conquer Stage:
+ // Combine the two sorted arrays into one sorted
+ // array, using the merge() algorithm
+ // Notes:
+ // Invented by von Neumann in 1945.
+ // The operation is O(nlogn) which is pretty much as good
+ // as you can get for general-purpose sorting algorithms.
+ // It has the same complexity in every case, since it
+ // fiddles with elements even if they're already sorted.
+ // Consequently insertionSort will be faster if lots of the
+ // elements are already sorted. Timsort merges the two
+ // algorithms for the best preformance.
+ /* ************************************************************* */
+ public static <T extends Comparable<T>> T[] mergeSort(T[] A) {
+ throw new UnsupportedOperationException("Not supported yet.");
+ // return mergeSortRecurse(A, 0, A.length - 1);
+ }
+
+
public static <T> void printArray(T[] A) {
System.out.print("[");
for (T i : A) {
@@ -119,8 +158,9 @@ public class SortingAlgos {
public static void main(String[] args) {
Integer myArray[] = {5, 6, 42, 12, 62, 9, 0, 21, 19};
- printArray(selectionSort(myArray));
- printArray(bubbleSort(myArray));
- printArray(insertionSort(myArray));
+ // printArray(selectionSort(myArray));
+ // printArray(bubbleSort(myArray));
+ // printArray(insertionSort(myArray));
+
}
} \ No newline at end of file
generated by cgit v1.2.3 (git 2.25.1) at 2025-04-27 19:45:05 +0000