Sorted Linked List using comparable in Java

Question

I am writing a ordered linked list for an assignment. We are using comparable, and I am struggling to get boolean add to work properly. I have labored over this code for two weeks now, and I am going cross-eyed looking at the code. I could really appreciate a fresh set of eyes on my code.

The code should work for Comparable data - both ints and String (not mixed though). I can get close to making each work, but not one code that stands for all. Please help me fix this, so the code works for either Strings or Ints.

I am only allowed to alter the add(), remove() and OrderedListNode classes

Update Thanks to parkydr, I was able to work out some of my issues, however, I am still getting a null point error. I am testing both int and Strings. If the String loop has a "<" in the while section then elements come back in reverse order. I will be an error for ints with that though. If I have >=, like parkydr said, then I get back the ints in proper order, but Strings get a null pointer error. How do I get both to work together?

Update2 the ints need to be in order, like in the code from AmitG.

Edit Does anyone have any ideas?

package dataStructures;

/**
*   Class OrderedLinkedList.
*
*   This class functions as a linked list, but ensures items are stored in ascending     
    order.
*
*/
public class OrderedLinkedList
{

/**************************************************************************
 * Constants
 *************************************************************************/

/** return value for unsuccessful searches */
private static final OrderedListNode NOT_FOUND = null;


/**************************************************************************
 * Attributes
 *************************************************************************/

/** current number of items in list */
private int theSize;

/** reference to list header node */
private OrderedListNode head;

/** reference to list tail node */
private OrderedListNode tail;

/** current number of modifications to list */
private int modCount;


/**************************************************************************
 * Constructors
 *************************************************************************/


/**
 *  Create an instance of OrderedLinkedList.
 *
 */
public OrderedLinkedList()
{
    // empty this OrderedLinkedList
    clear();

}


/**************************************************************************
 * Methods
 *************************************************************************/


/*
 *  Add the specified item to this OrderedLinkedList.
 *
 *  @param  obj     the item to be added
 */
public boolean add(Comparable obj){
   OrderedListNode node = new OrderedListNode(obj);
   OrderedListNode head2 = new OrderedListNode(obj);
   OrderedListNode tail2 = new OrderedListNode(obj);
       if (head2 == null)
       {
           head2 = node;
           tail2 = node;
           return true;
       }


       // When the element to be added is less than the first element in the list
       if (obj.compareTo(head2.theItem) < 0)
       {
           node.next = head2;
           head2 = node;
           return true;
       }

       // When the element to be added is greater than every element in in list
       // and has to be added at end of the list
       if (obj.compareTo(tail2.theItem) > 0)
       {
           tail2.next = node;
           tail2 = node;
           return true;
       }

       //When the element to be added lies between other elements in the list
       if (obj.compareTo(head2.theItem) >= 0 && obj.compareTo(tail2.theItem) <= 0)
       {
          OrderedListNode current = head.next;
          OrderedListNode previous = head;
          while (obj.compareTo(current.theItem) >= 0)
          {
              previous = current;
              current = current.next;
          }
          previous.next = node;
          node.next = current;

       }

       return true;
   }  

/*
 *  Remove the first occurrence of the specified item from this   
            OrderedLinkedList.
 *
 *  @param  obj     the item to be removed
 */
public boolean remove(Comparable obj)
{
   OrderedListNode curr = head;
       OrderedListNode prev = head;

       while(curr != null && ! (curr.theItem.compareTo(obj) == 0)){
       prev = curr;
       curr = curr.next;
       }
       if(curr == null)
      return false;
       else{
          prev.next = curr.next;
          curr = null;
          return true;
     }  
  }



/**
 *  Empty this OrderedLinkedList.
 */
public void clear()
{
    // reset header node
    head = new OrderedListNode("HEAD", null, null);

        // reset tail node
        tail = new OrderedListNode("TAIL", head, null);

        // header references tail in an empty LinkedList
        head.next = tail;

        // reset size to 0
    theSize = 0;

    // emptying list counts as a modification
    modCount++;
}


/**
 *  Return true if this OrderedLinkedList contains 0 items.
 */
public boolean isEmpty()
{
    return theSize == 0;
}


/**
 *  Return the number of items in this OrderedLinkedList.
 */
public int size()
{
    return theSize;
}


/*  
 *  Return a String representation of this OrderedLinkedList.
 *
 *  (non-Javadoc)
 *  @see java.lang.Object#toString()
 */
@Override
public String toString()
{
    String s = "";

    OrderedListNode currentNode = head.next;

    while (currentNode != tail)
    {
        s += currentNode.theItem.toString();

        if (currentNode.next != tail)
        {
            s += ", ";
        }

        currentNode = currentNode.next;
    }

    return s;
}


/**************************************************************************
 * Inner Classes
 *************************************************************************/


/**
 *  Nested class OrderedListNode.
 *
 *  Encapsulates the fundamental building block of an OrderedLinkedList
 *  contains a data item, and references to both the next and previous nodes
 *  in the list
 */


// TODO: Implement the nested class OrderedListNode (5 points).  This nested class
// should be similar to the nested class ListNode of the class LinkedList, but
// should store a data item of type Comparable rather than Object.
    public static class OrderedListNode {


