added linked list

1 files changed, 205 insertions, 0 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);
+
+    }
+
+}