/* * This is LinkedList is very similar to the one * we defined in class. I added a toString() method * for your convenience. * * You should implement the find() method. */ class LinkedList { /* * This class defines an Exception which can be * thrown in the case of an error involving the * "index" reference. It is a public subclass, * so that other classes can catch it, but have * to explicitly recognize its scope by referring * to it by LinkedList.IndexException */ public class IndexException extends Exception { /* * This method creates a String representation * of the Exception which has occurred */ public String toString() { return ("Bad index in Linked List"); } } /* * This class defines one piece of the linked list. * It contains an Object which represents the data * stored at the current spot, and a reference to * the next Node in the list */ private class Node { private Object data; private Node next; /* * Constructor. Initializes instance variables * to specified values */ public Node (Object data, Node next) { this.data = data; this.next = next; } /* * Constructor. Initializes data to the * specified value, and the next reference * to null */ public Node (Object data) { this.data = data; this.next = null; } /* * Returns the data */ public Object getData() { return data; } /* * Returns reference to next node */ public Node getNext() { return next; } /* * Sets the next reference to the specified value */ public void setNext(Node next) { this.next = next; } /* * Sets the data to the specified value * * We could have chosen not to implement this * method, and instead force users to create * new Node objects when they want to change * the data. */ public void setData(Object data) { this.data = data; } } private Node head; private Node tail; private Node index; /* * Constructor. By default, set all the references * to null */ public LinkedList() { head = tail = index = null; } public void addHead(Object data) { // Create new node w/data Node newNode; newNode = new Node(data); // Set new node to point to the old head newNode.setNext(head); // Reset head of list head = newNode; // Special case: empty list if (null == tail) { tail = head = index = newNode; } } public void addTail(Object data) { // Create new node w/data Node newNode = new Node(data); // special case: Empty list // can test either head or tail == null if (null == head) { head = tail = index = newNode; return; // all done } // Common case: list is not empty tail.setNext(newNode); tail = newNode; } /* * This is pretty straight-forward. It resets the index * to the head of the list. This is particularly important, * because index cannot move backwards. */ public void resetIndex() { index = head; } /* * This returns the datum from the node referenced by index. * It returns null if index is null. */ public Object getIndexedNode() { // special case: null index if (null == index) { return null; } // Common case: return indexed value return index.getData(); } /* * This moves index ahead by one node. It follows the * next reference within the linked list. */ public void advanceIndex() { // special case: null index if (null == index) { return; } // Common case: move forward index = index.getNext(); } /* * This adds a piece of data to the linked list * after the current index. It throws an exception * if index is currently null */ public void insertAfterIndex(Object data) throws IndexException { // special case: null index if (null == index) { throw new IndexException(); } // Common case Node newNode = new Node(data); newNode.setNext(index.getNext()); index.setNext(newNode); // special case: inserting after tail if (index == tail) { tail = newNode; } } /* * This deletes the node after the indexed node. It silently fails * if index is null. */ public void deleteAfterIndex() { // special case 1: null index if (null == index) { return; } // special case 2: null index.next if (null == index.getNext()) { return; } // special case 3: deleting tail if (index.getNext() == tail) { index.setNext(null); tail = index; } // common case index.setNext(index.getNext().getNext()); return; } /* * This is method converts the list to a string by * relying on the toString() method of the data element * within each node. * * This method is important, because it is called by * System.out.println(), &c. */ public String toString() { String ret = new String(); for (Node current=head; (null != current); current = current.getNext()) ret += current.getData().toString() + "\n"; return ret; } /* * You should implement this method. It should * return true if the data item is found in the list and * false otherwise. It should rely on the ".equals()" * method of the data item's class to do the comparison */ public boolean find (Object find_me) { for (Node index=head; index !=null; index = index.getNext()) { if (index.getData().equals(find_me)) return true; } return false; } /* * You should implement this method. It should * remove the first instance of the specified item * from the list. If the item is not in the list, * it should fail silently */ public void remove (Object remove_me) { // Special case: Empty list if (null == head) return; // Special case: First item in list if (index.getData().equals(remove_me)) { // Special case: deleting index if (index == head) index = null; head = head.getNext(); // Special case: only one item in list if (null == head) tail = null; return; } for (Node index=head; index.getNext() !=null; index = index.getNext()) { if (index.getNext().getData().equals(remove_me)) { // Special case: deleting index if (this.index == index.getNext()) this.index = null; // Special case: deleting tail if (tail == index.getNext()) tail = index; // Delete it! index.setNext (index.getNext().getNext()); return; } } return; } /* * This method removes the head node from the list, and returns * the data that had been stored there. In the case of an empty * list, it returns null. */ public Object removeHead() { // special case: empty list if (head == null) { return null; } Object headData = head.getData(); // special case: list with only one item if (head == tail) { head = tail = index = null; return headData; } // special case: index == head if (head == index) { head = head.getNext(); index = head; return headData; } // common case head = head.getNext(); return headData; } }