    Comparable theItem;   
        OrderedListNode next;
        OrderedListNode prev;


        OrderedListNode( Comparable theItem ) { this( theItem, null, null ); }

        OrderedListNode( Comparable theItem, OrderedListNode prev, OrderedListNode next)
        {
           this.theItem = theItem;         
           this.next = next;        
           this.prev = prev;
        }

        Comparable getData() { return theItem; }

        OrderedListNode getNext() { return next; }

        OrderedListNode getPrev() { return prev; }

        }
  // Remove - for testing only
   public static void main (String[] args)
   {
     OrderedLinkedList list = new OrderedLinkedList();
     list.add("1");
     list.add("4");
     list.add("3");
     list.add("33");
     list.add("4");
     System.out.println(list.toString());

   }

 }

This above code works for ints for the most part except that items are stored as strings lexically. So I need help fixing that. I also need to make this code work with Strings as well. Right now the below code works with String but not ints, it also stores in reverse order since the <= changes in the while statement. Help!

Notice that the change in sign will make Strings work (albeit in reverse order):

  while (obj.compareTo(current.theItem) <= 0)

Answer 1

import java.util.*;

public class List {

    private Node head;
    private int manyNodes;

    public List() {
        head = null;
        manyNodes = 0;
    }

    public boolean isEmpty() {
        return ((head == null) && (manyNodes == 0));
    }

    public void add(int element) {
        if (head == null) {
            head = new Node(element, null);
            manyNodes++;
        } else {
            head.addNodeAfter(element);
            manyNodes++;
        }
    }

    public boolean remove(int target) {
        boolean removed = false;

        Node cursor = head;
        Node precursor;

        if (head == null) {
            throw new NoSuchElementException("Cannot remove from empty list");
        }

        if (head.getInfo() == target) {
            head = head.getNodeAfter();
            manyNodes--;
            removed = true;
        } else {
            precursor = cursor;
            cursor = cursor.getNodeAfter();

            while ((cursor != null) && (!removed)) {
                if (cursor.getInfo() == target) {
                    precursor.removeNodeAfter();
                    manyNodes--;
                    removed = true;
                } else {
                    precursor = cursor;
                    cursor = cursor.getNodeAfter();
                }
            }
        }

        return removed;
    }

    public Node getFront() {
        return head;
    }

    public int size() {
        return manyNodes;
    }

    public Node listSort(Node source) {
        source = head;

        int largest = Integer.MIN_VALUE;
        int smallest;

        Node front;

        while (source != null) {
            if (source.getInfo() > largest) {
                largest = source.getInfo();
            }

            source = source.getNodeAfter();
        }

        front = new Node(Node.find(head, largest).getInfo(), null);
        remove(largest);

        while (!isEmpty()) {
            source = head;
            smallest = Integer.MAX_VALUE;

            while (source != null) {
                if (source.getInfo() <= smallest) {
                    smallest = source.getInfo();
                }

                source = source.getNodeAfter();
            }

            remove(smallest);
            front.addNodeAfter(smallest);
        }

        head = front.reverse(front);
        source = head;
        return source;
    }

    public void showList() {
        Node cursor = head;

        if (cursor == null) {
            System.out.println("This list contains no items.");
        } else {
            while (cursor != null) {
                System.out.print(cursor.getInfo() + " ");
                cursor = cursor.getNodeAfter();
            }
        }
    }

}//end class List

Answer 2

Here's my latest version of add. It does not set up the prev links (I'll leave that as an "exercise for the reader").

   public boolean add(Comparable obj){
       OrderedListNode node = new OrderedListNode(obj);

       // When the list is empty
       if (head.next == tail)
       {
           head.next = node;
           node.next = tail;
           tail.prev = node;
           return true;
       }


       // When the element to be added is less than the first element in the list
       if (obj.compareTo(head.next.theItem) < 0)
       {
           node.next = head.next;
           head.next = node;
           return true;
       }

       //When there is an element in the list

       OrderedListNode current = head.next;
       OrderedListNode previous = head;
       while (current != tail && node.theItem.compareTo(current.theItem) >= 0)
       {
          previous = current;
          current = current.next;
       }

       previous.next = node;
       node.next = current;

       return true;
   }

Answer 3

Modified program, output will be 1,3,33,4,4
if you want output like 1,3,4,4,33 then remove line 1 and line 2 from the following program and paste following code. Add and toString methods are modified.

int currentValue = Integer.parseInt(freshNode.theItem.toString());  
int tempValue = Integer.parseInt(nodeToTraverse.theItem.toString());
if(currentValue>tempValue)  

Complete code

/**
 * Class OrderedLinkedList.
 * 
 * This class functions as a linked list, but ensures items are stored in
 * ascending order.
 * 
 */
public class OrderedLinkedList {

