Help with this Java source code?

Discussion in 'OT Technology' started by hdot, Sep 28, 2008.

  1. hdot

    hdot New Member

    Joined:
    Jan 25, 2007
    Messages:
    10,758
    Likes Received:
    0
    Location:
    Texas
    This is for my computer science class .. We were given source code for an ordered linked list and asked to write the remove method and given a test, which it was required to pass. Now, I understand what needs to be done for the remove method, but I'm having trouble understanding the code so I'm stuck on how to implement it.

    Obviously, the remove method can't remove from an empty list, so I will check for that. If it is the first element, it should be removed and the remainder of the list should be returned, and finally if it is not the first element, the first element should be left alone and whatever remains after the remove method is completed is to be appended to the first element and returned.. Which would be as follows:

    Code:
    Node remove(Node list, T data) [COLOR=navy]{[/COLOR]
       [COLOR=navy][B]if[/B][/COLOR] (list == [COLOR=navy][B]null[/B][/COLOR]) [COLOR=navy][B]return[/B][/COLOR] [COLOR=navy][B]null[/B][/COLOR];
       [COLOR=navy][B]if[/B][/COLOR] (list.data == data) [COLOR=navy][B]return[/B][/COLOR] list.next;
       list.next= remove(list.next, data);
       [COLOR=navy][B]return[/B][/COLOR] list;
    [COLOR=navy]}[/COLOR]
    This would complete everything that I need it to do, but I have no idea how to implement it because I don't understand the rest of the code. My professor gave no explanation and this is only my second experience working with lists so the code went a bit over my head.

    Here is the Node Class:
    Code:
    package listOps;
    /**
     * Node of a singly linked list, which stores references to its
     * element and to the next node in the list.
     * 
     */
    
    public class Node<E> {
      // Instance variables:
      private E element;
      private Node<E> next;
      /** Creates a node with null references to its element and next node. */
      public Node() {
        this(null, null);
      }
      /** Creates a node with the given element and next node. */
      public Node(E e, Node<E> n) {
        element = e;
        next = n;
      }
      // Accessor methods:
      public E getElement() {
        return element; 
      }
      public Node<E> getNext() { 
        return next;
      }
      // Modifier methods:
      public void setElement(E newElem) { 
        element = newElem; 
      }
      public void setNext(Node<E> newNext) {
        next = newNext; 
      }
      
      public String toString() {
          return element.toString();
      }
    }
    Here is the OrderedLinkedList class:
    Code:
    package listOps;
    import java.util.Iterator;
    import java.util.NoSuchElementException;
    
    /** 
     * 
     * @author H. Paul Haiduk
     *
     * @param <ElementType> -- any type that implements the Comparable interface
     * 
     * The container is implemented as the recursively defined list 
     * of Node<ElementType> such that list ::= null | Node -> list
     * 
     * Class invariants:
     *         1) The list is maintained as a singly-linked list of Nodes.
     *         2) numElements indicates the number of nodes in the list.
     *         3) All non-trivial methods are implemented recursively. 
     *         4) The values of the Nodes is monotonically increasing.
     *         5) The ordering is stable in that for any Node x whose value
     *            is equal to the value of Node y, a traversal of the list
     *            will visit x first if it was inserted into the list first.
     *         6) ElementType MUST implement interface Comparable.
     *         7) All mutating methods have algorithmic complexity O(n).
     * 
     */
    
    public class OrderedLinkedList<ElementType extends Comparable<ElementType>> 
                  implements Iterable<ElementType> {
        
        private int numElements;
        private Node<ElementType> list;
    
        public OrderedLinkedList() {
            numElements = 0;
            list = null;
        }
        
        public void traverse() {
            traversep(list);
        }
        
        private void traversep(Node<ElementType> list) {
            if ( list == null )
                System.out.printf("\n");
            else {
                System.out.printf("%s ", list);
                traversep (list.getNext());
            }
        }
        /**
         * @return number of elements in list
         */
        public int length() {
            return numElements;
        }
        
        /**
         * @param element -- a reference to an element of type ElementType
         */
        public void insert(ElementType element) {
            list = insertp(list, element);
            numElements++;  //all insertions are assumed to be successful
        }
        
        /**
         * @param list -- reference to head of list
         * @param element -- the element to be inserted in the list
         * @return reference to head of new list
         */
        private Node<ElementType> insertp(Node<ElementType> list, ElementType element) {
            if ( (list == null) || ( element.compareTo(list.getElement() ) < 0 ) ) { 
                // test for insert at head or before current node
                Node<ElementType> newNode = new Node<ElementType>(element, null);
                newNode.setNext(list);
                return newNode;
            } 
            else if (list.getNext() == null) { // list with one element
                Node<ElementType> newNode = new Node<ElementType>(element, null);
                list.setNext(newNode);         // element goes at end
            }
            else if ( element.compareTo(list.getNext().getElement()) < 0 ) { // insert after list
                Node<ElementType> newNode = new Node<ElementType>(element, list.getNext());
                //newNode.setNext(list.getNext());
                list.setNext(newNode);
            } 
            else {
                insertp(list.getNext(), element); // find insertion point
            }
            return list;
        }
        
        /**
         * @param element -- a reference to an element of type ElementType
         */
        public void remove(ElementType element) {
            list = removep(list, element);
        }
        
        /**
         * @param list -- reference to head of list
         * @param element -- element to be removed from list if it exists
         * @return reference to head of possibly altered list
         */
        private Node<ElementType> removep (Node<ElementType> list, ElementType element) {
            //student is to implement removep with the above signature
                    
        }
        
        /**
         * Reverses the list such that traversal of elements is monotonically
         * decreasing
         * 
         * CAUTION: leaving the list in reversed state will cause insert
         * and remove methods to fail
         */
        public void reverse() {
            Node <ElementType> tmp = null;
            list = reversep(list, tmp);
        }
        
        /**
         * @param list -- reference to head of list
         * @param tmp -- supporting reference to reverse list
         * @return reference to head of reversed list
         */
        private Node<ElementType> reversep(Node<ElementType> list, Node<ElementType> tmp){    
            Node<ElementType> head;
            if (list == null) return list;
            head = reversep(list.getNext(), list);
            if (list.getNext() == null) head = list;
            list.setNext(tmp);
            return head;
        }
        
        public Iterator<ElementType> iterator() {
            return new OrderedLinkedListIterator();
        }
        
        /**
         * This class supports use of the for ... each construct
         * eg. If this list is used to hold integers (really Integers), then
         * for (int value : myList)
         *         System.out.printf("%d", value);
         *
         */
        private class OrderedLinkedListIterator implements Iterator<ElementType> {
            Node<ElementType> cursor;
            public OrderedLinkedListIterator() {
                cursor = list;
            }
            
            public boolean hasNext() {
                return cursor != null;
            }
            
            public ElementType next() {
                try {
                    ElementType next = cursor.getElement();
                    cursor = cursor.getNext();
                    return next;
                }
                catch (NullPointerException npe) {
                    throw new NoSuchElementException();
                }
            }
            
            public void remove() {
                throw new UnsupportedOperationException();
            }
        }
        
        public String toString() {
            StringBuffer sb = new StringBuffer();
            sb.append("[");
            for (ElementType element : this) {
                sb.append( ' ' + element.toString() );
            }
            sb.append(" ]");
            return sb.toString();
        }
    
    }
    
    I have no idea how to implement what I've written for the remove method into what is there. Any help would be greatly appreciated.
     
  2. hdot

    hdot New Member

    Joined:
    Jan 25, 2007
    Messages:
    10,758
    Likes Received:
    0
    Location:
    Texas
    I thought I might clarify that the part I'm not understanding is how to use the compareTo() method. If some one could possibly break down what exactly is done when that method is called from the above example of the insertp function, I would probably be able to continue from tehre..
     
  3. critter783

    critter783 OT Supporter

    Joined:
    Jul 15, 2005
    Messages:
    1,785
    Likes Received:
    0
    The insertp function is a recursive element insert function that uses the CompareTo method to find out where the new element goes. CompareTo return -1 if the object is less than the argument, 0 if the object is equal to the argument, and >1 if the object is greater than the argument. Here's what happens.

    The new element is compared to the head element in the list (if one exists). If the new element is less than the first element in the list (or the list is empty), the new element is inserted at the head of the list.
    Next, it checks to see if the list is one element long. If it is, the new element is inserted at the end of the list. We know that the element doesn't belong before the first element, since we already checked that.
    Next, it checks to see if the new element goes between the first and second elements. If it does, it inserts the new element.
    Finally, it tries to the whole thing over again, but this time, the function uses the 2nd node in the list as the head node.
     
  4. hdot

    hdot New Member

    Joined:
    Jan 25, 2007
    Messages:
    10,758
    Likes Received:
    0
    Location:
    Texas
    :bowdown:

    That's a better explanation than anyone had given me.. I turned in the project and had it done correctly (based on what little my professor gave me) but didn't understand it. Thanks bro.
     

Share This Page