diff options
| -rw-r--r-- | CircularLinkedList.java | 178 |
1 files changed, 118 insertions, 60 deletions
diff --git a/CircularLinkedList.java b/CircularLinkedList.java index 8130b04..7aa7d94 100644 --- a/CircularLinkedList.java +++ b/CircularLinkedList.java @@ -1,39 +1,29 @@ -package circularlinkedlist; import java.util.Iterator; -public class CircularLinkedList<E> implements Iterable<E> { - - - +public class CircularLinkedList<E> implements Iterable<E> +{ // Your variables Node<E> head; Node<E> tail; int size; // BE SURE TO KEEP TRACK OF THE SIZE - - // implement this constructor - - public CircularLinkedList() { + public CircularLinkedList() + { + head = null; + tail = null; + size = 0; } - // I highly recommend using this helper method // Return Node<E> found at the specified index // be sure to handle out of bounds cases - private Node<E> getNode(int index ) { - - return null; - } - - - // attach a node to the end of the list - public boolean add(E item) { - this.add(size,item); - return false; + public boolean add(E item) + { + add(size,item); + return true; } - // Cases to handle // out of bounds // adding to empty list @@ -41,28 +31,102 @@ public class CircularLinkedList<E> implements Iterable<E> { // adding to "end" // adding anywhere else // REMEMBER TO INCREMENT THE SIZE - public void add(int index, E item){ + public void add(int index, E item) + { + Node myNode = new Node(item); + if (index < 0 || index > size) + { + throw new IndexOutOfBoundsException(); + } + + // adding to empty list + if (size == 0) + { + head = myNode; + tail = myNode; + tail.next = head; + } + // adding to front + else if (index == 0) + { + myNode.next = head; + head = myNode; + tail.next = head; + } + // adding to "end" or anywhere else + else + { + Node<E> current = head; + + for (int i = 0; i < index - 1; i++) + { + current = current.next; + } + + myNode.next = current.next; + current.next = myNode; + if (index == size) + { + tail = myNode; + tail.next = head; + } + } + + size++; } - - - // remove must handle the following cases // out of bounds // removing the only thing in the list // removing the first thing in the list (need to adjust the last thing in the list to point to the beginning) - // removing the last thing + // removing the last thing // removing any other node // REMEMBER TO DECREMENT THE SIZE - public E remove(int index) { - return null; + public E remove(int index) + { + Node<E> myNode = null; + + if (index < 0 || index >= size) + { + throw new IndexOutOfBoundsException(); + } + + if (index == 0) + { + if (size == 1) + { + head = null; + tail = null; + } + else + { + head = head.next; + tail.next = head; + } + } + else + { + Node<E> current = head; + for (int i = 0; i < index - 1; i++) + { + current = current.next; + } + myNode = current.next; + current.next = myNode.next; + + if (index == size - 1) + { + tail = current; + tail.next = head; + } + } + + size--; + return myNode.next.item; } - - - - + // Turns your list into a string // Useful for debugging public String toString(){ @@ -73,7 +137,7 @@ public class CircularLinkedList<E> implements Iterable<E> { } if(size == 1) { return head.item.toString(); - + } else{ do{ @@ -84,22 +148,22 @@ public class CircularLinkedList<E> implements Iterable<E> { } return result.toString(); } - - + + public Iterator<E> iterator() { return new ListIterator<E>(); } - + // provided code for different assignment // you should not have to change this // change at your own risk! // this class is not static because it needs the class it's inside of to survive! private class ListIterator<E> implements Iterator<E>{ - + Node<E> nextItem; Node<E> prev; int index; - + @SuppressWarnings("unchecked") //Creates a new iterator that starts at the head of the list public ListIterator(){ @@ -113,7 +177,7 @@ public class CircularLinkedList<E> implements Iterable<E> { // TODO Auto-generated method stub return size != 0; } - + // advances the iterator to the next item // handles wrapping around back to the head automatically for you public E next() { @@ -122,10 +186,10 @@ public class CircularLinkedList<E> implements Iterable<E> { nextItem = nextItem.next; index = (index + 1) % size; return prev.item; - + } - - // removed the last node was visted by the .next() call + + // removed the last node was visted by the .next() call // for example if we had just created a iterator // the following calls would remove the item at index 1 (the second person in the ring) // next() next() remove() @@ -133,38 +197,32 @@ public class CircularLinkedList<E> implements Iterable<E> { int target; if(nextItem == head) { target = size - 1; - } else{ + } else{ target = index - 1; index--; } CircularLinkedList.this.remove(target); //calls the above class } - + } - + // It's easiest if you keep it a singly linked list // SO DON'T CHANGE IT UNLESS YOU WANT TO MAKE IT HARDER - private static class Node<E>{ + private static class Node<E> + { E item; Node<E> next; - - public Node(E item) { + + public Node(E item) + { this.item = item; } - - } - - public static void main(String[] args){ - - - - - - + } + public static void main(String[] args) + { + } - - } |