Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Everything works with this program. It takes both Strings and ints, however, I feel like my add method is simply too verbose. Does anyone believe I can implement a shorter version of this, or is it good as is?

Note: Nothing can be changed in any of the method signatures or parameters. The only thing I can change is the code within the add and remove methods, as well as the custom nested OrderedListNode class.

    public class OrderedLinkedList {

static Comparable temp; //this will be used to reference an element that was removed

public static void main(String[] args) {

    /*
    TEST STRINGS
     */
    OrderedLinkedList list = new OrderedLinkedList();
    modCount = 0;
    list.add("Dog");
    list.add("Bird");
    list.add("dog");
    list.add("bird");
    list.add("Cat");
    System.out.println("Before removal");
    System.out.println(list);
    list.remove("Dog");
    System.out.println("Removed " + temp);
    list.remove("bird");
    System.out.println("Removed " + temp);
    System.out.println("After removal");
    System.out.println(list);
    System.out.println("Total modifications = " + modCount); //make sure modification count is correct
    System.out.println("Size of Ordered List = " + theSize); //make sure size is correct
    System.out.println();

    /*
    TEST INTEGERS
     */
    OrderedLinkedList integerList = new OrderedLinkedList();
    modCount = 0;
    integerList.add(1);
    integerList.add(233);
    integerList.add(42);
    integerList.add(100);
    System.out.println("Before removal");
    System.out.println(integerList);
    integerList.remove(1);
    System.out.println("Removed " + temp);
    integerList.add(232);
    System.out.println("After removal of " + temp + " and addition of another element");
    System.out.println(integerList);
    System.out.println("Total modifications = " + modCount); //make sure modification count is correct
    System.out.println("Size of Ordered List = " + theSize); //make sure size is correct
}
/**************************************************************************
 * Constants
 *************************************************************************/

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

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

/**
 * current number of items in list
 */
private static 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 static 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) {
    // TODO: Implement this method (8 points)

    //FOR REFERENCE - public OrderedListNode(Comparable item, OrderedListNode before, OrderedListNode next) {

    OrderedListNode newElement = NOT_FOUND;

    if(head.next == tail) { //if the list contains only the head and tail (head.next being the tail) place item between the two.
        newElement = new OrderedListNode(obj, head, tail);
        head.next = newElement; // [HEAD -> newElement -> TAIL]
        tail.before = newElement;
        modCount++; //
        theSize++; //if size is not increased, output will not print correctly
        return true;
    }
    for(OrderedListNode element = head.next; element != tail; element = element.next) { //loop through each node of the list, stopping at the tail

        if(element.before == head && obj.compareTo(element.dataItem) < 0) { //if head is before inserted element and less than element at cursor
            newElement = new OrderedListNode(obj, head, element);

            head.next = newElement; //swap cursors
            element.before = newElement;
            modCount++; //another modification
            theSize++; //increase size by 1
            return true;
        }
        if(obj.compareTo(element.dataItem) > 0 && element.next == tail) { //if inserted element is greater than dataItem and next is tail
            newElement = new OrderedListNode(obj, element, tail);

            element.next = newElement;
            tail.before = newElement;
            modCount++; //another modification
            theSize++; //increase size by 1
            return true;
        }
        if(obj.compareTo(element.dataItem) > 0 && obj.compareTo(element.next.dataItem) < 0) { //if inserted element is greater than element at cursor, but less than current element

            OrderedListNode elementBefore = element;
            OrderedListNode elementAfter = element.next;

            newElement = new OrderedListNode(obj, element, element.next);
            elementBefore.next = newElement;
            elementAfter.before = newElement;
            modCount++; //another modification
            theSize++; //increase size by 1
            return true;
        }
    }
    return false;
}

/*
 *  Remove the first occurrence of the specified item from this OrderedLinkedList.
 *
 *  @param  obj     the item to be removed
 */
public boolean remove(Comparable obj) {
    // TODO: implement this method (7 points)

    for(OrderedListNode element = head.next; element != tail; element = element.next) {

        if(obj.equals(element.dataItem)) { //if element being removed is at the cursor
            OrderedListNode previousNode = element.before;
            OrderedListNode nextNode = element.next;
            temp = obj; //temp will be used to access element that was removed

            nextNode.before = previousNode; //places next element that's after before to the element after current element [prev -> current -> next]

            previousNode.next = nextNode; //places prev of next element to the element before current

            element.dataItem = (Comparable)NOT_FOUND; //removed element is now null

            modCount++; //another modification
            theSize--; //reduce the size by 1
            return true; //if remove is successful
        }
    }
    return false; //otherwise, not successful removal
}

