package rpi.goldsd.container; import java.util.Enumeration; /** * The LinkedList class provides a generic linked list container * by managing a doubly linked list of ListNode objects. * * @see ListNode * @see Comparable * @version 1.3, 4/16/98 * @author David Goldschmidt */ public class LinkedList { /** * The default constructor simply sets the protected data elements of * this linked-list to values indicating an empty list. *

* This method performs in constant time O(1). */ public LinkedList() { this.head = this.tail = null; this.numElements = 0; } /** * Adds a new ListNode object to this linked-list after the * given ListNode object existingNode. *

* This method performs in constant time O(1); however, * this method assumes that the existingNode does indeed * exist in this linked-list. * @param existingNode the element after which newNode will * be added to this linked-list. * @param newNode the element to be added to this linked-list. */ public synchronized void addAfter( ListNode existingNode, ListNode newNode ) { if ( tail == existingNode ) addToTail( newNode ); else { newNode.setNext( existingNode.getNext() ); existingNode.setNext( newNode ); newNode.setPrevious( existingNode ); if ( newNode.getNext() != null ) newNode.getNext().setPrevious( newNode ); numElements++; } } /** * Adds a new ListNode object to this linked-list at the * beginning of the list. *

* This method performs in constant time O(1). * @param newNode the element to be added to the beginning of this * linked-list. */ public synchronized void addToHead( ListNode newNode ) { if ( head != null ) head.setPrevious( newNode ); newNode.setNext( head ); newNode.setPrevious( null ); head = newNode; if ( numElements++ == 0 ) tail = head; } /** * Adds a new ListNode object to this linked-list at the end of * the list. *

* This method performs in constant time O(1). * @param newNode the element to be added to the end of this linked-list. */ public synchronized void addToTail( ListNode newNode ) { if ( numElements++ == 0 ) head = newNode; else tail.setNext( newNode ); newNode.setPrevious( tail ); tail = newNode; newNode.setNext( null ); } /** * Tests whether the given Comparable object exists in this * linked-list by using the isEqualTo() method. *

* This method performs in linear time O(n). * @param node the ListNode or Comparable object to * be found in this linked-list. * @return true if node is in this linked-list; * false otherwise. */ public synchronized boolean contains( Comparable node ) { return ( find( node ) != null ); } /** * Tests whether the given ListNode object exists in this * linked-list by comparing the references of the objects * (using the == operator). *

* This method performs in linear time O(n). * @param node the ListNode object to be found in this linked-list. * @return true if node is in this linked-list; * false otherwise. */ public synchronized boolean containsReferenceTo( ListNode node ) { Enumeration e = elements(); while ( e.hasMoreElements() ) if ( ((ListNode)e.nextElement()) == node ) return true; return false; } /** * Provides an enumeration or traversal of this linked-list * starting at the beginning of the list. The nextElement() * method of the instantiated Enumeration object returns the * next ListNode object in this list. *

* This method performs in constant time O(1); however, note that * an algorithm making use of the resulting Enumeration will * likely be linear O(n). * @return an Enumeration object representing a traversal of * this linked-list from head to tail. */ public synchronized Enumeration elements() { return ( new Enumeration() { ListNode current = head; public boolean hasMoreElements() { return ( current != null ); } public Object nextElement() { if ( ! hasMoreElements() ) return null; ListNode result = current; current = (ListNode)current.getNext(); return result; } } ); } /** * Traverses this linked-list to find the given Comparable * object by using the isEqualTo() method. *

* This method performs in linear time O(n). * @param node the ListNode or Comparable object to be * found in this linked-list. * @return a reference to the ListNode that was found; or * null if not found. */ public ListNode find( Comparable node ) { Enumeration e = elements(); while ( e.hasMoreElements() ) { ListNode N = (ListNode)e.nextElement(); if ( N.isEqualTo( node ) ) return N; } return null; } /** * Returns the number of elements in this linked-list. *

* This method performs in constant time O(1). * @return the number of elements in this linked-list. */ public synchronized int getSize() { return numElements; } /** * Returns true if this linked-list contains no elements. *

* This method performs in constant time O(1). * @return true if this linked-list contains no elements; * false otherwise. */ public synchronized boolean isEmpty() { return ( head == null ); } /** * Removes and returns a reference to the first occurrence * of the given ListNode or Comparable object. * To find the given object in this linked-list, the isEqualTo() * method is applied to the given argument and each node of this linked-list. * Note that the reference that is returned refers to the ListNode * object that is removed (or null if not found). *

* This method performs in linear time O(n). * @param node the ListNode or Comparable object to be * removed from this linked-list. * @return the removed ListNode object; or null if no * object is removed from this linked-list. */ public synchronized ListNode remove( Comparable node ) { if ( numElements == 0 ) return null; ListNode result = null; if ( head.isEqualTo( node ) ) { result = head; head = (ListNode)head.getNext(); if ( head != null ) head.setPrevious( null ); } else { boolean found = false; Enumeration e = elements(); while ( ! found && e.hasMoreElements() ) { result = (ListNode)e.nextElement(); if ( result.isEqualTo( node ) ) found = true; } if ( ! found ) return null; if ( result.getPrevious() != null ) result.getPrevious().setNext( result.getNext() ); if ( result.getNext() != null ) result.getNext().setPrevious( result.getPrevious() ); if ( result == tail ) tail = (ListNode)result.getPrevious(); } if ( --numElements == 0 ) head = tail = null; result.setNext( null ); result.setPrevious( null ); return result; } /** * Removes and returns a reference to the ListNode object that * is currently the head of this list. *

* This method performs in constant time O(1). * @return the removed ListNode object; or null if the * list contains no elements. */ public synchronized ListNode removeFromHead() { if ( numElements == 0 ) return null; ListNode result = head; head = (ListNode)head.getNext(); if ( head != null ) head.setPrevious( null ); if ( --numElements == 0 ) head = tail = null; result.setNext( null ); result.setPrevious( null ); return result; } /** * Removes and returns a reference to the ListNode object that * is currently the tail of this list. *

* This method performs in constant time O(1). * @return the removed ListNode object; or null if the * list contains no elements. */ public synchronized ListNode removeFromTail() { if ( numElements == 0 ) return null; ListNode result = tail; tail = (ListNode)tail.getPrevious(); if ( tail != null ) tail.setNext( null ); if ( --numElements == 0 ) head = tail = null; result.setNext( null ); result.setPrevious( null ); return result; } /** * The toString() is the default method used to display this * linked-list in the form of a String object. * @return a String representing this linked-list. */ public synchronized String toString() { if ( numElements == 0 ) return ""; String s = ""; Enumeration e = elements(); while ( e.hasMoreElements() ) { ListNode node = (ListNode)e.nextElement(); s = s + "[" + node + "]"; if ( node != tail ) s = s + "<-->"; } return s; } /** A reference to the first element of this linked-list. */ protected ListNode head; /** The number of elements in this linked-list. */ protected int numElements; /** A reference to the last element of this linked-list. */ protected ListNode tail; }