//DLLNode.java /** * A doubly-linked Node. * Contains an Object, and references to the next and previous nodes. * * @author Zach Tomaszewski * @version 1 Oct 2004 */ public class DLLNode { private Object contents; private DLLNode next; private DLLNode prev; /** * Creates a new Node with no links */ public DLLNode(Object contents) { this(contents, null, null); } /** * Create a new node with the given contents, and links */ public DLLNode(Object contents, DLLNode prev, DLLNode next){ this.setValue(contents); this.setNext(next); this.setPrev(prev); } /** * Sets this node to contain the given value * * @param value The new contents of this node. */ public void setValue(Object value) { this.contents = value; } /** * Returns this node's contents. */ public Object getValue() { return this.contents; } /** * Set this node's next reference to the given node. * * @param next The node this node should point to as next in a list. */ public void setNext(DLLNode next){ this.next = next; } /** * Returns the next node in a list after this node. */ public DLLNode getNext(){ return this.next; } /** * Set this node's previous reference to the given node. * * @param prev The node this node should point to as coming before * it in a list. */ public void setPrev(DLLNode prev){ this.prev = prev; } /** * Returns the node before this node in a list. */ public DLLNode getPrev(){ return this.prev; } }//end class //DLList.java import java.util.List; import java.util.Collection; import java.util.ListIterator; import java.util.Iterator; /** * A List. * Implemented as a doubly-linked list of nodes. * * @author Zach Tomaszewski * @version 01 Oct 2004 */ public class DLList implements List { /* uses only a head and no tail for simplicity of implementation */ protected DLLNode head; public String toString() { String repres = "["; DLLNode cursor = head; while (cursor != null) { repres += cursor.getValue().toString(); cursor = cursor.getNext(); if (cursor != null) { repres += ", "; //add spacer between elements } } repres += "]"; return repres; } public boolean add (Object o) { DLLNode last = getLastNode(); if (last == null) { //no last node because list is empty head = new DLLNode(o); }else { last.setNext(new DLLNode(o, last, null)); } return true; //will always add o to the list } public void add(int index, Object newObj){ if (index == this.size()) { //just adding to the end of the list this.add(newObj); }else { DLLNode oldPos = getNode(index); //will throw any IndexOutOfBoundsEx. if (oldPos == head) { //acutally adding to head of list head = new DLLNode(newObj, null, oldPos); oldPos.setPrev(head); }else { //adding amidst list DLLNode newNode = new DLLNode(newObj, oldPos.getPrev(), oldPos); oldPos.getPrev().setNext(newNode); oldPos.setPrev(newNode); } } } public void clear() { head = null; /* this makes the chain of nodes unreachable * (despite references among themselves) * and thus all nodes are garbage collected. */ } public boolean contains(Object o) { return (getNode(o) != null); } public boolean isEmpty() { return (head == null); } public int size() { int count = 0; //count the nodes for (DLLNode cursor = head; cursor != null; cursor = cursor.getNext(), count++) { } return count; } public boolean equals(Object rhsList) { if (!(rhsList instanceof DLList)) { return false; } DLList rhs = (DLList) rhsList; DLLNode lhsCursor = this.head; DLLNode rhsCursor = rhs.head; //go through both lists, comparing each position as we go while (lhsCursor != null && rhsCursor != null && (lhsCursor.getValue()).equals(rhsCursor.getValue())) { lhsCursor = lhsCursor.getNext(); rhsCursor = rhsCursor.getNext(); } //if we reached the end of identical lists, then lhs == rhs == null. //otherwise dropped out early because lhs != rhs return (lhsCursor == null && rhsCursor == null); } public Object get(int index) { return this.getNode(index).getValue(); } public Object set(int index, Object newObj) { DLLNode node = getNode(index); Object old = node.getValue(); //need to return original value node.setValue(newObj); return old; } public int indexOf(Object o){ DLLNode cursor = head; int index = 0; while(cursor != null && !cursor.getValue().equals(o)) { cursor = cursor.getNext(); index++; } //return index value only if really found a match return (cursor != null) ? index : -1; } public int lastIndexOf(Object o){ DLLNode cursor = getLastNode(); int index = this.size() - 1; while(cursor != null && !cursor.getValue().equals(o)) { cursor = cursor.getPrev(); index--; } //return index value only if really found a match return (cursor != null) ? index : -1; } public Object remove(int index) { DLLNode node = getNode(index); //will throw any IndexOutOfBoundsException Object old = node.getValue(); //return deleted value if (node == head) { head = node.getNext(); head.setPrev(null); }else { node.getPrev().setNext(node.getNext()); // if a > n > c, now a > c if (node.getNext() != null) { node.getNext().setPrev(node.getPrev()); // if a < n < c, now a < c } } return old; } public boolean remove(Object o) { DLLNode node = this.getNode(o); //find first occurance if (node == null) { //no occurance found return false; }else { if (node == head) { head = node.getNext(); head.setPrev(null); }else { node.getPrev().setNext(node.getNext()); // if a > n > c, now a > c if (node.getNext() != null) { node.getNext().setPrev(node.getPrev()); // if a < n < c, now a < c } } return true; } } public Object[] toArray() { return toArray(new Object[0]); } public Object[] toArray(Object[] a) { if (a.length < this.size()) { // a is too small for this list a = (Object[]) java.lang.reflect.Array.newInstance( a.getClass().getComponentType(), this.size()); } int i = 0; for(DLLNode cursor = head; cursor != null; i++, cursor = cursor.getNext()){ a[i] = cursor.getValue(); } if (this.size() < a.length) { //a was longer than list a[this.size()] = null; //set element after end of list to null } return a; } // UNSUPPORTED INTERFACE METHODS public boolean addAll(Collection c){ throw new UnsupportedOperationException(); } public boolean addAll(int index, Collection c){ throw new UnsupportedOperationException(); } public boolean containsAll(Collection c){ throw new UnsupportedOperationException(); } public Iterator iterator() { throw new UnsupportedOperationException(); } public ListIterator listIterator() { throw new UnsupportedOperationException(); } public ListIterator listIterator(int index) { throw new UnsupportedOperationException(); } public boolean removeAll(Collection c){ throw new UnsupportedOperationException(); } public boolean retainAll(Collection c){ throw new UnsupportedOperationException(); } public List subList(int fromIndex, int toIndex){ throw new UnsupportedOperationException(); } // PRIVATE HELPER METHODS /** * Returns the node at the given position in the list. * Positioning starts at 0. * * @throws IndexOutOfBoundsException if position is not in the range * of the list: pos < 0 || pos >= size() */ private DLLNode getNode(int position){ DLLNode cursor = head; for (int i = 0; i < position; i++, cursor = cursor.getNext()){ if (cursor == null) { //ran off the list before reaching position throw new IndexOutOfBoundsException(); } } if (cursor != null) { return cursor; }else { //cursor is null, such when asking for pos 0 in an empty list throw new IndexOutOfBoundsException(); } } /** * Returns the first node containing the given Object. * * @return The found node, or null if no node in this list contains o. */ private DLLNode getNode(Object o){ DLLNode cursor = head; while(cursor != null && !cursor.getValue().equals(o)) { cursor = cursor.getNext(); } return cursor; } /** * Returns the last node in this list. * * @return the last node or null if this list is empty */ private DLLNode getLastNode() { DLLNode cursor = head; while (cursor != null && cursor.getNext() != null) { cursor = cursor.getNext(); } return cursor; } }//end class //DLLTest.java /** * Tests of the class DLList. * * @author Zach Tomaszewski * @version 12 Oct 2004 */ public class DLLTest { /** * Creates a DLList, reverses it, and re-reverses it. * Prints the list out each time an action is performed on it. */ public static void main(String[] args){ DLList list = new DLList(); list.add("one"); list.add("two"); list.add("three"); list.add("four"); System.out.print("A new list: \t"); System.out.println(list.toString()); list = reverseList(list); System.out.print("The list after reversal: \t"); System.out.println(list.toString()); list = reverseList(list); System.out.print("The list reversed again: \t"); System.out.println(list.toString()); System.out.println("Done."); } /** * Returns a reversed copy of a given list. * * @param original The list to reverse, which is unchanged by this method. * @return a reversed copy of original */ public static DLList reverseList(java.util.List original) { DLList rev = new DLList(); for (int i = 0; i < original.size(); i++){ //move through original, copying each element to start of rev rev.add(0, original.get(i)); } return rev; } }//end class