/**
 * 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.dataItem.toString();

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

        currentNode = currentNode.next;
    }
    return s;
}

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

/**
 * Nested class OrderedListNode.
 * <p>
 * Encapsulates the fundamental building block of an OrderedLinkedList
 * contains a data item, and references to both the next and before 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 {

    /**
     * FOR REFERENCE
     * <p>
     * private static class Node<E> {
     * E item;
     * Node<E> next;
     * Node<E> prev;
     * <p>
     * Node(Node<E> prev, E element, Node<E> next) {
     this.item = element;
     this.next = next;
     this.prev = prev;
     * }
     * }
     */
    Comparable dataItem;
    OrderedListNode next;
    OrderedListNode before;

    public OrderedListNode(Comparable item, OrderedListNode before, OrderedListNode next) {
        this.dataItem = item;
        this.next = next;
        this.before = before;
    }
}//end nested class
}

Output:

Before removal
Bird, Cat, Dog, bird, dog
Removed Dog
Removed bird
After removal
Bird, Cat, dog
Total modifications = 7
Size of Ordered List = 3

Before removal
1, 42, 100, 233
Removed 1
After removal of 1 and addition of another element
42, 100, 232, 233
Total modifications = 6
Size of Ordered List = 4
share|improve this question
    
Can you please confirm that private static int theSize; was given to you like that and cannot be changed? – janos Mar 13 at 7:23
    
I did change that so I could use it in other areas. For example. in the add and remove methods, I wanted to increment or decrement the size with each modification. Also, after posting this, I included the size in the print statements in the main method. I can edit my post to show this. – IRGeekSauce Mar 13 at 7:35
    
Please also confirm that the class name was given as OrderedLinkedList, and without type parameter, or is that your own writing? As a homework exercise, I would expect something different, something like SortedLinkedList<T extends Comparable<T>> – janos Mar 13 at 9:36
    
@janos the class OrderedLinkedList with parameter Comparable obj is as instructed. Everything was a template with the add and remove methods left empty (except for the signature), and we had to create the nested class ourselves. – IRGeekSauce Mar 13 at 19:05
up vote 1 down vote accepted

Concerns

Although you wrote:

Nothing can be changed in any of the method signatures or parameters. The only thing I can change is the code within the add and remove methods, as well as the custom nested OrderedListNode class.

However, in a comment you confirmed other changes you made, such as private static int theSize;.

As it's not very clear what was really given, I'd like to point out some troubling points.

  1. Type safety. An untyped collection of comparable elements is a dysfunctional idea. Such a collection will accept both "some text" and the number 7, and if you try to compare the two the program will crash at runtime. Something from which the compiler could have protected.

  2. Calling clear() in a constructor: at construction time, this doesn't make any sense, the object is empty. If your program doesn't work correctly without this, then you're not using OOP correctly.

  3. The comment in theSize++; //if size is not increased, output will not print correctly is troubling: behavior during output should not be the reason for incrementing the size. The reason for incrementing the size should be that a new element is being added.

  4. The name "ordered" doesn't make sense when talking about lists: lists are ordered by definition. It's the ordering that sets a List apart from a Collection. I think the term you're looking for is "sorted".

Simplifying add

Your main question was how to shorten the add method. The current logic is checking too many cases, unnecessarily. You can simplify using this algorithm:

  • Set node to head
  • Loop over the nodes until node.next is tail
    • Compare obj with node.next
    • If they are equal, then no need to insert, return false
    • If obj is less than node.next, then break out of the loop
  • Insert the new node before node.next
    • Note that at this point, node.next either has a larger value than obj, or it is tail
    • Setup the links correctly (node -> new -> node.next), increment size and modification count

Something like this:

public boolean add(Comparable obj) {

    OrderedListNode node = head;

    for (; node.next != tail; node = node.next) {

        int cmp = obj.compareTo(node.next.dataItem);

        if (cmp == 0) {
            return false;
        }

        if (cmp < 0) {
            // obj is less than next, so should be inserted before next
            break;
        }
    }

    OrderedListNode newNode = new OrderedListNode(obj, node, node.next);
    newNode.next.before = newNode;
    node.next = newNode;

    modCount++;
    theSize++;
    return true;
}
share|improve this answer
    
I changed theSize and modCount temporarily so I could print it during testing in the main method. Aside from my code edit, your concerns actually concern me as well now because I didn't write the template for the program. You made some very valid points. As far as using Comparable goes, this was one of the instructions: Remember that because the items in the list must be stored in sorted order, you will need to use data items of type Comparable rather than type Object. As far as not incrementing the size creating a problem, I will continue to look into this and try to find out why. – IRGeekSauce Mar 13 at 19:56
1  
Using Comparable is good, but it should be made type-safe: the class declared as SortedLinkedList<T extends Comparable<T>>, and the add method declared as add(Comparable<T> obj), and so on... – janos Mar 13 at 20:08
    
Thanks! Also, I was doing more work than necessary by changing the modCount and theSize to static. When I created a new OrderedLinkedList object in main, I simply called the variables, like: 'list.modCount = 0; ' and 'System.out.println("Total modifications = " + list.modCount);' – IRGeekSauce Mar 13 at 21:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.