    /**************************************************************************
     * Constants
     *************************************************************************/

    /** return value for unsuccessful searches */
    private static final OrderedListNode NOT_FOUND = null;

    /**************************************************************************
     * Attributes
     *************************************************************************/

    /** current number of items in list */
    private int theSize;

    /** reference to list header node */
    private OrderedListNode head;

    /** reference to list tail node */
    private OrderedListNode tail;

    /** current number of modifications to list */
    private int modCount;

    /**************************************************************************
     * Constructors
     *************************************************************************/

    /**
     * Create an instance of OrderedLinkedList.
     * 
     */
    public OrderedLinkedList() {
        // empty this OrderedLinkedList
//       clear();  //work around with this method. Removed temporarily.

    }

    /**************************************************************************
     * Methods
     *************************************************************************/

    /*
     * Add the specified item to this OrderedLinkedList.
     * 
     * @param obj the item to be added
     */
    public void add(Comparable obj) {
        OrderedListNode freshNode = new OrderedListNode(obj);
        if (head == null) {
            head = freshNode;
            tail = freshNode;
            return;
        }
        OrderedListNode nodeToTraverse = head;
        while(nodeToTraverse!=null)
        {
            int result = freshNode.theItem.compareTo(nodeToTraverse.theItem);  // line 1
            if(result>0)   // line 2
            {
                if(nodeToTraverse.next==null)
                {
                    nodeToTraverse.next=freshNode;
                    freshNode.prev =nodeToTraverse;
                    break;
                }
                else
                {
                    nodeToTraverse=nodeToTraverse.next;
                    continue;
                }
            }
            else
            {
                nodeToTraverse.prev.next = freshNode;
                freshNode.prev = nodeToTraverse.prev;
                freshNode.next= nodeToTraverse;
                nodeToTraverse.prev=freshNode;
                break;
            }
        }
    }

    /*
     * Remove the first occurrence of the specified item from this
     * OrderedLinkedList.
     * 
     * @param obj the item to be removed
     */
    public boolean remove(Comparable obj) {
        OrderedListNode curr = head;
        OrderedListNode prev = head;

        while (curr != null && !(curr.theItem.compareTo(obj) == 0)) {
            prev = curr;
            curr = curr.next;
        }
        if (curr == null)
            return false;
        else {
            prev.next = curr.next;
            curr = null;
            return true;
        }
    }

    /**
     * Empty this OrderedLinkedList.
     */
    public void clear() {
        // reset header node
        head = new OrderedListNode("HEAD", null, null);

        // reset tail node
        tail = new OrderedListNode("TAIL", head, null);

        // header references tail in an empty LinkedList
        head.next = tail;

        // reset size to 0
        theSize = 0;

        // emptying list counts as a modification
        modCount++;
    }

    /**
     * Return true if this OrderedLinkedList contains 0 items.
     */
    public boolean isEmpty() {
        return theSize == 0;
    }

    /**
     * Return the number of items in this OrderedLinkedList.
     */
    public int size() {
        return theSize;
    }

    /*
     * Return a String representation of this OrderedLinkedList.
     * 
     * (non-Javadoc)
     * 
     * @see java.lang.Object#toString()
     */
    @Override
    public String toString() {
        String s = "";

        OrderedListNode temp = head;
        while (temp != null) {
            s = s + temp.theItem.toString()+",";
            temp = temp.next;
        }

        return s.substring(0,s.lastIndexOf(",")); //this will remove last comma
//      return s; //1,2,3,4,5,25,33, this will not remove last comma(,)
    }

    /**************************************************************************
     * Inner Classes
     *************************************************************************/

    /**
     * Nested class OrderedListNode.
     * 
     * Encapsulates the fundamental building block of an OrderedLinkedList
     * contains a data item, and references to both the next and previous nodes
     * in the list
     */

    // TODO: Implement the nested class OrderedListNode (5 points). This nested
    // class
    // should be similar to the nested class ListNode of the class LinkedList,
    // but
    // should store a data item of type Comparable rather than Object.

    // Remove - for testing only
    public static void main(String[] args) {
        OrderedLinkedList list = new OrderedLinkedList();
        /*list.add("1");
        list.add("4");
        list.add("3");
        list.add("33");
        list.add("5");
        list.add("2");
        list.add("25");*/
        list.add("1");
         list.add("4");
         list.add("3");
         list.add("33");
         list.add("4");

        System.out.println(list.toString());
    }

    private static class OrderedListNode {
        Comparable data;
        Comparable theItem;
        OrderedListNode next;
        OrderedListNode prev;

        OrderedListNode(Comparable data) {
            this(data, null, null);
        }

        OrderedListNode(Comparable data, OrderedListNode prev, OrderedListNode next) {
            this.theItem = data;
            this.next = next;
            this.prev = prev;
        }

        Comparable getData() {
            return data;
        }

        OrderedListNode getNext() {
            return next;
        }

        OrderedListNode getPrev() {
            return prev;
        }
        @Override
        public String toString() {
            return (String)theItem;
        }

    }
}